| Summary: | A bipartite graph
$H = \left (V_1, V_2; E \right )$
with
$\lvert V_1\rvert + \lvert V_2\rvert = n$
is semilinear if
$V_i \subseteq \mathbb {R}^{d_i}$
for some
$d_i$
and the edge relation E consists of the pairs of points
$(x_1, x_2) \in V_1 \times V_2$
satisfying a fixed Boolean combination of s linear equalities and inequalities in
$d_1 + d_2$
variables for some s. We show that for a fixed k, the number of edges in a
$K_{k,k}$
-free semilinear H is almost linear in n, namely
$\lvert E\rvert = O_{s,k,\varepsilon }\left (n^{1+\varepsilon }\right )$
for any
$\varepsilon> 0$
; and more generally,
$\lvert E\rvert = O_{s,k,r,\varepsilon }\left (n^{r-1 + \varepsilon }\right )$
for a
$K_{k, \dotsc ,k}$
-free semilinear r-partite r-uniform hypergraph.
|
|---|