Zarankiewicz’s problem for semilinear hypergraphs

A bipartite graph H = (V₁,V₂; E) with |V₁| + |V₂| = n is semilinear if V_i ⊆ R^di for some d_i and the edge relation E consists of the pairs of points (x₁, x₂) ∈ V₁ × V₂ satisfying a fixed Boolean combination of s linear equalities and inequalities in d₁+d₂ 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¹+^ε) 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₁ points and n₂ open boxes with axis-parallel sides in R^d such that their incidence graph is K_k,k-free, there can be at most O_k,ε (n¹+^ε) 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 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).