Zarankiewicz’s problem for semilinear hypergraphs
Open Access
- 31 August 2021
- journal article
- research article
- Published by Cambridge University Press (CUP) in Forum of Mathematics, Sigma
- Vol. 9
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).
Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- AN O-MINIMAL SZEMEREDI-TROTTER THEOREMThe Quarterly Journal of Mathematics, 2018
- A semi-algebraic version of Zarankiewicz's problemJournal of the European Mathematical Society, 2017
- On the Zarankiewicz problem for intersection hypergraphsJournal of Combinatorial Theory, Series A, 2016
- Separation Dimension of Bounded Degree GraphsSIAM Journal on Discrete Mathematics, 2015
- Weakly one-based geometric theoriesThe Journal of Symbolic Logic, 2012
- Separator theorems and Turán-type results for planar intersection graphsAdvances in Mathematics, 2008
- Trivial Stable Structures with Non-Trivial ReductsJournal of the London Mathematical Society, 2005
- Coloring intersection graphs of geometric figures with a given clique number2004
- Additive reducts of real closed fieldsThe Journal of Symbolic Logic, 1992
- Extremal problems in discrete geometryCombinatorica, 1983