{"id":"4ca56a77-f308-4b4c-8c9f-942896da943a","arxiv_id":"2502.02301","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The Pach-Spencer-Tóth conjecture on optimal crossing lower bounds for graphs with sparse subgraphs is proved, and the admissible degree-sum range for the bisection-width bound is fully determined.","lead":"This paper proves an optimal crossing-number lower bound for graphs whose subgraphs are sparse, confirming a 25-year-old conjecture by Pach, Spencer and Tóth. It also settles a related open problem on the relation between crossing number, degree sums, and bisection width.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection to Theorem 1.2; proof is coherent. Secondary Theorem 1.5 grid counting is flawed but repairable.","rationale":"The reader's weakest_assumption identified the external inequality (4) and the vertex-splitting operation as load-bearing for Theorem 1.2. In my reading, these are not flaws: (4) is a cited theorem and the proof only needs some constants, so even if the numerical coefficients differed slightly, the final constants c and c' could be adjusted; the vertex-splitting is a standard operation that does not increase crossings, and the subsequent pre-image counting is valid. The proof of Theorem 1.2 appears sound, and I can find no internal gap in its central argument. The actual issue in the paper is the secondary Theorem 1.5 grid-counting proof, which is invalid as written but easily repairable; the theorem itself is true. This matches the reader's conditional verdict, so the verdict should remain unchanged. I disagree with the reader's framing of the weakest assumption: the dependency on (4) is not the soft spot; the soft spot is the grid argument in Theorem 1.5.","tokens_in":7611,"tokens_out":31324,"duration_ms":262063,"concrete_test":"Verify the final constant choices in (18) by recomputing the two terms in the bound for the total deleted edges σ with the stated c and c'. If either term exceeds e/4 for any α>0, the proof would need adjusted constants; if both stay below e/4, Theorem 1.2 closes. Separately, for Theorem 1.5, re-prove b(G) ≥ n/3 for the n x n grid using the standard edge-isoperimetric inequality or by a direct case analysis of rows and columns with both V1 and V2 vertices.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified for the central claim, Theorem 1.2. The proof is internally consistent: the vertex-splitting operation is standard and does not increase crossings; the recursive bisection, Cauchy-Schwarz estimates, and the pre-image counting all close correctly; and the final constants c and c' satisfy the required inequalities with margin. The reliance on the external inequality (4) is a legitimate citation, not a logical gap, and the proof only needs some universal constants, so minor numerical changes would not break it. The only genuine defect in the paper is in the secondary Theorem 1.5 (t>2 case): the grid bisection lower bound argument is invalid. Specifically, from 'at most 2n/3 full rows in V1' the paper concludes 'at least n/3 columns containing an edge in E(V1,V2),' but rows not full in V1 could be entirely in V2. The lower bound itself is true and easily repairable via a standard isoperimetric argument, but the text as written needs correction. This flaw does not bear on Theorem 1.2.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":7743,"tokens_out":34996,"duration_ms":291736,"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":[{"comment":"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.","section":"Section 3, proof of Theorem 1.6"}],"minor_comments":[{"comment":"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.","section":"Theorem 1.5, proof for t > 2"},{"comment":"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.","section":"Section 3, proof of Theorem 1.6"},{"comment":"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.","section":"Several displayed equations in Section 3"},{"comment":"Please proofread for small language slips such as 'without losing generality', and ensure the figures and references are correctly formatted.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The main conjecture is resolved convincingly, and the proof of Theorem 1.2 appears sound; the same is true of Theorem 1.5 once the nomenclature is clarified. The only substantive gap is the constant choice in the proof of Theorem 1.6, which is local and should be corrected. If the authors fix that point, the paper would be a strong contribution to the crossing-number literature."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things. First, the main result, Theorem 1.2, confirms the Pach-Spencer-Tóth conjecture in full: under the monotone subgraph-sparsity condition (2), the crossing-number lower bound holds as soon as e ≥ cn, with no logarithmic factor. The proof is a careful refinement of the PST and Füredi-Kündgen machinery: vertex splitting to cap degrees, recursive bisection using the Pach-Shahrokhi-Szegedy / Sýkora-Vrt'o inequality (4), and a clean pre-image counting argument. I went through the constant chasing and it closes; the choices in (18) work. Corollary 1.3 (C_{2k}-free graphs) follows immediately from Bondy-Simonovits. This is a genuine resolution of a 25-year-old conjecture, and the proof is coherent.\n\nSecond, the alleged flaw in Theorem 1.5 is not there. The stress-test note claims the grid bisection proof counts non-full rows, but the text actually counts non-full columns. The assumption that some row is entirely in V1 ensures every column has at least one V1 vertex. If a column is not full, it also has a V2 vertex, so along that column path there must be an edge crossing between the two sets. Thus at least n/3 edges cross. The t>2 counterexample stands, and the 02$.","core_discovery":"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 $02$, and Theorem 1.6, which converts small crossing numbers of all large subgraphs into a sparsity bound.","pith_inferences":["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."],"forward_implications":["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