Pith. sign in

REVIEW 1 major objections 4 minor 17 references

On a conjecture of Pach-Spencer-T\'oth for graph crossing numbers

T0 review · 1 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash

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

Pith's one-line read A 25-year-old conjecture on graph crossing numbers is proved: every graph whose subgraphs satisfy the density bound $e(H) \le A n(H)^{1+\alpha}$ and has $e \ge c n$ edges has crossing number at least $c' e^{2+1/\alpha}/n^{1+1/\alpha}$.

desk verdict Main theorem settles the Pach-Spencer-Tóth conjecture with a sound refinement of existing methods; the secondary theorem is also correct, and the alleged grid-counting flaw is a misreading. read the letter →

arxiv 2502.02301 v1 pith:R4XD5XZ2 submitted 2025-02-04 math.CO

Kaizhe Chen , Jie Ma This is my paper · ORCID
classification math.CO MSC 05C1005C35
keywords crossingnumberbisectionwidthPach-Spencer-Tóthconjecturemonotonegraphpropertiesdegreesequencemomentsdrawingsextremaltheory
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 proves the Pach–Spencer–Tóth conjecture: every $n$-vertex graph $G$ with $e$ edges whose subgraphs $H$ all satisfy $e(H) \le A\,n(H)^{1+\alpha}$ and whose edge count is at least $c n$ has crossing number $\mathrm{cr}(G) \ge c' e^{2+1/\alpha}/n^{1+1/\alpha}$, with $c,c'$ depending only on $A$ and $\alpha$. This removes the extra $\log n$ factor from the original 2000 bound and makes the lower bound optimal for all monotone graph families at linear edge density. The same proof technique settles a related question of Pach and Tóth: the bisection width of a graph is controlled by $\sqrt{\mathrm{cr}(G)}$ plus the $\ell^t$-norm of its degree sequence exactly when $0

What carries the argument

The workhorse is a recursive bisection algorithm that, starting from a graph whose maximum degree has been capped at $d=2e/n$ by local vertex splitting, repeatedly cuts every component with more than $(2/3)^i N$ vertices into two parts by deleting its bisection-width number of edges. The critical external ingredient is the inequality $b(G) \le 6.32\sqrt{\mathrm{cr}(G)} + 1.58\sqrt{\sum d_i^2}$ of Pach–Shahrokhi–Szegedy and Sýkora–Vrt'o, which is applied to every cut component; the square roots are summed via Cauchy–Schwarz, and the constants in (18) are chosen so the total deleted edges stays below $e/2$. For Theorem 1.5 the key step is Jensen's inequality applied to the convex function $x^{2/t}$, which shows the $\ell^2$ norm of the degree sequence is bounded by the $\ell^t$ norm for $t\le 2$; the planar grid graph supplies the matching counterexample for $t>2$.

What would settle it

The theorem would collapse if one found a family of graphs satisfying $e(H) \le A n(H)^{1+\alpha}$ for all subgraphs and $e \ge c n$, but with $\mathrm{cr}(G)$ smaller than $c' e^{2+1/\alpha}/n^{1+1/\alpha}$ by a factor tending to infinity; a direct way to search is to compute the crossing numbers of known extremal graphs for even-cycle-free or $K_{s,t}$-free families and compare them with the claimed bound.

Watch

Extended reading notes

Core claim

The central result, Theorem 1.2, resolves Conjecture 1.1: under the subgraph density condition (2), the crossing number lower bound $\mathrm{cr}(G) \ge c' e^{2+1/\alpha}/n^{1+1/\alpha}$ holds as soon as $e \ge cn$, where the constants depend only on $A$ and $\alpha$. The proof is by contradiction: assuming a drawing with fewer crossings than the bound, the authors split high-degree vertices so every degree is at most $2e/n$ without increasing the crossing number, then run a recursive bisection algorithm on the resulting graph. At each step they delete the bisection width of each large component; the total deleted edges is bounded by $6.32$ times the square root of the crossing sum plus $1.58$ times the square root of the sum of squared degrees, using inequality (4). They tune the constants $c$ and $c'$ (given explicitly in (18)) so that fewer than $e/2$ edges are deleted, while the remaining subgraph has fewer than $e/2$ edges by the density hypothesis—a contradiction. The same section proves Theorem 1.5, which answers Pach and Tóth's Problem 1.4: inequality (5) holds for all graphs precisely when $0<t\le 2$, with planar grid graphs showing failure for $t>2$, and Theorem 1.6, which converts small crossing numbers of all large subgraphs into a sparsity bound.

Load-bearing premise

The proof depends on the quoted bisection-width inequality $b(G) \le 6.32\sqrt{\mathrm{cr}(G)} + 1.58\sqrt{\sum d_i^2}$ with its exact numerical coefficients, and on the step that replaces each high-degree vertex by a cluster of smaller-degree vertices without introducing any new crossings; if either premise fails, the deletion count is no longer forced below $e/2$.

Editorial extensions

If this is right

  • For graphs with no even cycle of length $2k$, the lower bound $\mathrm{cr}(G) \ge c' e^{2+k}/n^{1+k}$ now holds for every $k\ge 2$ under $e\ge cn$, not just $k=2,3$.
  • Any monotone graph property satisfying the density condition (2) gets an optimal crossing-number lower bound at linear edge density; the earlier extra $\log n$ factor is gone.
  • Bisection width is governed by the second moment of the degree sequence: inequality (5) holds precisely for $0<t\le 2$, with $t=2$ the threshold.
  • The dual theorem gives a crossing-number test for sparsity: if every large subgraph has crossing number at most $e(H)^2/2^{16+3/\alpha}$, then the whole graph has fewer than $A n^{1+\alpha}$ edges.

Reading between the lines

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

  • If unit-distance graphs could be shown to satisfy $\mathrm{cr}(G)=O(e^2/\log\log e)$, Theorem 1.6 would immediately give $e=n^{1+o(1)}$; the paper explicitly points to this application but does not prove the crossing bound.
  • The $t=2$ threshold suggests that the $\ell^2$ norm is the only degree moment that interacts structurally with crossings; the same critical exponent may appear in other separator-type inequalities.
  • The recursive bisection scheme with vertex splitting is largely independent of the specific extremal hypothesis, so it may yield explicit constants for crossing-number lower bounds in other sparse graph families, such as minor-closed or bounded-genus classes.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 4 minor

Summary. The paper proves the Pach–Spencer–Tóth conjecture on crossing numbers for graphs with a monotone subgraph-density bound: if every subgraph H of an n-vertex graph G satisfies e(H) ≤ A n(H)^{1+α} and e(G) ≥ c n, then cr(G) ≥ c' e^{2+1/α}/n^{1+1/α}, with c, c' depending only on A and α. The proof refines the earlier approach of Pach–Spencer–Tóth and Füredi–Kündgen via vertex splitting, recursive bisection, and the Pach–Shahrokhi–Szegedy / Sýkora–Vrt'o bisection-width inequality. The paper also addresses a problem of Pach and Tóth on the relation between bisection width, crossing number, and degree moments, proving that b(G) = O(√cr(G) + (Σ d_i^t)^{1/t}) holds exactly for 0 < t ≤ 2, with matching counterexamples for t > 2. Finally, it proves a dual theorem (Theorem 1.6) converting a crossing-number upper bound for all subgraphs into an edge-density bound.

Significance. If the proof is correct, Theorem 1.2 resolves a conjecture that has been open for over 25 years, and the bound is known to be tight up to constant factors. The proof of Theorem 1.2 is honest and explicit: the constants c and c' are given, there are no fitted parameters, and the argument is self-contained apart from standard external theorems. I also checked the disputed counting step in the proof of Theorem 1.5: the concern that a non-full column might lie entirely in V2 does not apply, because the case assumption provides a full row contained in V1, so every non-full column contains both a V1 vertex (on that row) and a V2 vertex, and therefore contains a boundary edge. Thus the lower bound b(G) ≥ n/3 is valid as written. The main defect I find is in the proof of the secondary Theorem 1.6, where the explicit choice of the constant A does not appear to satisfy the inequality that the proof requires. This is local and repairable, but it is load-bearing for that theorem.

major comments (1)
  1. [Section 3, proof of Theorem 1.6] The proof needs the chain A^{1+α} n ≥ (88)^2 α^{2α+3} A n = c n to guarantee e ≥ c n, which requires A^α ≥ (88)^2 α^{2α+3}. The displayed choice A = max{88^2 2^{1+3/α}, N} does not satisfy this for all α: for example, with α = 200, A^200 is far smaller than (88)^2 · 200^{403}. Since α is unrestricted in the theorem, the proof as printed has a gap. This does not affect Theorem 1.2 or Theorem 1.5, and it is easily repaired by choosing A = max{N, (88)^2 α^{2α+3}} (or any A with A^α ≥ (88)^2 α^{2α+3}), but the correction should be made explicitly.
minor comments (4)
  1. [Theorem 1.5, proof for t > 2] The notation is confusing: the grid graph has n^2 vertices, while the theorem statement uses n for the number of vertices. The proof works, but it should either state the example with m = n^2 vertices or explicitly say that n denotes the grid side length.
  2. [Section 3, proof of Theorem 1.6] The phrase 'minimum counterexample' should specify 'minimum by number of edges', since the argument uses e−1 ≤ A n^{1+α} after deleting one edge from G.
  3. [Several displayed equations in Section 3] There are apparent typographical artifacts: for example, the degree-sum estimate and the final constant bounds appear to be missing fraction bars and superscripts, so expressions like 2e√n and 45√(...)e^2 should be checked carefully against the intended 2e/√n and 45√(...)e.
  4. [Throughout] Please proofread for small language slips such as 'without losing generality', and ensure the figures and references are correctly formatted.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: Theorem 1.2 is derived from external results (bisection-width inequality (4) and Bondy-Simonovits), with no fitted input called a prediction and no load-bearing self-citation.

full rationale

The derivation chain is self-contained against external theorems. Theorem 1.2 is proved by contradiction: it assumes e ≥ cn and cr(G) < c' e^{2+1/α}/n^{1+1/α}, splits high-degree vertices without increasing crossings, runs a recursive bisection algorithm, and bounds the total deleted edges using the external inequality (4) of Pach, Shahrokhi, Szegedy and of Sýkora and Vrt'o. The constants c and c' are then chosen algebraically so that each term in the final bound is at most e/4; they are not fitted to any target graph or to the desired conclusion. The sparse subgraph condition e(H) ≤ A n(H)^{1+α} is the hypothesis of the theorem, not an output of the proof, and the proof of the bound e(G^k) < e/2 uses only that hypothesis together with standard counting and Cauchy-Schwarz estimates. Corollary 1.3 relies on the external Bondy-Simonovits theorem. Theorem 1.5 uses the same external inequality (4) plus Jensen's inequality for the t ≤ 2 case and an explicit grid construction for t > 2; no claim is reduced to its own input. Theorem 1.6 applies the already-proved Theorem 1.2 in a contradiction argument, which is a legitimate internal use rather than circularity. There are no self-citations that carry any load-bearing argument: the cited work [11] is the conjecture being resolved, not a substitute for the proof. Although the paper contains a genuine correctness concern in the t > 2 case of Theorem 1.5 (the grid-row argument as written is flawed but repairable), that issue is independent of circularity and does not affect the central Theorem 1.2. Overall, the paper's predictions and theorems are derived from stated external results and explicit constructions, so no circular step is present.

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

No parameters are fitted to data; A and α are inputs of the theorem. The central claim rests on external theorems, the most important being the bisection-width inequality (4).

assumptions (4)
  • domain assumption Pach-Shahrokhi-Szegedy and Sýkora-Vrt'o inequality: b(G) ≤ 6.32√cr(G) + 1.58√(Σ d_i^2).
    External theorem stated as Eq. (4); the decomposition algorithm in Theorem 1.2 uses it to bound the number of deleted edges, and the numerical constants flow into the choice of c and c'.
  • standard math Bondy-Simonovits bound: every C_{2k}-free n-vertex graph has at most 100k n^{1+1/k} edges.
    Used in Corollary 1.3 to convert the alpha = 1/k sparsity condition into the crossing-number bound for C_{2k}-free graphs.
  • standard math Standard properties of crossing number: existence of an optimal drawing with no three edges sharing an interior point, and the vertex-splitting operation can be performed without increasing crossings.
    Invoked in Section 3 to construct G' with max degree at most 2e/n while preserving e(G')=e and cr(G')≤cr(G).
  • standard math Jensen's inequality for convex functions.
    Used in the proof of Theorem 1.5 to deduce (Σ d_i^2)^{1/2} ≤ (Σ d_i^t)^{1/t} for t≤2.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On a conjecture of Pach-Spencer-T\'oth for graph crossing numbers." pith.science (2026). https://pith.science/paper/R4XD5XZ2

@misc{pith2026250202301,
  author       = {Pith},
  title        = {Pith review of: On a conjecture of Pach-Spencer-T\'oth for graph crossing numbers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/R4XD5XZ2}},
  note         = {Machine review of arXiv:2502.02301}
}
abstract

The crossing number of a graph $G$ denotes the minimum number of crossings in any planar drawing of $G$. In this short note, we confirm a long-standing conjecture posed by Pach, Spencer, and T\'oth over 25 years ago, establishing an optimal lower bound on the crossing number of graphs that satisfy some monotone properties. Furthermore, we address a related open problem introduced by Pach and T\'oth in 2000, which explores the interplay between the crossing number of a graph, its degree sequence, and its bisection width.

Figures

Figures reproduced from arXiv: 2502.02301 by the authors.

Figure 1
Figure 1. A drawing of G with n = 5 four. We claim that b(G) ≥ n/3. Indeed, let V (G) = V1 ∪ V2 be any partition of V (G) such that |V1|, |V2| ≥ n 2/3. It suffices to prove that |E(V1, V2)| ≥ n/3. Suppose that there is an i0 ∈ [n] such that (i0, j) ∈ V1 for every j ∈ [n]. Since |V1| ≤ 2n 2/3, there are at most 2n/3 number of j such that (i, j) ∈ V1 for every i ∈ [n]. Thus, there are at least n/3 columns containing at least on… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 16 canonical work pages

  1. [1]

    Ackerman, On topological graphs with at most four crossings per edge, Computa- tional Geometry 85 (2019), 35 pages

    E. Ackerman, On topological graphs with at most four crossings per edge, Computa- tional Geometry 85 (2019), 35 pages

    work page 2019

  2. [2]

    Ajtai, V

    M. Ajtai, V. Chvátal, M. Newborn and E. Szemerédi, Crossing-free subgraphs, The- ory and Practice of Combinatorics, Mathematical Studies, Vol. 60, North-Holland, Amsterdam (1982), 9-12

    work page 1982

  3. [3]

    J. A. Bondy and M. Simonovits, Cycles of even length in graphs, J. Combin. Theory Ser. B 16 (1974), 97-105

    work page 1974

  4. [4]

    F¨ uredi and A

    Z. F¨ uredi and A. K¨ undgen, Moments of graphs in monotone families, J. Graph Theory 57 (2006), 37-48. 9

    work page 2006

  5. [5]

    Garey and D

    M. Garey and D. Johnson, Crossing number is NP-complete, SIAM Journal on Alge- braic and Discrete Methods 4 (1983), 312-316

    work page 1983

  6. [6]

    F. T. Leighton, Complexity Issues in VLSI, MIT Press, Cambridge, MA, 1983

    work page 1983

  7. [7]

    F. T. Leighton, New lower bound techniques for VLSI, Math. Systems Theory 17 (1984), 47-70

    work page 1984

  8. [8]

    Lipton and R

    R. Lipton and R. Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math., 36 (1979), 177-189

    work page 1979

Show all 17 references
  1. [9]

    Matousek, Lectures on discrete geometry (Vol

    J. Matousek, Lectures on discrete geometry (Vol. 212), Springer Science& Business Media (2013)

    2013

  2. [10]

    J. Pach, F. Shahrokhi and M. Szegedy, Applications of the crossing number, Algorith- mica 16 (1996), 111-117

    1996

  3. [11]

    J. Pach, J. Spencer and G. Tóth, New bounds on crossing numbers, ACM Symposium on Computational Geometry (Miami, 1999), Discrete Comput. Geom. 24 (2000), 623- 644

    2000

  4. [12]

    Pach and G

    J. Pach and G. Tóth, Graphs drawn with few crossings per edge, Combinatorica 17 (1997), 427-439

    1997

  5. [13]

    Pach and G

    J. Pach and G. Tóth, Thirteen problems on crossing numbers, Geombinatorics, 9 (2000), 194-207

    2000

  6. [14]

    R. B. Richter and G. Salazar, Crossing numbers, Topics in topological graph theory 128 (2009), 133-150

    2009

  7. [15]

    Schaefer, The Graph Crossing Number and its Variants: A Survey, the Electronic Journal of Combinatorics (2024), #DS21

    M. Schaefer, The Graph Crossing Number and its Variants: A Survey, the Electronic Journal of Combinatorics (2024), #DS21. (DOI: https://doi.org/10.37236/2713)

    2024 doi

  8. [16]

    L. A. Székely, Crossing numbers and hard Erdős problems in discrete geometry, Com- bin. Probab. Comput. 6 (1998), 353-358

    1998

  9. [17]

    Sýkora and I

    O. Sýkora and I. Vrt’o, On VLSI layouts of the star graph and related networks, Integration, 17 (1994), 83-93. 10

    1994

Pith tools

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