Pith. sign in

REVIEW 3 major objections 3 minor 1 cited by

On Zarankiewicz's Problem for Intersection Hypergraphs of Geometric Objects

T0 review · 3 major / 3 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves near-optimal Zarankiewicz bounds for intersection hypergraphs of boxes and pseudo-discs; in the box case the logarithmic factor does not grow with r.

desk verdict Strong, likely-correct bound for boxes; the pseudo-disc theorem has a real gap in the clipping step that needs fixing. read the letter →

arxiv 2412.06490 v2 pith:QOQGQPKN submitted 2024-12-09 math.CO cs.CG

Timothy M. Chan , Chaya Keller , Shakhar Smorodinsky This is my paper · ORCID
classification math.COcs.CG MSC 05C6505C3552C45
keywords Zarankiewiczproblemintersectionhypergraphsaxis-parallelboxespseudo-discsextremalcombinatoricsbicliquecoversshallowcuttingsgeometric
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Zarankiewicz's problem for hypergraphs asks how many intersecting r-tuples can be formed from r families of n objects each, under the condition that the resulting r-partite hypergraph contains no complete t-by-t-by-...-by-t subhypergraph. This paper proves that for axis-parallel boxes in $\mathbb{R}^d$ the answer is $O_{r,d}(t n^{r-1} (\log n / \log \log n)^{d-1})$, a bound whose logarithmic factor does not grow with $r$ and which is sharp in both $n$ and $t$. For $y$-monotone pseudo-discs it proves the bound $O_r(t n^{r-1} (\log n)^{r-2})$, sharp up to a factor of $(\log n)^{r-2}$. These are the first improvements over the 60-year-old general hypergraph bound in geometric settings with no algebraic structure, and the pseudo-disc bound improves the best previous semialgebraic disc bound by a polynomial factor. The proofs reduce the hypergraph problem to lopsided two-family graph Zarankiewicz bounds, then reassemble the $r$ parts using biclique covers and shallow cuttings.

What carries the argument

The argument is carried by four objects. A lopsided graph Zarankiewicz theorem (Theorem 2.1) bounds intersections between two families of boxes with unequal side sizes, splitting vertex-containment intersections from facet intersections. A biclique-cover lemma (Lemma 2.7) partitions the intersection graph of two box families into $O(b\log^{d-1} b)$ full and partial bicliques, so the proof can split two coordinates at a cost that does not explode with $r$. A constraints graph on the $r$ parts records which pairs of families contain a disjoint pair of boxes; the proof removes its edges inductively, and the Helly number 2 property of boxes (any pairwise intersecting family of boxes has a common point) converts a $K_{t,t}$ into a $K^r_{t,t,\ldots,t}$. For pseudo-discs, shallow cuttings (a plane decomposition whose cells are crossed by few boundaries) and a lopsided point-versus-pseudo-disc bound supply the induction step, while a clipping-plus-perturbation step cuts every pseudo-disc to the common intersection $Z$ of a chosen set and keeps the clipped family inside the pseudo-disc class.

What would settle it

Find two $y$-monotone pseudo-discs $s_1,s_2$ and a set $T$ of pseudo-discs whose common intersection $Z$ forces the clipped boundaries $s_1'$ and $s_2'$ to have at least three crossing points inside $Z$ under every perturbation of the type described in Section 3.2. Such a pair would show the clipping step can destroy the pseudo-disc property, invalidating the induction in the proof of Theorem 1.2.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that $r$-partite intersection hypergraphs of geometric families inherit near-optimal Zarankiewicz bounds from lopsided two-family intersection graph bounds, with no algebraic assumptions needed. Theorem 1.1 states that for $r,d,t\ge 2$ and $n$ axis-parallel boxes in general position in $\mathbb{R}^d$, every $K^r_{t,t,\ldots,t}$-free intersection hypergraph has at most $O_{r,d}(t n^{r-1} (\log n/\log\log n)^{d-1})$ hyperedges, and matching lower bounds show this is sharp. Theorem 1.2 states that for $r$ families of $n$ $y$-monotone pseudo-discs in general position, the number of hyperedges is $O_r(t n^{r-1}(\log n)^{r-2})$, sharp up to logarithmic factors. The paper also conjectures that the pseudo-disc truth is $O_r(t n^{r-1})$ and that this would follow from a lopsided version of the linear graph-level bound.

Load-bearing premise

The load-bearing premise is that clipping every pseudo-disc to the common intersection region $Z$ of a chosen set $T$, then perturbing boundaries slightly, yields a family whose boundaries still cross at most twice; if clipping can create a third crossing between two boundaries, the induction step that builds a forbidden $K^r_{t,t,\ldots,t}$ fails.

Editorial extensions

If this is right

  • For axis-parallel boxes, the maximum number of hyperedges is now pinned down up to constant factors, and the power of $\log n$ in the bound does not depend on $r$.
  • The box result improves the previous semilinear bound by a factor of about $(\log n)^{d(2^{r-1}-2)}$.
  • For pseudo-discs, the bound $O_r(t n^{r-1}(\log n)^{r-2})$ improves the best previous semialgebraic disc bound by a factor of order $n^{(2r-2)/(3r-2)}$.
  • In the pseudo-disc case, an optimal lopsided two-family graph bound would upgrade the theorem to the conjectured $O_r(t n^{r-1})$.
  • The lower-bound construction from the graph setting extends to $r$ families by adding $r-2$ families of large boxes, so the box bound is sharp in both $n$ and $t$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If a stronger lopsided graph bound for boxes is ever found, the same biclique-cover and constraints-graph recursion would transplant it verbatim to $r$-partite hypergraphs, because those steps do not depend on the exact graph bound.
  • The constraints-graph recursion has an algorithmic reading the paper does not state: a $K^r_{t,\ldots,t}$-free box hypergraph could be enumerated in time proportional to the bound by splitting only along constraints-graph edges.
  • The pseudo-disc proof hinges on a geometric clipping property; testing whether clipping an arbitrary pseudo-disc family to a convex region $Z$ preserves the at-most-two-crossings condition would show whether Theorem 1.2 extends beyond $y$-monotone pseudo-discs or to other simply connected regions.
  • The logarithmic gap in the pseudo-disc result could be probed by constructing $K^r_{t,\ldots,t}$-free $r$-partite intersection hypergraphs with $n^{r-1}$ times a polylogarithmic number of hyperedges, modeled on graph-level lower-bound constructions; the paper does not provide such lower bounds.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper studies the hypergraph Zarankiewicz problem for r-partite intersection hypergraphs of geometric objects. The first main result, Theorem 1.1, gives an O_{r,d}( t n^{r-1} (log n / log log n)^{d-1} ) bound for axis-parallel boxes in R^d, improving the previous bound of Basit et al. by a factor of about (log n)^{d(2^{r-1}-2)} and matching the known lower bound up to the dependence on t. The second main result, Theorem 1.2, gives O_r( t n^{r-1} (log n)^{r-2} ) for y-monotone pseudo-discs, which is sharp up to logarithmic factors. The proofs introduce a lopsided bipartite Zarankiewicz bound for boxes, a modified biclique cover lemma, an induction on a constraints graph, and a lopsided point--pseudo-disc incidence bound; the pseudo-disc case reduces r to r-1 via a clipping step.

Significance. If both theorems are correct, they are substantial: they give the first improvement over Erdős's 60-year-old general bound for these non-algebraic geometric settings, and the box bound is sharp in both n and t. The biclique-cover lemma and the lopsided bipartite bounds are likely to be useful beyond this paper. The proof of Theorem 1.1 is largely self-contained and the underlying divide-and-conquer arguments are carefully structured. The main risks are the delicate clipping step in Theorem 1.2 and the reliance on two unpublished preprints for base cases; both are localized and appear fixable within the manuscript's scope.

major comments (3)
  1. [Section 3.2] The induction step for Theorem 1.2 rests on the assertion, in the paragraph beginning 'Now, we clip each pseudo-disc s ...', that after clipping every s in A_1 ∪ ... ∪ A_{r-1} to s ∩ Z and applying the described perturbation, the family {s'} is again a family of y-monotone pseudo-discs. This is load-bearing: the induction hypothesis is applied to the clipped (r-1)-partite hypergraph H', and the resulting K^{r-1}_{t,...,t} must be contained in Z. The one-paragraph justification does not constitute a proof. A pseudo-disc boundary can meet ∂Z in up to 2t points, the inclusion partial order on s ∩ ∂Z does not by itself control how many crossings the perturbation adds at the endpoints of the arcs of ∂Z, and the text does not show that s ∩ Z is connected or that the perturbed regions remain y-monotone. Without a rigorous clipping lemma (proved in the paper or quoted with full hypotheses from a published source), Theorem 1.2 is not fully established.
  2. [Section 3.1, Lemma 3.5] The proof of Lemma 3.5 states: 'By the last part of Lemma 3.3, the number of cells in Ξ that contain at least one point of depth between m/r and 2m/r is O(r).' The quoted Lemma 3.3 gives a (1/(2r))-cutting with O(r^2) cells and a per-cell boundary-weight bound; the asserted O(r) bound for cells containing points in that depth range is not a consequence of the statement as written. This bound is what makes the recursion in Theorem 3.2 converge, so the gap is in the main line of the pseudo-disc proof. Please either state the full shallow-cutting theorem from [7] that implies the O(r) cell count, or supply a direct proof.
  3. [Appendix A and Section 3.2] Two load-bearing ingredients are outsourced to preprints that are not yet in final published form. Proposition 2.4 is proved only as a sketch adapting [6, Theorem 3], and Theorem 3.7, the r=2 base case of Theorem 1.2, is quoted from [17], an arXiv preprint. Proposition 2.4 feeds Theorem 2.1 and hence Theorem 1.1; Theorem 3.7 is the induction basis of Theorem 1.2. The manuscript should either include complete proofs of these statements, give their exact statements with all hypotheses, or point to final published versions. As it stands, the correctness of both main theorems depends on the correctness of those preprints.
minor comments (3)
  1. [Section 2.2.3, Case B] In the triangle case, the sentence 'by partitioning each of A_4,...,A_r arbitrarily into b equal parts' appears to be a typo: after the three splits the first three parts have size n/b^2, so to obtain T_G(n/b^2) the remaining r-3 families must be partitioned into b^2 equal parts, not b.
  2. [Section 2.1.3] In the proof of Proposition 2.3, the phrase 'substituting to (14)' should read 'substituting to (1)'; the displayed equation is numbered (1).
  3. [Abstract] There is a typo in the abstract: 'Futhermore' should be 'Furthermore'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main bounds are proved from lopsided graph lemmas and external base cases, not from the target statements.

full rationale

The paper's derivation chain does not reduce any central result to its own inputs. Theorem 1.1 is proved from the lopsided graph bound Theorem 2.1, which is proved in Section 2.1 via Propositions 2.2-2.4; those propositions are proved in the appendix by divide-and-conquer induction and by an adaptation of the external charging argument of [6]/[17], not by assuming Theorem 1.1. Theorem 1.2 is proved by induction on r, with the base case being an external theorem [17, Theorem 1.6] and the induction step using the lopsided point/pseudo-disc bound Theorem 3.2, whose proof is given in Section 3.1 using shallow cuttings from [7] and a recursive counting argument; the lopsided bound is not the same as the target hypergraph bound. The cited prior results of the authors, [7] and [19], are used as auxiliary building blocks (shallow-cutting lemmas and two-family graph bounds) and are either proved in the present paper or are published results by overlapping authors that do not assume the theorem being proved. The one genuinely questionable point is the clipping step in Section 3.2, where preservation of the pseudo-disc property after clipping to Z is asserted with a sketched perturbation argument; this is a correctness gap, not a circularity, because the assertion is not obtained by assuming Theorem 1.2. No equation in the paper reduces to an earlier result by definition, and no fitted parameter is renamed as a prediction. Accordingly, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper relies on standard geometric facts and previously published Zarankiewicz bounds as black boxes. No free parameters or invented entities are introduced.

assumptions (5)
  • domain assumption Axis-parallel boxes in R^d have Helly number 2
    Used in Sections 2.2.1 and 2.2.3 to conclude that pairwise intersecting boxes have a common point, which is essential for constructing a complete r-partite subhypergraph.
  • domain assumption Families are in general position
    Assumed for boxes and pseudo-discs to avoid degeneracies in intersection counts; stated in Section 1.2.
  • standard math Existence of shallow cuttings for pseudo-discs
    Lemma 3.3, cited from Chan and Har-Peled [7], provides the decomposition used in the proof of the lopsided bound for points versus pseudo-discs.
  • domain assumption Intersection of pseudo-discs is connected
    Used in the proof of Theorem 1.2 to define the region Z; cited from Ackerman et al. [2, Theorem 4.4].
  • standard math Base case for r=2 pseudo-discs
    Theorem 3.7 from Hunter et al. [17], which gives a linear bound for bipartite intersection graphs of pseudo-discs, is used as the induction base in Theorem 1.2.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On Zarankiewicz's Problem for Intersection Hypergraphs of Geometric Objects." pith.science (2026). https://pith.science/paper/QOQGQPKN

@misc{pith2026241206490,
  author       = {Pith},
  title        = {Pith review of: On Zarankiewicz's Problem for Intersection Hypergraphs of Geometric Objects},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QOQGQPKN}},
  note         = {Machine review of arXiv:2412.06490}
}
abstract

The hypergraph Zarankiewicz's problem, introduced by Erd\H{o}s in 1964, asks for the maximum number of hyperedges in an $r$-partite hypergraph with $n$ vertices in each part that does not contain a copy of $K_{t,t,\ldots,t}$. Erd\H{o}s obtained a near optimal bound of $O(n^{r-1/t^{r-1}})$ for general hypergraphs. In recent years, several works obtained improved bounds under various algebraic assumptions -- e.g., if the hypergraph is semialgebraic. In this paper we study the problem in a geometric setting -- for $r$-partite intersection hypergraphs of families of geometric objects. Our main results are essentially sharp bounds for families of axis-parallel boxes in $\mathbb{R}^d$ and families of pseudo-discs. For axis-parallel boxes, we obtain the sharp bound $O_{d,r}(tn^{r-1}(\frac{\log n}{\log \log n})^{d-1})$. The best previous bound was larger by a factor of about $(\log n)^{d(2^{r-1}-2)}$. For pseudo-discs, we obtain the bound $O_r(tn^{r-1}(\log n)^{r-2})$, which is sharp up to logarithmic factors. As this hypergraph has no algebraic structure, no improvement of Erd\H{o}s' 60-year-old $O(n^{r-1/t^{r-1}})$ bound was known for this setting. Futhermore, even in the special case of discs for which the semialgebraic structure can be used, our result improves the best known result by a factor of $\tilde{\Omega}(n^{\frac{2r-2}{3r-2}})$. To obtain our results, we use the recently improved results for the graph Zarankiewicz's problem in the corresponding settings, along with a variety of combinatorial and geometric techniques, including shallow cuttings, biclique covers, transversals, and planarity.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. $C_4$-free subgraphs of high degree with geometric applications

    math.CO 2025-06 conditional novelty 8.0 of 10

    A new dichotomy about C4-free induced subgraphs and dense patches yields optimal O(sn) bounds for geometric Zarankiewicz problems and a near-tight semilinear bound.

Reference graph

Works this paper leans on

43 extracted references · 38 canonical work pages · cited by 1 Pith paper

  1. [6]

    Chalermsook, L

    P. Chalermsook, L. Orgo, and M. Zarsav. On geometric bipartite graphs with asymptotically smallest Zarankiewicz numbers, proceedings of GD’25, to appear, 2025

    work page 2025

  2. [17]

    Hunter, A

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

    arXiv 2025

  3. [7]

    T. M. Chan and S. Har-Peled. On the number of incidences when avoiding an induced biclique in geometric settings. InProceedings of SODA 2023, pages 1398–1413. SIAM, 2023

    work page 2023

  4. [1]

    Ackerman and B

    E. Ackerman and B. Keszegh. The Zarankiewicz problem for polygon visibility graphs, available at arxiv:2503.09115, 2025

    arXiv 2025

  5. [2]

    Ackerman, B

    E. Ackerman, B. Keszegh, and D. P´ alv¨ olgyi. Coloring hypergraphs defined by stabbed pseudo- disks and ABAB-free hypergraphs.SIAM J. Discret. Math., 34(4):2250–2269, 2020

    work page 2020

  6. [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:Paper No. e59, 23, 2021

    work page 2021

  7. [4]

    W. G. Brown. On graphs that do not contain a Thomsen graph.Canadian Math. Bulletin, 9(3):281–285, 1966

    work page 1966

  8. [5]

    Compact Representation of Semilinear and Terrain-like Graphs

    J. Cardinal and Y. Yuditsky. Compact representation of semilinear and terrain-like graphs, available at arxiv:2507.00252, 2025

    work page Pith review arXiv 2025

Show all 43 references
  1. [8]

    T. M. Chan, C. Keller, and S. Smorodinsky. On zarankiewicz’s problem for intersection hyper- graphs of geometric objects. InSoCG 2025, volume 332 ofLIPIcs, pages 33:1–33:14. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2025

    2025

  2. [9]

    Chazelle

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

    1990

  3. [10]

    Chekuri, K

    C. Chekuri, K. L. Clarkson, and S. Har-Peled. On the set multicover problem in geometric settings.ACM Trans. Algorithms, 9(1):9:1–9:17, 2012

    2012

  4. [11]

    F. R. K. Chung, P. Erd˝ os, and J. Spencer.On the decomposition of graphs into complete bipartite subgraphs, in: Studies in Mathematics: To the Memory of Paul Tur´ an (P. Erd˝ os, L. Al´ par, G. Ha´lasz, and A. S´ ark¨ ozy, eds.), pages 95–101. Birkh¨ auser, Basel, 1983

    1983

  5. [12]

    T. Do. Zarankiewicz’s problem for semi-algebraic hypergraphs.J. Combin. Th., Ser. A, 158:621–642, 2018

    2018

  6. [13]

    T. Do. Representation complexities of semi-algebraic graphs.SIAM J. Discret. Math., 4(33):1864–1877, 2019

    2019

  7. [14]

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

    1964

  8. [15]

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

    2017

  9. [16]

    Frankl and A

    N. Frankl and A. Kupavskii. On the Erd˝ os-Purdy problem and the Zarankiewitz problem for semialgebraic graphs, available at arxiv: 2112.10245, 2021

    2021 arXiv

  10. [18]

    Janzer and C

    O. Janzer and C. Pohoata. On the Zarankiewicz problem for graphs with bounded VC- dimension.Combinatorica, 44(4):839–848, 2024

    2024

  11. [19]

    Keller and S

    C. Keller and S. Smorodinsky. Zarankiewicz’s problem viaϵ-t-nets. InSoCG 2024, volume 293 ofLIPIcs, pages 66:1–66:15. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2024

    2024

  12. [20]

    K˝ ov´ ari, V

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

    1954

  13. [21]

    Matouˇ sek

    J. Matouˇ sek. Reporting points in halfspaces.Comput. Geom., 2(3):169–186, 1992

    1992

  14. [22]

    Milojevi´ c, B

    A. Milojevi´ c, B. Sudakov, and I. Tomon. Incidence bounds via extremal graph theory, available at arxiv: 2401.06670, 2024

    2024 arXiv

  15. [23]

    B. Sudakov. Recent developments in extremal combinatorics: Ramsey and Tur´ an type prob- lems. InProceedings of the International Congress of Mathematicians. Volume IV, pages 2579–2606, 2010

    2010

  16. [24]

    Tidor and H-H

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

    2024 arXiv

  17. [25]

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

    2024

  18. [26]

    Tomon and D

    I. Tomon and D. Zakharov. Tur´ an-type results for intersection graphs of boxes.Comb. Probab. Comput., 30(6):982–987, 2021

    2021

  19. [27]

    M. Tong. Zarankiewicz bounds from distal regularity lemma, available at arxiv: 2410.13695, 2024. 18 A Lopsided Results for the Graph Zarankiewicz’s Problem In this appendix we prove Propositions 2.2 and 2.4, which give bounds for the lopsided Zarankiewicz problem for the inter...

    2024

  20. [28]

    In the proof of Lemma 35, the only change is that the size ofQ(in the notation of [6]) isgt−1 instead oft−1, since the forbidden biclique isK t,gt

    In the statement of Lemma 35 in [6], no change is required. In the proof of Lemma 35, the only change is that the size ofQ(in the notation of [6]) isgt−1 instead oft−1, since the forbidden biclique isK t,gt

  21. [29]

    Lemma 36 in [6] is symmetric to the aforementioned Lemma 35. 20

  22. [30]

    In the proof of the lemma, again, the only change is that the setQhas sizegt−1 instead oft−1, for the same reason

    In the statement of Lemma 23 in [6], no change is required. In the proof of the lemma, again, the only change is that the setQhas sizegt−1 instead oft−1, for the same reason. The following lemma is a lopsided version of the bound of [7] on the number of edges inK t,t-free bipa...

  23. [31]

    IfG A,B isK t,gt-free (ton the side ofA) then it hasO(gtn+tm)edges

  24. [32]

    IfG A,B isK gt,t-free (ton the side ofB) then it hasO(gtm+tn)edges. Proof.We represent each bottomless rectangle by its ‘upper’ edge (thus obtaining a familyB ′), and represent each point by a long segment emanating from it in the ‘upper’ direction (thus obtaining a familyA ′)...

  25. [33]

    IfG A,B isK t,gt-free (ton the side ofA) then it hasO ϵ gtn logn log logn +tmlog ϵ n edges

  26. [34]

    The proof uses a divide-and-conquer argument, with a parameterb

    IfG A,B isK gt,t-free (ton the side ofB) then it hasO ϵ tn logn log logn +gtmlog ϵ n edges. The proof uses a divide-and-conquer argument, with a parameterb. It is clearly sufficient to prove the following claim, wherebis a parameter that may depend onn, m. Claim A.4.LetAbe a m...

  27. [35]

    IfG A,B isK t,gt-free (ton the side ofA) then it hasO(gtnlog b n+btm)edges

  28. [36]

    Indeed, substitutingb= (logn) ϵ into the claim yields the assertion of Proposition A.3

    IfG A,B isK gt,t-free (ton the side ofB) then it hasO(tnlog b n+bgtm)edges. Indeed, substitutingb= (logn) ϵ into the claim yields the assertion of Proposition A.3. Proof of Claim A.4.LetA, Bbe multisets that satisfy the assumptions of the claim. We divide the plane intobvertic...

  29. [37]

    If the bipartite intersection graphG A,B isK t,gt-free (ton the side ofA) then it has Oϵ gtn( logn log logn)d−1 +tm( logn log logn)d−2+ϵ edges

  30. [38]

    Like in the proof of Proposition A.3 above, it is clearly sufficient to prove the following claim, wherebis a parameter that may depend onn, m

    If the bipartite intersection graph ofG A,B isK gt,t-free (ton the side ofB) then it has Oϵ tn( logn log logn)d−1 +gtm( logn log logn)d−2+ϵ edges. Like in the proof of Proposition A.3 above, it is clearly sufficient to prove the following claim, wherebis a parameter that may d...

  31. [39]

    IfG A,B isK t,gt-free (ton the side ofA) then it hasO(gtn(log b n)d−1 +tmb d−1(logb n)d−2) edges

  32. [40]

    Indeed, substitutingb= (logn) ϵ d−1 into the claim yields the assertion of Proposition A.3

    IfG A,B isK gt,t-free (ton the side ofB) then it hasO tn(logb n)d−1 +gtmb d−1(logb n)d−2 edges. Indeed, substitutingb= (logn) ϵ d−1 into the claim yields the assertion of Proposition A.3. Proof of Claim A.5.The proof is by induction ond. The induction basis is the cased= 2 pro...

  33. [41]

    Each box inBhas either half of its vertices or all of its vertices inU

  34. [42]

    The total number of vertices of boxes inBinsideUism·2 d−1

  35. [43]

    We shall prove that Id(n, m)≤O(gtn(log b n)d−1 +tmb d−1(logb n)d−2)

    The bipartite intersection graph ofA, BisK t,gt-free. We shall prove that Id(n, m)≤O(gtn(log b n)d−1 +tmb d−1(logb n)d−2). This clearly implies the assertion, as by considering a vertical stripUthat fully contains all points inAand boxes inB(where|A|=nand|B|=m), we getE(G A,B)...

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.