Skip to main content
Open Access Publications from the University of California


UCLA Previously Published Works bannerUCLA

Zarankiewicz’s problem for semilinear hypergraphs


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^{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).

Many UC-authored 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
For improved accessibility of PDF content, download the file to your device.
Current View