pith. sign in

arxiv: 2604.20815 · v1 · submitted 2026-04-22 · 🧮 math.CO

A dichotomy for hypergraph Zarankiewicz problems on axis-parallel boxes

Ting-Wei Chao , Zichao Dong , Hong Liu , Xichao Shu , Shuaichao Wang This is my paper

Pith reviewed 2026-05-09 23:42 UTC · model grok-4.3

classification 🧮 math.CO
keywords Zarankiewicz problemhypergraphsaxis-parallel boxesincidence geometryextremal combinatoricsdichotomy2-coherence
0
0 comments X

The pith

Zarankiewicz numbers for r-partite box hypergraphs are either Θ(t n^{r-1}) or Ω(t n^{r-1} log n / log log n) depending on whether the direction sets satisfy 2-coherence.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies the maximum number of edges in r-uniform r-partite hypergraphs whose vertices are axis-parallel boxes in R^d drawn from r families, each with a prescribed set of coordinate directions. It proves that this extremal function exhibits a sharp dichotomy controlled by a purely combinatorial condition on those direction sets. When the condition holds the bound matches the obvious construction up to constants; when it fails the number of edges must be larger by a logarithmic factor that traces back to planar point-line incidences. The argument proceeds by a chain of reductions that ultimately slices the higher-dimensional geometry down to a planar incidence problem while preserving the leading asymptotics.

Core claim

For any r and any choice of direction sets F1, …, Fr subsets of {1,…,d}, the Zarankiewicz number in this geometric setting is Θ_r(t n^{r-1}) unless the tuple (F1,…,Fr) is 2-coherent, in which case it is at least Ω(t n^{r-1} log n / log log n). The extra factor appears precisely when the directions contain an underlying two-dimensional incidence configuration; the proof reduces every instance to such a planar problem via slicing and combinatorial reductions without altering the asymptotic order.

What carries the argument

The 2-coherence condition on the tuple of direction sets (F1,…,Fr), which detects whether the configuration embeds a two-dimensional incidence structure that forces the polylogarithmic term.

Load-bearing premise

The reductions and geometric slicing argument map every configuration to an equivalent planar incidence problem without introducing extra asymptotic factors or omitting cases that would change the dichotomy.

What would settle it

An explicit family of 2-coherent direction sets whose box-intersection hypergraph has o(t n^{r-1} log n / log log n) edges, or a non-2-coherent family whose hypergraph has ω(t n^{r-1}) edges.

Figures

Figures reproduced from arXiv: 2604.20815 by Hong Liu, Shuaichao Wang, Ting-Wei Chao, Xichao Shu, Zichao Dong.

Figure 1
Figure 1. Figure 1: The proof outline of Theorem 3.1. Reduction I. In R d , define the canonical direction-vector as F⃗ d def = [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A αe z x y [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
read the original abstract

We study the Zarankiewicz problem for $r$-partite, $r$-uniform intersection hypergraphs arising from $r$ families of axis-parallel boxes in $\mathbb{R}^d$ with prescribed directions $F_1, \dots, F_r \subseteq \{1, \dots, d\}$. This extends the problems studied by Chan and Har-Peled on points and $d$-dimensional boxes in $\mathbb{R}^d$, corresponding to $(F_1,F_2)=(\varnothing,[d])$, as well as by Chan, Keller, and Smorodinsky on $r$ families of $d$-dimensional boxes, corresponding to $(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 $\Theta_r(tn^{r-1})$ or at least $\Omega \bigl( tn^{r-1} \cdot \frac{\log n}{\log\log n} \bigr)$, depending only on a simple set-theoretic condition on $(F_1,\dots,F_r)$, which we call $2$-coherence. Informally, $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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript studies the Zarankiewicz problem for r-partite r-uniform intersection hypergraphs formed by r families of axis-parallel boxes in R^d with prescribed direction sets F_1,...,F_r. It proves a sharp dichotomy: the extremal function is Θ_r(t n^{r-1}) or Ω(t n^{r-1} log n / log log n) according to whether the tuple (F_1,...,F_r) satisfies the set-theoretic condition of 2-coherence (which detects the presence of an underlying 2-dimensional incidence structure). The argument proceeds by a sequence of reductions followed by a geometric slicing argument that reduces the problem to known planar incidence bounds.

Significance. If the reductions and slicing preserve exact asymptotics, the result supplies a clean, parameter-free classification for a natural family of geometric hypergraph extremal problems, extending the earlier work of Chan-Har-Peled and Chan-Keller-Smorodinsky. The simple combinatorial predicate 2-coherence and the reduction to planar bounds are strengths that make the dichotomy potentially reusable in other incidence settings.

major comments (2)
  1. [Proof of the main dichotomy theorem] The geometric slicing argument and the preceding reductions (detailed after the definition of 2-coherence): each step must be shown to map arbitrary direction sets F_i to planar point-line incidences without introducing hidden polylogarithmic factors that would collapse the two sides of the claimed dichotomy or omitting configurations where the 2D structure appears or disappears.
  2. [Section introducing 2-coherence] Definition of 2-coherence: the formal predicate must be verified to be exactly equivalent to the existence of a 2-dimensional subconfiguration that triggers the planar incidence bound with the log n / log log n factor, with no post-hoc exclusions that alter the asymptotic orders for the non-coherent cases.
minor comments (2)
  1. [Abstract] The abstract's informal gloss on 2-coherence is useful but should be paired with the formal definition in the introduction for immediate clarity.
  2. [Introduction] Notation for the extremal function z(F_1,...,F_r; n,t) and the parameter t should be fixed consistently from the first appearance onward.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback on our manuscript. We appreciate the positive assessment of the overall contribution and will revise the paper to address the concerns about clarity and rigor in the proof and the definition of 2-coherence.

read point-by-point responses

  1. Referee: [Proof of the main dichotomy theorem] The geometric slicing argument and the preceding reductions (detailed after the definition of 2-coherence): each step must be shown to map arbitrary direction sets F_i to planar point-line incidences without introducing hidden polylogarithmic factors that would collapse the two sides of the claimed dichotomy or omitting configurations where the 2D structure appears or disappears.

    Authors: We agree that the reductions and slicing argument require more explicit verification to confirm the absence of extraneous polylogarithmic factors and the precise preservation of 2D structures. In the revised manuscript we will insert a new subsection that analyzes each reduction step in turn, proving asymptotic equivalence to planar incidences and showing via case analysis on direction sets that the mapping respects 2-coherence exactly. This will ensure the two sides of the dichotomy remain separated by the claimed factor. revision: yes

  2. Referee: [Section introducing 2-coherence] Definition of 2-coherence: the formal predicate must be verified to be exactly equivalent to the existence of a 2-dimensional subconfiguration that triggers the planar incidence bound with the log n / log log n factor, with no post-hoc exclusions that alter the asymptotic orders for the non-coherent cases.

    Authors: We will strengthen the section by adding a formal equivalence proof between the 2-coherence predicate and the existence of an underlying 2-dimensional incidence subconfiguration. The proof will establish both directions without post-hoc exclusions, confirming that the logarithmic factor appears if and only if 2-coherence holds. Illustrative examples and counterexamples will be included to demonstrate that the asymptotic distinction is preserved for all direction tuples. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation reduces to external planar incidence bounds via independent reductions

full rationale

The paper establishes its dichotomy for the Zarankiewicz number via a sequence of reductions and geometric slicing that map the r-partite r-uniform box intersection hypergraphs to planar incidence problems. These incidence bounds are external, established results from incidence geometry and are not derived or fitted within the paper. The 2-coherence predicate is a purely set-theoretic condition on the direction sets (F1,...,Fr) that is defined independently of the asymptotic claims. No equations, definitions, or self-citations in the abstract or described proof chain reduce the Theta_r(t n^{r-1}) or Omega(t n^{r-1} log n / log log n) bounds to inputs by construction, fitted parameters, or load-bearing prior results by the same authors. The argument is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof relies on standard planar incidence bounds and introduces the new combinatorial notion of 2-coherence; no free parameters or invented geometric entities are described.

axioms (1)
  • standard math Known asymptotic bounds on incidences between points and lines (or curves) in the plane
    The geometric slicing reduces the original hypergraph problem to planar incidence problems whose extremal bounds are taken as given.

pith-pipeline@v0.9.0 · 5574 in / 1314 out tokens · 61342 ms · 2026-05-09T23:42:47.686080+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

  1. [1]

    P. K. Agarwal and J. Erickson. Geometric range searching and its relatives. InAdvances in discrete and computational geometry (South Hadley, MA, 1996), volume 223 ofContemp. Math., pages 1–56. Amer. Math. Soc., Providence, RI, 1999

    work page 1996

  2. [2]

    N. Alon, L. R´ onyai, and T. Szab´ o. Norm-graphs: variations and applications.J. Combin. Theory Ser. B, 76(2):280–290, 1999

    work page 1999

  3. [3]

    Basit, A

    A. Basit, A. Chernikov, S. Starchenko, T. Tao, and C.-M. Tran. Zarankiewicz’s problem for semilinear hypergraphs.Forum Math. Sigma, 9:No. e59, 2021

    work page 2021

  4. [4]

    B. Bukh. Random algebraic construction of extremal graphs.Bull. Lond. Math. Soc., 47(6):939– 945, 2015

    work page 2015

  5. [5]

    B. Bukh. Extremal graphs without exponentially small bicliques.Duke Math. J., 173(11):2039– 2062, 2024

    work page 2039

  6. [6]

    Chalermsook, L

    P. Chalermsook, L. Orgo, and M. Zarsav. On geometric bipartite graphs with asymptotically smallest Zarankiewicz numbers. In33rd International Symposium on Graph Drawing and Net- work Visualization, volume 357 ofLIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 21, 24. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2025

    work page 2025

  7. [7]

    T. M. Chan and S. Har-Peled. On the number of incidences when avoiding an induced biclique in geometric settings.Discrete Comput. Geom., 73(2):466–489, 2025

    work page 2025

  8. [8]

    T. M. Chan, C. Keller, and S. Smorodinsky. On Zarankiewicz’s problem for intersection hyper- graphs of geometric objects, 2024. arXiv:2412.06490. 21

    work page arXiv 2024

  9. [9]

    T. M. Chan, C. Keller, and S. Smorodinsky. On Zarankiewicz’s problem for intersection hy- pergraphs of geometric objects. In41st International Symposium on Computational Geometry, volume 332 ofLIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 33, 14. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2025

    work page 2025

  10. [10]

    T. M. Chan and D. W. Zheng. Hopcroft’s problem, log-star shaving, 2D fractional cascading, and decision trees. InProceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 190–210. [Society for Industrial and Applied Mathematics (SIAM)], Philadelphia, PA, 2022

    work page 2022

  11. [11]

    Chazelle

    B. Chazelle. Lower bounds for orthogonal range searching: I. the reporting case.J. ACM, 37(2):200–212, 1990

    work page 1990

  12. [12]

    Q. Chen, H. Liu, and K. Ye. Extremal constructions for apex partite hypergraphs, 2025. arXiv:2510.07997

    work page arXiv 2025

  13. [13]

    P. Erd˝ os. On extremal problems of graphs and generalized graphs.Israel J. Math., 2:183–190, 1964

    work page 1964

  14. [14]

    Fox and J

    J. Fox and J. Pach. A separator theorem for string graphs and its applications.Combin. Probab. Comput., 19(3):371–390, 2010

    work page 2010

  15. [15]

    J. Fox, J. Pach, A. Sheffer, A. Suk, and J. Zahl. A semi-algebraic version of Zarankiewicz’s problem.J. Eur. Math. Soc. (JEMS), 19(6):1785–1810, 2017

    work page 2017

  16. [16]

    Hunter, A

    Z. Hunter, A. Milojevi´ c, B. Sudakov, and I. Tomon.C 4-free subgraphs of high degree with geometric applications, 2025. arXiv:2506.23942

    work page arXiv 2025

  17. [17]

    Keller and S

    C. Keller and S. Smorodinsky. Zarankiewicz’s problem viaϵ-t-nets. In40th International Sympo- sium on Computational Geometry, volume 293 ofLIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 66, 15. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2024

    work page 2024

  18. [18]

    Koll´ ar, L

    J. Koll´ ar, L. R´ onyai, and T. Szab´ o. Norm-graphs and bipartite Tur´ an numbers.Combinatorica, 16(3):399–406, 1996

    work page 1996

  19. [19]

    K¨ ovari, V

    T. K¨ ovari, V. T. S´ os, and P. Tur´ an. On a problem of K. Zarankiewicz.Colloq. Math., 3:50–57, 1954

    work page 1954

  20. [20]

    J. Ma, X. Yuan, and M. Zhang. Some extremal results on complete degenerate hypergraphs.J. Combin. Theory Ser. A, 154:598–609, 2018. 22

    work page 2018

  21. [21]

    N. H. Mustafa and J. Pach. On the Zarankiewicz problem for intersection hypergraphs.J. Combin. Theory Ser. A, 141:1–7, 2016

    work page 2016

  22. [22]

    Szemer´ edi and W

    E. Szemer´ edi and W. T. Trotter. Extremal problems in discrete geometry.Combinatorica, 3(3-4):381–392, 1983

    work page 1983

  23. [23]

    Tidor and H.-H

    J. Tidor and H.-H. H. Yu. Multilevel polynomial partitioning and semialgebraic hypergraphs: regularity, Tur´ an, and Zarankiewicz results, 2024. arXiv:2407.20221

    work page arXiv 2024

  24. [24]

    I. Tomon. Coloring lines and Delaunay graphs with respect to boxes.Random Structures Algo- rithms, 64(3):645–662, 2024

    work page 2024

  25. [25]

    Zarankiewicz

    K. Zarankiewicz. Problem 101.Colloquium Mathematicum, 2:301, 1951. A Proof of Theorem 4.7 InR 1, there are only two possible direction sets,∅or{1}. A box family with direction set∅is a collection of points, and a box family with direction set{1}is a collection of segments. To prove Theorem 4.7, we begin with ther= 2 case. Firstly, we establish the result ...

    work page 1951