Pith. sign in

REVIEW 3 major objections 4 minor 2 cited by

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

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

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

Pith's one-line read Every graph of average degree d hides either an induced C4-free subgraph of degree at least k or a d-vertex patch with c d^2 edges, and this dichotomy yields optimal Zarankiewicz bounds across geometry.

desk verdict Theorem 1.9 is a real result; referees need to verify the imported Lemma 3.3 before this is final. read the letter →

arxiv 2506.23942 v1 pith:NQIPSHXA submitted 2025-06-30 math.CO cs.CG

Zach Hunter , Aleksa Milojević , Istvan Tomon , Benny Sudakov This is my paper · ORCID
classification math.COcs.CG MSC 05C3505C6205D40
keywords ZarankiewiczprobleminducedC4-freesubgraphdegree-boundedfamiliesdensity-Erdős-Hajnalpropertygeometricgraphtheorystringgraphssemilinearsubdivisions
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

This paper tries to establish a graph-theoretic dichotomy and to show it is the right engine for a broad family of geometric Zarankiewicz problems. The dichotomy says that every graph of average degree d either contains an induced C4-free subgraph of average degree at least k, or contains a subgraph on d vertices with at least c(k)$d^{2}$ edges. If true, a hereditary family of graphs whose C4-free members have bounded average degree and whose dense members contain large bicliques automatically has K_{s,s}-free members of average degree O(s). The paper then uses this to derive tight or near-tight bounds for string graphs, k-intersecting families of curves, convex set intersection graphs, y-monotone pseudodisks, semilinear incidence graphs, and polygon visibility graphs, and to prove a conjecture that sparse graphs of large average degree contain induced subdivisions of any fixed graph.

What carries the argument

The load-bearing object is the (c,t)-sparsity condition and the local control it gives over common neighbourhoods. The paper proves Theorem 1.12 by a four-step extraction: choose a maximal-average-degree induced subgraph with a balanced cut; use the imported Lemma 3.3 to upgrade sparsity so that vertices sharing many neighbours form a set of size O(t); randomly sample to keep edges while destroying all copies of K_{2,v+1} with two vertices on one side; then apply a known theorem converting K_{v+1,v+1}-freeness with large average degree into an induced C4-free subgraph. The 1-subdivision of $K_v^{{(h)}}$, a bipartite graph whose one side encodes all h-subsets of the other, is the obstruction gadget that makes the random sampling work.

What would settle it

Search for a sequence of graphs that are (c,t)-sparse and induced-H-free for some fixed bipartite H yet contain two sets of size at least βt with at least (1−ε)|A||B| edges; such a construction would refute Lemma 3.3 and break the proof of Theorem 1.12.

Watch

Extended reading notes

Core claim

Theorem 1.9 states that for every k there is c=c(k)>0 such that every graph G with average degree d contains either an induced C4-free subgraph of average degree at least k or a subgraph on d vertices with at least c $d^{2}$ edges. The proof runs through a stronger statement, Theorem 1.12: every (c,t)-sparse graph of sufficiently large average degree contains a bipartite induced C4-free subgraph of average degree at least k. From the dichotomy, Corollary 1.10 draws the main structural conclusion: a hereditary family that is weakly degree-bounded (bounded average degree on C4-free members) and has the density-Erdős-Hajnal property (every dense induced subgraph contains a linear-size biclique) has K_{s,s}-free members of average degree O(s). The paper claims this unified mechanism recovers and improves a long list of geometric bounds, including O(s log s) for string graphs without separator theorems, O_k(sn) for k-intersecting curve families, O(sn) for convex sets and for two families of disjoint curves, O(sn) for y-monotone pseudodisks, and O_{dx,h}(t s n (log n/log log n)^{dy-1}) for semilinear graphs.

Load-bearing premise

The proof imports the unproved lemma that a graph which avoids induced copies of a fixed bipartite graph and has no dense pair of large sets (c,t-sparse) also has no nearly complete pair of sets of size βt; if that lemma fails, the local sparsity argument collapses.

Editorial extensions

If this is right

  • Any hereditary family with bounded average degree on C4-free members and large bicliques in dense induced subgraphs automatically has K_{s,s}-free members of average degree O(s).
  • The string graph bound O(s log s) follows without separator theorems, purely from the dichotomy plus a dense-string-graph biclique lemma.
  • For k-intersecting curve families, convex sets, and two families of disjoint curves, the dichotomy plus a new biclique-in-dense-bipartite-curve-intersection-graph theorem gives linear-in-s bounds.
  • Semilinear incidence graphs of dimension (dx,dy) and complexity (h,t) have K_{s,s}-free edge bound O_{dx,h}(t s n (log n/log log n)^{dy-1}), matching the point-box bound up to dimension-dependent constants.
  • A (c,t)-sparse graph of average degree Ω_{H,c}(t) contains an induced subdivision of every fixed graph H, confirming the sparse-graph conjecture.

Reading between the lines

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

  • The dichotomy offers a reusable recipe: to prove degree-boundedness of a hereditary geometric family, check only C4-free members and dense-induced bicliques; this may shorten future proofs that currently rely on separators or epsilon-nets.
  • The semilinear bound suggests the log factor is governed by the ambient dimension of the point side, so any family representable by polytopes with O(1) facet directions should satisfy the same bound; testing point-box incidences in higher dimensions would confirm the range of the method.
  • If Lemma 3.3 turns out to hold only for particular bipartite H, Theorem 1.12 may still be salvageable for those H; a targeted search for counterexamples to the lemma would clarify which sparse graph classes the method covers.
  • The same dichotomy may extend to longer even cycles: replace C4-free by C_{2ℓ}-free in the hypothesis and ask whether the conclusion holds with a corresponding dense patch, which would give an analogue for higher even-cycle obstructions.
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 / 4 minor

Summary. The paper introduces and proves a structural dichotomy for general graphs (Theorem 1.9): for every k there is c(k)>0 such that every graph of average degree at least d either contains an induced C4-free subgraph of average degree at least k, or a subgraph on d vertices with at least c d^2 edges. The dichotomy is derived from a stronger statement about (c,t)-sparse graphs (Theorem 1.12), proved through a four-step sampling argument in Section 3. The authors then use this tool to give uniform and, in several cases, optimal bounds for Zarankiewicz-type problems in geometric settings: string graphs, intersection graphs of k-intersecting curve families, intersection graphs of convex sets, incidence graphs of y-monotone pseudodisks, semilinear graphs, and polygon visibility graphs. The paper also derives a conjecture of Fox, Nenadov, and Pham on induced subdivisions in (c,t)-sparse graphs.

Significance. If the main dichotomy is accepted, the paper is a significant contribution: it unifies a broad range of geometric Zarankiewicz results and obtains tight dependence on s (often O(s n)) that previously required ad-hoc geometric arguments or separator theorems. The overall architecture is coherent and the applications are substantial. The proof of Theorem 1.9 is carefully structured, and the use of the published theorem of Du, Hunter, Girão, McCarty, and Scott (Theorem 3.8) as a black box is appropriate. The main barrier to acceptance is not the internal derivation but the reliance, at a single load-bearing point, on an unproved lemma imported from a preprint, together with a few proof gaps and typos that need to be repaired.

major comments (3)
  1. [Section 3, Lemma 3.3] Lemma 3.3 is imported from Ding–Gao–Liu–Luan–Sun (arXiv:2411.12659) without a proof or even a full statement of the result in the present paper. This lemma is the only mechanism in Lemma 3.4 that upgrades (c,t)-sparsity to (1−ε,βt)-sparsity; that upgraded sparsity is then used twice: to bound |S_a| < t0 and to delete vertices from the sets T_e in Claim 3.5. If Lemma 3.3 fails, the proof of Lemma 3.4 collapses, and with it Theorem 1.12 and Theorem 1.9, on which all geometric applications depend. The paper should either prove the needed special case, give a precise statement with the dependence of β on H and ε, or cite a version that has passed peer review. As written, this is a load-bearing external-preprint dependency and must be resolved before the paper is considered final.
  2. [Section 5, Lemma 5.5, Step 4] In the proof of Lemma 5.5, Step 4 says that a (d−1)-dimensional vertical face F is covered by at most f(d, 2(d−1)) parallelotopes, but the induction is on the dimension d, so the bound should refer to f(d−1, 2(d−1)). As written, the recurrence uses the same dimension d and is circular; this affects the proof of Lemma 5.2 and hence Proposition 5.1 and Theorem 1.7. The error appears to be a typo, but it must be corrected and the induction checked explicitly.
  3. [Section 2, Claim 2.7] Claim 2.7 is stated as a proof sketch, yet it is used to assert that the family of point-halfspace incidence graphs in R^4 is not degree-bounded, which the introduction presents as resolving the open case of dimension 4. Several steps are only sketched: the conversion from rectangles to inscribed ellipses, the deletion argument for close pairs, and the final lifting map. Since this is a claimed theorem rather than an aside, the proof should be completed or the claim should be explicitly downgraded to a conjecture or conditional construction.
minor comments (4)
  1. [Section 3, Lemma 3.4] There is a typo in 'we havεd' in the paragraph after the definition of t0; also the constant K is required to satisfy d/4 ≥ βt/ε, but the displayed inequality says K ≥ 4 C(v,h) β/ε, which should be checked for consistency with the subsequent lower bound on |N(a)|.
  2. [Section 4.2, Lemma 4.5] In the case e(G1) ≥ εn^2/3, the text says a point p in P' is contained in at least εn/2 pseudodisks, but the earlier deletion step only guarantees εn/6. The subsequent conclusion should be adjusted accordingly (the desired bound still follows).
  3. [Section 6] Theorem 6.9 and Theorem 6.11 refer to 'Theorem 1.10' in their final sentences, but the correct reference is Corollary 1.10.
  4. [General] The manuscript contains many typographical errors (e.g., 'strucutral', 'recieved', 'sugbgraph', 'biparite', 'indicedence', 'parrallelotope', 'the set A'' has size at least 2/3 |A''|' in the proof of Theorem 1.2). A careful proofreading pass is needed.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation: Theorem 1.9 follows from a direct averaging argument plus independent cited lemmas; the unproved external Lemma 3.3 is a support gap, not a circular step.

full rationale

The derivation of Theorem 1.9 is not circular. It is obtained from Theorem 1.12 by a direct averaging argument: setting c=1/2 and t=floor(d/C), if G is not (1/2,t)-sparse then the violating pair A,B yields a d-vertex subgraph with at least (1/4)t^2 = Omega(d^2) edges; otherwise Theorem 1.12 supplies the required induced C4-free subgraph of average degree at least k. Theorem 1.12 is then proved through Lemmas 3.2, 3.4, 3.7 and the cited Theorem 3.8. Theorem 3.8 (Du, Girao, Hunter, McCarty, Scott) does share a coauthor with the present paper, but it is a published, parameter-free theorem whose hypothesis (K_{s,s}-free with large average degree) is not the paper's target dichotomy, and it is used only as the final step after an independent sparsification argument. No fitted parameter is relabeled as a prediction, and no object is defined in terms of the target conclusion. The one notable caveat is Lemma 3.3, imported without proof from Ding, Gao, Liu, Luan, Sun (arXiv:2411.12659) and used to upgrade (c,t)-sparsity to (1-epsilon, beta t)-sparsity in Lemma 3.4. This lemma is genuinely load-bearing: if it failed, the local sparsity estimate |S_a| < t0 and the rich-set deletion in Claim 3.5 would collapse, breaking Lemma 3.4 and hence Theorem 1.12. That is a completeness and correctness risk, not circularity, because the lemma is external to the paper and not derived from the paper's own conclusions. Accordingly, the circularity score is low: there is no significant circularity, though the proof is not fully self-contained at one external-support step.

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

The paper has no fitted constants and no invented physical entities. It relies on external theorems for weak degree-boundedness and density-EH properties; the most fragile imported item is Lemma 3.3 from a preprint.

assumptions (8)
  • standard math Kühn-Osthus theorem: K_{s,s}-free graphs with no induced subdivisions of a fixed H have O(n) edges
    Used in Sections 2.1, 2.2, 4.2 to establish weak degree-boundedness of string graphs, point-halfspace incidence graphs, and pseudo-disk graphs.
  • standard math Theorem 3.8 (Du, Hunter, Girão, McCarty, Scott): every K_{s,s}-free graph with average degree at least k C0 s^3 has a C4-free induced subgraph of average degree k
    Black box in final step of Lemma 3.1.
  • domain assumption Lemma 3.3 from Ding, Gao, Liu, Luan, Sun: (c,t)-sparse graphs avoiding induced bipartite H are (1-ε,βt)-sparse
    Assumed in Lemma 3.4; not proved here; see red flag.
  • standard math Density-EH property for semialgebraic graphs (Fox-Gromov-Lafforgue-Naor-Pach; Fox-Pach-Sheffer-Suk-Zahl)
    Used as Lemma 2.1 to find bicliques in dense semialgebraic patches.
  • domain assumption Fox-Pach-Tóth Theorem 15: dense intersection graphs of convex sets contain large bicliques
    Used in Theorem 2.8(iii).
  • standard math Chan-Har-Peled point-box Zarankiewicz bound
    Used at the end of Proposition 5.1.
  • standard math Lovász-Szegedy ultra-strong regularity lemma
    Used in Lemma 6.1.
  • domain assumption Ackerman-Keszegh double-cherry avoidance in curve visibility graphs
    Used in Lemma 6.7.

how reviews work

0 comments
Cite this review

Pith. "Pith review of $C_4$-free subgraphs of high degree with geometric applications." pith.science (2026). https://pith.science/paper/NQIPSHXA

@misc{pith2026250623942,
  author       = {Pith},
  title        = {Pith review of: $C_4$-free subgraphs of high degree with geometric applications},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NQIPSHXA}},
  note         = {Machine review of arXiv:2506.23942}
}
abstract

The Zarankiewicz problem, a cornerstone problem in extremal graph theory, asks for the maximum number of edges in an $n$-vertex graph that does not contain the complete bipartite graph $K_{s,s}$. While the problem remains widely open in the case of general graphs, the past two decades have seen significant progress on this problem for various restricted graph classes -- particularly those arising from geometric settings -- leading to a deeper understanding of their structure. In this paper, we develop a new structural tool for addressing Zarankiewicz-type problems. More specifically, we show that for any positive integer $k$, every graph with average degree $d$ either contains an induced $C_4$-free subgraph with average degree at least $k$, or it contains a $d$-vertex subgraph with $\Omega_k(d^2)$ edges. As an application of this dichotomy, we propose a unified approach to a large number of Zarankiewicz-type problems in geometry, obtaining optimal bounds in each case.

Figures

Figures reproduced from arXiv: 2506.23942 by the authors.

Figure 1
Figure 1. Illustration of a ladder • I is disjoint from a1 ∪ a2, except at endpoints, and • I intersects at least c 12k n distinct curves from A. In what follows, we fix a pair of curves (a1, a2) and index j. Let Bgood be the set of j-good curves with respect to (a1, a2). If b ∈ Bgood, we denote by I(b) the subcurve I, by p(b) the point p, and by q(b) the point q. We introduce the final definition needed for the proof. For a … view at source ↗
Figure 2
Figure 2. Illustration of the regions Si defined in the proof of Theorem 1.2. Hence, there exists an index 1 < q < s such that xq ∈ b2i+1 and xq+1 ∈ b2i−1 ∪ b2i+3. Without loss of generality, assume that xq+1 ∈ b2i−1, the other case can be handled similarly. Then the subcurve of a between xq and xq+1 is contained in Si , and it intersects every element of B2i . Here, we are using that a1 intersects the elements of B2i positiv… view at source ↗
Figure 5
Figure 5. Decomposition of a trapezoid into a parallelogram and a triangle only constantly many new hyperplanes to H. Furthermore, a parallelotope in R d is a polytope which can be obtained from a unit cube by a nondegenerate affine map. Equivalently, P ⊆ R d is a parallelotope if it has 2 d vertices of the form {x + P i∈I vi |I ⊆ [d]}, for some x, v1, . . . , vd ∈ R d , where v1, . . . , vd are linearly independent. To simpl… view at source ↗
Figures from the paper (7 more)
Figure 6
Figure 6. Figure 6: Step 2: Illustration of a slanted prism with [PITH_FULL_IMAGE:figures/full_fig_p026_6.png]
Figure 7
Figure 7. Figure 7: Cutting the slanted prism using a hyperplane H (highlighted in green), which is spanned by v − 1 , v+ 2 and passes through x +. The top cell contains a pair of parallel edges, which a highlighted in red. The parallel edges of the bottom cell are highlighted in blue. Le…
Figure 8
Figure 8. Figure 8: Decomposing a slanted prism in case [PITH_FULL_IMAGE:figures/full_fig_p028_8.png]
Figure 9
Figure 9. Figure 9: A double cherry. The dashed arc indicates a non-edge. [PITH_FULL_IMAGE:figures/full_fig_p032_9.png]
Figure 10
Figure 10. Figure 10: Illustration of proof of Claim 6.10. Let M0 be the member of M in which the 5 unspecified pairs of vertices {i, j} with i ∈ {1, 2, 3}, j ∈ {4, 5, 6} are not edges. Then M0 is a matching. Also, let M1 be the member of M in which {1, 4}, {2, 5}, {3, 6} are not edges, an…
Figure 11
Figure 11. Figure 11: The family M, and ordered bipartite graphs M0, M1, M2. Theorem 6.11. Let G be an n-vertex visibility graph with respect to a star-shaped Jordan curve K. If G is Ks,s-free, then G has O(sn) edges. Proof. Let P ⊂ K be the vertex set of G. Let c ∈ K∗ be a point such that…
Figure 12
Figure 12. Figure 12: Illustration of proof of Claim 6.12. Let M ∈ M be the unique member with {2, 3} being a non-edge. Then M is a matching, and the bipartite complement of M is also a matching. Let F be the family of graphs H which have an ordering such that H does not contain a bipartit…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

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

  1. Nearly tight bounds for induced subdivisions

    math.CO 2026-07 accept novelty 7.0 of 10

    Every K_{s,t}-free graph of average degree Ω(h^{2(s-1)} log^{7(s-1)} h) and every C_{2k}-free graph of average degree Ω(h log^5 h) contains an induced subdivision of K_h, both nearly optimal.

  2. Block structure in boolean matrices of bounded factorization norm

    math.CA 2025-07 conditional novelty 6.0 of 10

    A boolean matrix with gamma-2 norm at most lambda contains a blocky submatrix that covers at least a 1/2^{2^{O(lambda)}} fraction of its 1-entries.

Reference graph

Works this paper leans on

52 extracted references · 46 canonical work pages · cited by 2 Pith papers

  1. [13]

    L. Ding, J. Gao, H. Liu, B. Luan, and S. Sun.Induced even cycles in locally sparse graphs.preprint, arXiv:2411.12659 (2024). 35

    arXiv 2024

  2. [1]

    Ackerman, and B

    E. Ackerman, and B. Keszegh.The Zarankiewicz Problem for Polygon Visibility Graphs.preprint, arXiv:2503.09115 (2025)

    arXiv 2025

  3. [2]

    Alon, and J

    N. Alon, and J. H. Spencer.The probabilistic method.John Wiley & Sons, 2016

    work page 2016

  4. [3]

    Apfelbaum, and M

    R. Apfelbaum, and M. Sharir.Large Complete Bipartite Subgraphs In Incidence Graphs Of Points And Hyperplanes.SIAM Journal on Discrete Mathematics 21.3 (2007), 707–725

    work page 2007

  5. [4]

    Induced Tur\'an problem in bipartite graphs

    M. Axenovich and J. Zimmermann. Induced Turán problem in bipartite graphs . Preprint, arXiv:2401.11296 (2024)

    work page Pith review arXiv 2024

  6. [5]

    Zarankiewicz’s problem for semilinear hypergraphs.Forum Math

    A.Basit, A.Chernikov, S.Starchenko, T.Tao, andC.-M.Tran. Zarankiewicz’s problem for semilinear hypergraphs.Forum Math. Sigma 9 Paper No. e59 (2021), 23

    work page 2021

  7. [6]

    Benzer.On the topology of the genetic fine structure.Proc

    S. Benzer.On the topology of the genetic fine structure.Proc. Nat. Acad. Sci. 45 (1959), 1607–1620

    work page 1959

  8. [7]

    Bourneuf, M

    R. Bourneuf, M. Bucić, L. Cook, and J. Davies.On polynomial degree-boundedness.Advances in Combinatorics 5 (2024), 16pp

    work page 2024

Show all 52 references
  1. [8]

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

    2023

  2. [9]

    T. M. Chan, C. Keller, and S. Smorodinsky.On Zarankiewicz’s Problem for Intersection Hypergraphs of Geometric Objects. Preprint, arXiv:2412.06490 (2024)

    2024 arXiv

  3. [10]

    Chazelle

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

    1990

  4. [11]

    Chekuri, K

    C. Chekuri, K. Clarkson, and S. Har-Peled.On the set multi-cover problem in geometric settings. ACM Trans. Algo., 9(1) (2012), 9

    2012

  5. [12]

    Davies, T

    J. Davies, T. Krawczyk, R. McCarty, and B. Walczak.Coloring polygon visibility graphs and their generalizations. Journal of Combinatorial Theory, Series B, 161 (2023), 268–300

    2023

  6. [14]

    X. Du, A. Girão, Z. Hunter, R. McCarty, and A. Scott.Induced C4-free subgraphs with large average degree.Journal of Combinatorial Theory, Series B, 173 (2025), 305–328

    2025

  7. [15]

    Du and R

    X. Du and R. McCarty.A survey of degree-boundedness.European Journal of Combinatorics (2024)

    2024

  8. [16]

    Ehrlich, S

    G. Ehrlich, S. Even, and R. E. Tarjan. Intersection graphs of curves in the plane. Journal of Combinatorial Theory, Series B 21 (1976), 8–20

    1976

  9. [17]

    J. Fox, M. Gromov, V. Lafforgue, A. Naor, and J. Pach.Overlap properties of geometric expanders. J. Reine Angew. Math. (Crelle’s Journal), 671 (2012), 49–83

    2012

  10. [18]

    J. Fox, R. Nenadov, T. Pham.The largest subgraph without a forbidden induced subgraph.preprint, arXiv:2405.05902, (2024)

    2024 arXiv

  11. [19]

    Fox, and J

    J. Fox, and J. Pach.Separator theorems and Turan-type results for planar intersection graphs.Adv. Math. 219 (2008), 1070–1080

    2008

  12. [20]

    Fox, and J

    J. Fox, and J. Pach.A Separator Theorem for String Graphs and its Applications.Comb. Prob. Comp. 19 (2010), 371–390

    2010

  13. [21]

    Fox, and J

    J. Fox, and J. Pach.String graphs and incomparability graphs.Adv. Math. 230 (2012), 1381–1401

    2012

  14. [22]

    Fox, and J

    J. Fox, and J. Pach. Applications of a new separator theorem for string graphs.Combinatorics, Probability and Computing, 23(1) (2014), 66–74

    2014

  15. [23]

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

    2017

  16. [24]

    J. Fox, J. Pach, and A. Suk.A structure theorem for pseudo-segments and its applications.preprint arXiv:2312.01028 (2023)

    2023 arXiv

  17. [25]

    J. Fox, J. Pach, and C. D. Tóth.Turán-type results for partial orders and intersection graphs of convex sets.Israel Journal of Mathematics, 178 (1) (2010), 29–50

    2010

  18. [26]

    J. Fox, J. Pach, and C. D. Tóth.Intersection patterns of curves.J. Lond. Math. Soc. 83 (2011), 389–406

    2011

  19. [27]

    Girão, and Z

    A. Girão, and Z. Hunter.Induced subdivisions inKs,s-free graphs with polynomial average degree. preprint, arXiv:2310.18452, (2023)

    2023 arXiv

  20. [28]

    Glock.A note on dense bipartite induced subgraphs.preprint, arXiv:2006.05101, (2020)

    S. Glock.A note on dense bipartite induced subgraphs.preprint, arXiv:2006.05101, (2020)

    2020 arXiv

  21. [29]

    Hunter, A

    Z. Hunter, A. Milojević, B. Sudakov, I. Tomon.Kővári-Sós-Turán theorem for hereditary families. Journal of Combinatorial Theory, Series B 172 (2025), 168–197

    2025

  22. [30]

    Janzer, C

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

    2024

  23. [31]

    Keller, and S

    C. Keller, and S. Smorodinsky.Zarankiewicz’s problem viaε-t-nets. preprint, arxiv:2311.13662, 2023

    2023 arXiv

  24. [32]

    Keszegh.Coloring intersection hypergraphs of pseudo-disks.In SoCG 2018, pages 52:152:15, 2018

    B. Keszegh.Coloring intersection hypergraphs of pseudo-disks.In SoCG 2018, pages 52:152:15, 2018

    2018

  25. [33]

    Korándi, J

    D. Korándi, J. Pach, and I. Tomon.Large homogeneous submatrices.SIAM J. Discrete Math. 34 (4) (2020), 2532–2552

    2020

  26. [34]

    Kővári, V

    T. Kővári, V. Sós, and P. Turán.On a problem of K. Zarankiewicz.Colloquium Math., 3 (1954), 50–57. 36

    1954

  27. [35]

    Kühn, and D

    D. Kühn, and D. Osthus. Induced subdivisions in Ks,s-free graphs of large average degree. Combinatorica, 24 (2004), 287–304

    2004

  28. [36]

    M. Kwan, S. Letzter, B. Sudakov, and T. Tran.Dense induced bipartite subgraphs in triangle-free graphs. Combinatorica, 40 (2020), 283–305

    2020

  29. [37]

    J. R. Lee.Separators in region intersection graphs.In: 8th Innovations in Theoretical Comp. Sci. Conf. (ITCS 2017), LIPIcs 67 (2017), 1–8

    2017

  30. [38]

    Lovász and B

    L. Lovász and B. Szegedy.Regularity partitions and the topology of graphons.An Irregular Mind, Imre Bárány, József Solymosi, and Gábor Sági editors, Bolyai Society Mathematical Studies 21 (2010), 415–446

    2010

  31. [39]

    Marcus and G

    A. Marcus and G. Tardos.Excluded permutation matrices and the Stanley-Wilf conjecture.Journal of Combinatorial Theory, Ser. A 107 (2004), 153–160

    2004

  32. [40]

    Matoušek.Near-optimal separators in string graphs.Combinatorics, Probability and Computing, 23(1) (2014), 135–139

    J. Matoušek.Near-optimal separators in string graphs.Combinatorics, Probability and Computing, 23(1) (2014), 135–139

    2014

  33. [41]

    McCarty.Dense induced subgraphs of dense bipartite graphs.Siam J

    R. McCarty.Dense induced subgraphs of dense bipartite graphs.Siam J. Disc. Math., 35(2) (2021), 661–667

    2021

  34. [42]

    Milojević, B

    A. Milojević, B. Sudakov, and I. Tomon.Point-hyperplane incidences via extremal graph theory. preprint, arXiv:2401.06670 (2024)

    2024 arXiv

  35. [43]

    Pach and G

    J. Pach and G. Tóth.Recognizing string graphs is decidable.Discrete Comput. Geom. 28 (2002), 593–606

    2002

  36. [44]

    Schaefer and D

    M. Schaefer and D. Štefankovič,Decidability of string graphs.J. Comput. System Sci. 68 (2004), 319–334

    2004

  37. [45]

    Schaefer, E

    M. Schaefer, E. Sedgwick, and D. Štefankovič.Recognizing string graphs in NP.Special issue on STOC2002 (Montreal, QC). J. Comput. System Sci. 67 (2003), 365 – 380

    2003

  38. [46]

    Scott, P

    A. Scott, P. Seymour, and S. Spirkl,Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree.J. Graph Theory, 102(3) (2023), 458–471

    2023

  39. [47]

    Topology of thin film RC-circuits.BellSystemTechnologicalJournal(1966), 1639–1662

    F.W.Sinden. Topology of thin film RC-circuits.BellSystemTechnologicalJournal(1966), 1639–1662

    1966

  40. [48]

    Smorodinsky.A survey of Zarankiewicz problem in geometry.preprint, arXiv:2410.03702, 2024

    S. Smorodinsky.A survey of Zarankiewicz problem in geometry.preprint, arXiv:2410.03702, 2024

    2024 arXiv

  41. [49]

    G. Tardos. Extremal theory of ordered graphs. Proceedings of the International Congress of Mathematics – 2018, Vol. 3 (2018), 3219–3228

    2018

  42. [50]

    I. Tomon. Coloring lines and Delaunay graphs with respect to boxes. Random Structures & Algorithms 64 (2024), 645–662

    2024

  43. [51]

    Tomon, and D

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

    2021

  44. [52]

    Zarankiewicz.Problem P 101.Colloq

    K. Zarankiewicz.Problem P 101.Colloq. Math., 2 (1951), 301. 37

    1951

Pith tools

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