## Abstract

A bipartite graph H = (V_{1},V_{2}; E) with |V_{1}| + |V_{2}| = n is semilinear if V_{i} ⊆ R^{di} for some d_{i} and the edge relation E consists of the pairs of points (x_{1}, x_{2}) ∈ 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 R^{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 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).

Original language | English |
---|---|

Article number | e59 |

Number of pages | 23 |

Journal | Forum of Mathematics, Sigma |

Volume | 9 |

DOIs | |

Publication status | Published - 31 Aug 2021 |

Externally published | Yes |

## Keywords

- incidence combinatorics
- local modularity
- o-minimality
- semilinear hypergraphs
- Zarankiewicz’s problem