A dichotomy for hypergraph Zarankiewicz problems on axis-parallel boxes

Ting-Wei Chao, Zichao Dong, Hong Liu, Xichao Shu, Shuaichao Wang · 2026

Read A dichotomy for hypergraph Zarankiewicz problems on axis-parallel boxes by Ting-Wei Chao, Zichao Dong, Hong Liu, Xichao Shu, Shuaichao Wang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-20815.txt.

Introduction

Chao, Dong, Liu, Shu, and Wang study the Zarankiewicz problem for intersection hypergraphs from r families of axis-parallel boxes with prescribed directions. Their main result is a sharp dichotomy for the Zarankiewicz number. The number is either Theta of t times n to the r minus 1, or at least that times log n over log log n. The split depends only on a set-theoretic condition called 2-coherence. 2-coherence captures whether the configuration holds an underlying two-dimensional incidence structure, which gives rise to the extra polylogarithmic factor.

Catalog record

CREATORTing-Wei Chao, Zichao Dong, Hong Liu, Xichao Shu, Shuaichao Wang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE73894
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.20815

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A dichotomy for hypergraph Zarankiewicz problems on axis-parallel boxes Ting-Wei Chao, Zichao Dong, Hong Liu, Xichao Shu, Shuaichao Wang Abstract We study the Zarankiewicz problem for r r -partite, r r -uniform intersection hypergraphs arising from r r families of axis-parallel boxes in ℝ d \mathbb{R}^{d} with prescribed directions F 1 , … , F r ⊆ { 1 , … , d } F_{1},\dots,F_{r}\subseteq\{1,\dots,d\} . This extends the problems studied by Chan and Har-Peled on points and d d -dimensional boxes in ℝ d \mathbb{R}^{d} , corresponding to ( F 1 , F 2 ) = ( ∅ , [ d ] ) (F_{1},F_{2})=(\varnothing,[d]) , as well as by Chan, Keller, and Smorodinsky on r r families of d d -dimensional boxes, corresponding to ( F 1 , … , F r ) = ( [ d ] , … , [ d ] ) (F_{1},\dots,F_{r})=([d],\dots,[d]) . Our main result establishes a sharp dichotomy for the Zarankiewicz number in this setting: it is either Θ r ​ ( t ​ n r − 1 ) \Theta_{r}(tn^{r-1}) or at least Ω ⁡ ( t ​ n r − 1 ⋅ log ⁡ n log ⁡ log ⁡ n ) \Omega\bigl(tn^{r-1}\cdot\frac{\log n}{\log\log n}\bigr) , depending only on a simple set-theoretic condition on ( F 1 , … , F r ) (F_{1},\dots,F_{r}) , which we call 2 2 - coherence . Informally, 2 2 -coherence captures whether the configuration contains an underlying two-dimensional incidence structure, which is precisely what gives rise to the extra polylogarithmic factor. Our proof proceeds via a sequence of reductions and a geometric slicing argument that reduces the problem to planar incidence bounds. 1 Introduction In 1951, Zarankiewicz [ 25 ] asked for the maximum number z(n;t) of edges in a bipartite graph on 2n vertices and parts of size n containing no copy of K_{t,t} . The classical Kővári–Sós–Turán theorem [ 19 ] implies z(n;t)=O\bigl(n^{2-\frac{1}{t}}\bigr) . Determining its tightness remains a major open problem, though several algebraic incidence constructions [ 18 , 2 , 4 , 5 ] show it is tight for K_{s,t} in place of K_{t,t} when s\gg t . In 1964, Erdős [ 13 ] proposed a natural hypergraph analogue: determine the maximum number z_{r}(n;t) of hyperedges in an r -uniform, r -partite hypergraph on rn vertices with parts of size n that contains no copy of K^{(r)}_{t,\dots,t} . In the same paper, he proved the upper bound z_{r}(n;t)=O\bigl(n^{r-\frac{1}{t^{r-1}}}\bigr) , which generalizes the Kővári–Sós–Turán theorem. Analogous tightness results [ 20 , 12 ] are known when the largest parameter t_{r} is much larger than t_{1},\dots,t_{r-1} , for K_{t_{1},\dots,t_{r}}^{(r)} in place of K_{t,\dots,t}^{(r)} . Zarankiewicz problems on axis-parallel boxes. Bipartite graphs naturally model geometric incidences or intersections. Consider the incidence graph G between n points and n lines, where an edge connects a point p and a line \ell if p\in\ell . Since two points determine a unique line, G contains no K_{2,2} . The Kővári–Sós–Turán theorem then yields e(G)=O(n^{3/2}) , while the Szemerédi–Trotter theorem [ 22 ] , a central result in incidence geometry, improves this bound to the tight O(n^{4/3}) . The incidence problems are closely related to algorithmic problems in theoretical computer science such as range searching [ 1 ] and the so-called Hopcroft’s problem [ 10 ] . We refer to [ 21 , 7 , 9 ] for related studies on simplices, balls, pseudo-disks, and other geometric objects. This paper studies Zarankiewicz problems for incidences between axis-parallel boxes. For any positive integer n , we use the standard notation [n]\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}\{1,\dots,n\} . Throughout the whole paper, every box refers to an axis-parallel box . We require several notations. In the d -dimensional Euclidean space \mathbb{R}^{d} , an axis-parallel box is the product of d closed intervals \bm{b}=[a_{1},b_{1}]\times\dots\times[a_{d},b_{d}] , where a_{i}\leq b_{i}\,(i=1,\dots,d) are real numbers. If a_{i}=b_{i} , then \bm{b} collapses along the i -th coordinate axis. We call the set \bigl\{i\in[d]:a_{i}<b_{i}\bigr\} the direction set of \bm{b} . For example, the box \{0\}\times[e,\pi]\times\{\frac{2}{3}\} in \mathbb{R}^{3} collapses in the 1 -st and 3 -rd coordinates and has direction set \{2\} . In the literature, axis-parallel boxes usually exclude the case a_{i}=b_{i} . However, we allow such degeneracies and study a strictly more general class of configurations. We call boxes with direction set [d] (i.e., without any a_{i}=b_{i} for i=1,\dots,d ) full boxes . Let d\geq 1,\,r\geq 2 . In \mathbb{R}^{d} , every r - direction - vector \vec{F}\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}(F_{1},\dots,F_{r}) refers to an r -tuple of subsets of [d] . An r -tuple of sets * * * Hereafter boxes in each set are not necessarily distinct, and so formally all the box sets we consider are multisets. of boxes (\mathcal{B}_{1},\dots,\mathcal{B}_{r}) is an \vec{F} - family if each box in \mathcal{B}_{j} has direction set F_{j} . For \vec{F} -family (\mathcal{B}_{1},\dots,\mathcal{B}_{r}) , we study the r -uniform r -partite intersection hypergraph \mathcal{H}=(V,E) , where V\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}\mathcal{B}_{1}\cup\dots\cup\mathcal{B}_{r} and \{\bm{b}_{1},\dots,\bm{b}_{r}\}\in E if and only if \bm{b}_{1}\cap\dots\cap\bm{b}_{r}\neq\varnothing . For r - size - vector \vec{n}=(n_{1},\dots,n_{r}) of positive integers, denote by z_{d}^{\vec{F}}(\vec{n};t)=z_{d}^{\vec{F}}(n_{1},\dots,n_{r};t) the maximum number of edges in \mathcal{H} , provided that |\mathcal{B}_{j}|=n_{j} for j=1,\dots,r and \mathcal{H} forbids the complete r -partite subgraph K_{t,\dots,t}^{(r)} . We also introduce the abbreviated notation z_{d}^{\vec{F}}(n;t)\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}z_{d}^{\vec{F}}\bigl(\underbrace{n,\dots,n}_{r};t\bigr) . The Zarankiewicz problem between points and full boxes in \mathbb{R}^{d} , where \vec{F}=(\varnothing,[d]) , has been extensively studied. In the complexity analysis of orthogonal range reporting, Chazelle [ 11 ] constructed random points and boxes in \mathbb{R}^{d} to deduce z_{d}^{\vec{F}}(n;2)=\Omega\bigl(n(\frac{\log n}{\log\log n})^{d-1}\bigr) . This construction was later reformulated in mathematical language and generalized by Tomon [ 24 ] and by Chan–Har-Peled [ 7 ] to z_{d}^{\vec{F}}(n;t)=\Omega\bigl(tn(\frac{\log n}{\log\log n})^{d-1}\bigr) . Basit, Chernikov, Starchenko, Tao, and Tran [ 3 ] obtained the upper bound z_{d}^{\vec{F}}(n;t)=O_{d,t}\bigl(n(\log n)^{2d}\bigr) . This upper bound was later improved by Chan–Har-Peled [ 7 ] to z_{d}^{\vec{F}}(n;t)=O_{d}\bigl(tn(\frac{\log n}{\log\log n})^{d-1}\bigr) , matching the lower bound and thereby resolving the problem. The Zarankiewicz problem for full boxes has also attracted much attention. Keller and Smorodinsky [ 17 ] established z_{2}^{\vec{F}}(n;t)=\Theta_{t}\bigl(n\frac{\log n}{\log\log n}\bigr) for rectangles, where \vec{F}=([2],[2]) . Chan, Keller, and Smorodinsky [ 8 ] later extended this to incidence r -hypergraphs in \mathbb{R}^{d} and improved the dependence on t to linear, obtaining the sharp bound z_{d}^{\vec{F}}(n;t)=\Theta_{r,d}\bigl(tn^{r-1}(\frac{\log n}{\log\log n})^{d-1}\bigr) for \vec{F}=\bigl(\underbrace{[d],\dots,[d]}_{r}\bigr) . For an arbitrary \vec{F} , the lower bound z_{d}^{\vec{F}}(n;t)\geq(t-1)\cdot n^{r-1} is straightforward. Indeed, suppose each box in \mathcal{B}_{1},\dots,\mathcal{B}_{r-1} contains the origin. In \mathcal{B}_{r} , choose t-1 boxes containing the origin and place the remaining n-t+1 boxes far away so that they intersect no others. Then the intersection hypergraph is K_{n,\dots,n,t-1}^{(r)} , which contains no K_{t,\dots,t}^{(r)} , and thus yields (t-1)\,n^{r-1} hyperedges. In some cases, this lower bound is tight. For example, for intervals (\{1\},\{1\}) in \mathbb{R}^{1} and for planar vertical and horizontal segments (\{1\},\{2\}) in \mathbb{R}^{2} , it was previously established in [ 7 , 17 ] that z_{1}^{(\{1\},\{1\})}(n;t)=\Theta(tn) and z_{2}^{(\{1\},\{2\})}(n;t)=\Theta(tn) . On the other hand, an additional logarithmic factor is sometimes unavoidable: for the aforementioned (\varnothing,[2]) in \mathbb{R}^{2} and ([3],[3],[3]) in \mathbb{R}^{3} , it is known [ 7 , 9 ] that z_{2}^{(\varnothing,[2])}(n;t)=\Theta\bigl(tn\tfrac{\log n}{\log\log n}\bigr) and z_{3}^{([3],[3],[3])}(n;t)=\Theta\bigl(tn^{2}(\tfrac{\log n}{\log\log n})^{2}\bigr) . Motivated by these results on z_{d}^{\vec{F}}(n;t) for different direction-vectors \vec{F} , a natural question arises: Under what conditions on \vec{F} does a

Read the complete text