 Main
Zarankiewicz’s problem for semilinear hypergraphs
Published Web Location
https://doi.org/10.1017/fms.2021.52Abstract
AbstractA 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^{r1 + \varepsilon }\right )$for a$K_{k, \dotsc ,k}$free semilinearrpartiteruniform hypergraph.As an application, we obtain the following incidence bound: given$n_1$points and$n_2$open boxes with axisparallel 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 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 modeltheoretic trichotomy inominimal structures (showing that the failure of an almostlinear bound for some definable graph allows one to recover the field operations from that graph in a definable manner).
Many UCauthored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.
Main Content
Enter the password to open this PDF file:













