Submission date: 7 September 2020

Abstract:

A bipartite graph H = (V_1, V_2; E ) with |V_1| + |V_2| = n is semilinear if V_i ⊆ ℝ^{d_i} for some d_i and the edge relation E consists of the pairs of points (x_1, x_2) in V_1 × 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 |E| = O_{s,k,ε}(n^{1+ε}) for any ε > 0; and more generally, |E| = O_{s,k,r,ε}(n^{r-1 + ε}) for a K_{k, .... ,k}-free semilinear r-partite r-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 ℝ^d such that their incidence graph is K_{k,k}-free, there can be at most O_{k,ε}(n^{1+ε}) incidences. The same bound holds if instead of boxes one takes polytopes cut out by the translates of an arbitrary fixed finite set of halfspaces. 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 in o-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).

Mathematics Subject Classification: 05D10, 52C10, 52C45, 03C45, 03C64

Keywords and phrases:

Full text arXiv 2009.02922: pdf, ps.