Some remarks on the midrange crossing constant

\'E. Czabarka; I. Singgih; L.A. Sz\'ekely; Zhiyu Wang

arxiv: 1907.00368 · v1 · pith:YZVKUVO4new · submitted 2019-06-30 · 🧮 math.CO

Some remarks on the midrange crossing constant

\'E. Czabarka , I. Singgih , L.A. Sz\'ekely , Zhiyu Wang This is my paper

Pith reviewed 2026-05-25 12:36 UTC · model grok-4.3

classification 🧮 math.CO

keywords midrange crossing constantcrossing numbergeometric graphsrandom drawingsupper boundMoon's theorem

0 comments

The pith

Moon's 1965 result verifies that the midrange crossing constant is at most 8/(9π²)

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

The paper verifies an upper bound of 8/(9π²) on the midrange crossing constant originally stated by Pach and Tóth. It does this with a method based on Moon's 1965 theorem about the expected number of crossings in a random drawing of points on the sphere. Moon's bound is known to be tight in its own setting, which leads the authors to ask whether the midrange crossing constant equals exactly 8/(9π²). A reader would care because the constant controls the typical crossing density for large graphs drawn with random point placements.

Core claim

We verify an upper bound of Pach and Tóth on the midrange crossing constant. Details of their 8/(9π²) upper bound have not been available. Our verification is different from their method and hinges on a result of Moon. As Moon's result is optimal, we raise the question whether the midrange crossing constant is 8/(9π²).

What carries the argument

Moon's 1965 result on the expected number of crossings in a random drawing of a complete graph on the sphere, which supplies the normalized crossing density used to bound the midrange crossing constant.

If this is right

The midrange crossing constant satisfies an upper bound of 8/(9π²)
The new verification rests on Moon's theorem rather than the original Pach-Tóth argument
Because Moon's bound is asymptotically tight, the midrange crossing constant may equal exactly 8/(9π²)
The exact value of the constant remains an open question

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the constant equals 8/(9π²) then random geometric graphs realize the extremal crossing density in the midrange regime
The same Moon-based argument might be adapted to bound other variants of crossing numbers that involve random or average-case drawings
Numerical experiments on large random point sets could provide supporting evidence for or against equality

Load-bearing premise

Moon's 1965 result applies directly and transfers its optimality to the midrange crossing constant in the manner used for the verification.

What would settle it

A family of drawings of graphs on n points whose normalized crossing count exceeds 8/(9π²) + ε for arbitrarily large n would disprove the upper bound.

read the original abstract

We verify an upper bound of Pach and T\'oth [Combinatorica 17(1997), 427-439, Discrete and Computational Geometry 36(2006), 527-552] on the midrange crossing constant. Details of their $\frac{8}{9\pi^2}$ upper bound have not been available. Our verification is different from their method and hinges on a result of Moon [J. Soc. Indust. Appl. Math. 13(1965), 506-510]. As Moon's result is optimal, we raise the question whether the midrange crossing constant is $\frac{8}{9\pi^2}$.

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.

Desk Editor's Note private letter to a colleague

Alternative verification of the Pach-Tóth upper bound via Moon 1965, plus an open question on exactness.

read the letter

This paper verifies the 8/(9π²) upper bound on the midrange crossing constant that Pach and Tóth stated, using a route that goes through Moon's 1965 result instead of the original method. The details of the Pach-Tóth proof were never published, so the alternative check is the useful part here. They also note that Moon's result is optimal in its setting and ask whether the midrange constant equals exactly that number. That question is reasonable to raise once the bound is confirmed by a second route. The paper does the verification cleanly enough on the surface and sticks to established results without adding free parameters or new entities. The soft spot is the mapping step. Moon worked with random points or graphs on the sphere, while the midrange crossing constant sits in a different combinatorial geometry context. The abstract says the argument hinges on Moon, but if the full text does not give an explicit reduction showing the constants match without extra factors or regime shifts, that part needs more detail. A referee would likely ask for that spelled out. The citation pattern is standard and points to the right prior work. This note is mainly for people already tracking crossing number constants in geometric graph theory. A specialist who wants an independent check on the bound or who is thinking about whether it is tight would get something from it. It is narrow enough that it will not change much outside the subfield, but the verification plus the open question is substantive enough to send to peer review rather than desk reject.

Referee Report

1 major / 0 minor

Summary. The manuscript verifies the Pach-Tóth upper bound of 8/(9π²) on the midrange crossing constant via an independent argument that relies on Moon's 1965 result concerning the expected number of crossings in random drawings of complete graphs on the sphere. It notes that Moon's bound is tight and therefore asks whether the midrange crossing constant equals exactly 8/(9π²).

Significance. If the mapping from Moon's spherical model to the midrange crossing constant is rigorous, the paper supplies the first publicly available verification of a bound whose original details were never published and raises a concrete optimality question that could be settled by a matching lower bound construction.

major comments (1)

[abstract / method paragraph] The central verification step (abstract and the paragraph describing the method) asserts that Moon's 1965 result transfers directly to the midrange crossing constant. The precise statement of Moon's theorem that is invoked, together with the explicit reduction showing that the spherical random model yields the midrange quantity without a multiplicative loss or change of asymptotic regime, must be written out; without this derivation the claim that the Pach-Tóth bound is recovered cannot be checked.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the constructive comment on clarifying the transfer from Moon's result. We agree that an explicit derivation is needed for the claim to be verifiable and will incorporate it in the revision.

read point-by-point responses

Referee: [abstract / method paragraph] The central verification step (abstract and the paragraph describing the method) asserts that Moon's 1965 result transfers directly to the midrange crossing constant. The precise statement of Moon's theorem that is invoked, together with the explicit reduction showing that the spherical random model yields the midrange quantity without a multiplicative loss or change of asymptotic regime, must be written out; without this derivation the claim that the Pach-Tóth bound is recovered cannot be checked.

Authors: We agree that the manuscript as submitted does not contain a self-contained derivation of the transfer. Moon's theorem gives the exact leading constant for the expected number of crossings in a uniformly random spherical drawing of K_n. The midrange crossing constant is defined via the infimum over all drawings of the normalized crossing number in the limit. In the revision we will insert the precise statement of Moon's 1965 theorem and then supply the short reduction: the spherical random model can be projected to a drawing in the plane (or used directly) such that the expected normalized crossing number equals the midrange quantity exactly in the leading asymptotic term, with no multiplicative loss and no change of regime. This will make the recovery of the 8/(9π²) bound fully checkable. The optimality question raised in the abstract remains open, as the paper only notes that Moon's bound is tight and does not claim a matching lower bound for the midrange constant. revision: yes

Circularity Check

0 steps flagged

No circularity: verification rests on independent external result from Moon 1965

full rationale

The paper states that its verification of the Pach-Tóth upper bound 'hinges on a result of Moon' (1965) and notes that 'Moon's result is optimal' before raising a question about the midrange crossing constant. Moon is an independent author from 1965; Pach and Tóth are also external. No self-citations appear in the load-bearing step, no fitted parameters are renamed as predictions, and no derivation reduces by construction to the paper's own inputs or ansatz. The chain is self-contained against the cited external benchmark.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on the applicability and optimality of Moon's 1965 result; no free parameters, new entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)

domain assumption Moon's 1965 result is optimal and can be applied to establish the midrange crossing constant bound.
Abstract states that the verification hinges on this result and that it is optimal.

pith-pipeline@v0.9.0 · 5643 in / 1115 out tokens · 39376 ms · 2026-05-25T12:36:40.353676+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages · 4 internal anchors

[1]

On topological graphs with at most four crossings per edge

E. Ackerman, On topological graphs with at most four crossings per edge, arXiv:1509.01932

work page internal anchor Pith review Pith/arXiv arXiv
[2]

Ajtai, V

M. Ajtai, V. Chv´ atal, M. Newborn and E. Szemer´ edi, Crossing- free subgraphs, Annals of Discrete Mathematics 12 (1982) 9–12. SOME REMARKS ON THE MIDRANGE CROSSING CONSTANT 5

work page 1982
[3]

Beyond-Planarity: Density Results for Bipartite Graphs

P. Angelini, M.A. Bekos, M, Kaufmann, M. Pﬁster, T. Ueckerdt, B eyond-planarity: density results for bipartite graphs, arXiv:1712.09855

work page internal anchor Pith review Pith/arXiv arXiv
[4]

Using Block Designs in Crossing Number Bounds

J. Asplund, G. Clark, G. Cochran, ´E. Czabarka, A. Hamm, G. Spencer, L.A. Sz´ ekely, L. Taylor, Z. Wang, Using block designs in crossing number bounds, J. Combin. Designs DOI: 10.1002/jcd.21665, arXiv:1807.03430

work page internal anchor Pith review Pith/arXiv arXiv doi:10.1002/jcd.21665
[5]

Balogh, B

J. Balogh, B. Lidick´ y, G. Salazar, Closing in on Hill’s conjecture, ar Xiv:1711.08958v2

work page arXiv
[6]

Midrange crossing constants for graphs classes

´E. Czabarka, J. Reiswig, L.A. Sz´ ekely, and Z. Wang, Midrange cros sing constants of graph classes, arXiv:1811.08071

work page internal anchor Pith review Pith/arXiv arXiv
[7]

Erd˝ os, R.K

P. Erd˝ os, R.K. Guy, Crossing number problems, American Mathematical Monthly 80, 52–58, (1973)

work page 1973
[8]

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

work page 1983
[9]

Moon, On the distribution of crossings in random complete grap hs

J. Moon, On the distribution of crossings in random complete grap hs. J. Soc. Indust. Appl. Math. 13(1965), 506–510

work page 1965
[10]

J. Pach, J. Spencer, G. T´ oth, New bounds on crossing numbe rs, Discrete & Computational Geometry 24(4), 623–644, (2000)

work page 2000
[11]

Pach, L.A

J. Pach, L.A. Sz´ ekely, Cs.D. T´ oth, G. T´ oth, Note on k-planar crossing numbers, Computational Geometry: Theory and Applications Special Issue in Memoriam Ferran Hurtado. 68(2018), 2–6

work page 2018
[12]

J. Pach, G. T´ oth, Graphs drawn with few crossings per edge, Combinatorica 17 (1997), 427–439

work page 1997
[13]

J. Pach, R. Radoiˇ ciˇ c, G. Tardos, G. T´ oth: Improving theCrossing Lemma by ﬁnding more crossings in sparse graphs, Discrete and Computational Geometry 36, (2006), 527–552

work page 2006
[14]

Schaefer, Crossing Numbers of Graphs , CRC Press, Boca Raton FL, 2017

M. Schaefer, Crossing Numbers of Graphs , CRC Press, Boca Raton FL, 2017

work page 2017
[15]

Sz´ ekely, Tur´ an’s Brick Factory Problem: the Status of t he Conjectures of Zarankiewicz and Hill, Chapter 13 in it Graph Theory—Favorite Conjectures and Open P roblems -1, eds

L.A. Sz´ ekely, Tur´ an’s Brick Factory Problem: the Status of t he Conjectures of Zarankiewicz and Hill, Chapter 13 in it Graph Theory—Favorite Conjectures and Open P roblems -1, eds. R. Gera, S. Hedetniemi, C. Larson, Problem Books in Mathematics series, Spring er-Verlag, 2016, 211–230. ´Eva Czabarka, Department of Mathematics, University of Sou th Caro...

work page 2016

[1] [1]

On topological graphs with at most four crossings per edge

E. Ackerman, On topological graphs with at most four crossings per edge, arXiv:1509.01932

work page internal anchor Pith review Pith/arXiv arXiv

[2] [2]

Ajtai, V

M. Ajtai, V. Chv´ atal, M. Newborn and E. Szemer´ edi, Crossing- free subgraphs, Annals of Discrete Mathematics 12 (1982) 9–12. SOME REMARKS ON THE MIDRANGE CROSSING CONSTANT 5

work page 1982

[3] [3]

Beyond-Planarity: Density Results for Bipartite Graphs

P. Angelini, M.A. Bekos, M, Kaufmann, M. Pﬁster, T. Ueckerdt, B eyond-planarity: density results for bipartite graphs, arXiv:1712.09855

work page internal anchor Pith review Pith/arXiv arXiv

[4] [4]

Using Block Designs in Crossing Number Bounds

J. Asplund, G. Clark, G. Cochran, ´E. Czabarka, A. Hamm, G. Spencer, L.A. Sz´ ekely, L. Taylor, Z. Wang, Using block designs in crossing number bounds, J. Combin. Designs DOI: 10.1002/jcd.21665, arXiv:1807.03430

work page internal anchor Pith review Pith/arXiv arXiv doi:10.1002/jcd.21665

[5] [5]

Balogh, B

J. Balogh, B. Lidick´ y, G. Salazar, Closing in on Hill’s conjecture, ar Xiv:1711.08958v2

work page arXiv

[6] [6]

Midrange crossing constants for graphs classes

´E. Czabarka, J. Reiswig, L.A. Sz´ ekely, and Z. Wang, Midrange cros sing constants of graph classes, arXiv:1811.08071

work page internal anchor Pith review Pith/arXiv arXiv

[7] [7]

Erd˝ os, R.K

P. Erd˝ os, R.K. Guy, Crossing number problems, American Mathematical Monthly 80, 52–58, (1973)

work page 1973

[8] [8]

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

work page 1983

[9] [9]

Moon, On the distribution of crossings in random complete grap hs

J. Moon, On the distribution of crossings in random complete grap hs. J. Soc. Indust. Appl. Math. 13(1965), 506–510

work page 1965

[10] [10]

J. Pach, J. Spencer, G. T´ oth, New bounds on crossing numbe rs, Discrete & Computational Geometry 24(4), 623–644, (2000)

work page 2000

[11] [11]

Pach, L.A

J. Pach, L.A. Sz´ ekely, Cs.D. T´ oth, G. T´ oth, Note on k-planar crossing numbers, Computational Geometry: Theory and Applications Special Issue in Memoriam Ferran Hurtado. 68(2018), 2–6

work page 2018

[12] [12]

J. Pach, G. T´ oth, Graphs drawn with few crossings per edge, Combinatorica 17 (1997), 427–439

work page 1997

[13] [13]

J. Pach, R. Radoiˇ ciˇ c, G. Tardos, G. T´ oth: Improving theCrossing Lemma by ﬁnding more crossings in sparse graphs, Discrete and Computational Geometry 36, (2006), 527–552

work page 2006

[14] [14]

Schaefer, Crossing Numbers of Graphs , CRC Press, Boca Raton FL, 2017

M. Schaefer, Crossing Numbers of Graphs , CRC Press, Boca Raton FL, 2017

work page 2017

[15] [15]

Sz´ ekely, Tur´ an’s Brick Factory Problem: the Status of t he Conjectures of Zarankiewicz and Hill, Chapter 13 in it Graph Theory—Favorite Conjectures and Open P roblems -1, eds

L.A. Sz´ ekely, Tur´ an’s Brick Factory Problem: the Status of t he Conjectures of Zarankiewicz and Hill, Chapter 13 in it Graph Theory—Favorite Conjectures and Open P roblems -1, eds. R. Gera, S. Hedetniemi, C. Larson, Problem Books in Mathematics series, Spring er-Verlag, 2016, 211–230. ´Eva Czabarka, Department of Mathematics, University of Sou th Caro...

work page 2016