UCLA

Abstract: A bipartite graph$H = \left (V_1, V_2; E \right )$with$\lvert V_1\rvert + \lvert V_2\rvert = n$issemilinearif$V_i \subseteq \mathbb {R}^{d_i}$for some$d_i$and the edge relationEconsists of the pairs of points$(x_1, x_2) \in V_1 \times V_2$satisfying a fixed Boolean combination ofslinear equalities and inequalities in$d_1 + d_2$variables for somes. We show that for a fixedk, the number of edges in a$K_{k,k}$-free semilinearHis almost linear inn, 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 semilinearr-partiter-uniform hypergraph. As an application, we obtain the following incidence bound: given$n_1$points and$n_2$open boxes with axis-parallel sides in$\mathbb {R}^d$such that their incidence graph is$K_{k,k}$-free, there can be at most$O_{k,\varepsilon }\left (n^{1+\varepsilon }\right )$incidences. The same bound holds if instead of boxes, one takes polytopes cut out by the translates of an arbitrary fixed finite set of half-spaces. We also obtain matching upper and (superlinear) lower bounds in the case of dyadic boxes on the plane, and point out some connections to the model-theoretic trichotomy ino-minimal structures (showing that the failure of an almost-linear bound for some definable graph allows one to recover the field operations from that graph in a definable manner).