REVIEW 2 major objections 3 minor 6 references
On the Simple Quasi Crossing Number of $K_{11}$
T0 review · 2 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read The simple quasi crossing number of $K_{11}$ is exactly 4, making $K_{11}$ the smallest complete graph that is not simple quasi-planar.
desk verdict The lower bound cr3(K11) ≥ 4 is sound, but the claimed equality rests entirely on a missing figure; the probabilistic add-on also has a fixable gap. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The carrier of the proof is the quantity $\operatorname{cr}_3(G)$, the minimum number of triples of pairwise crossing edges over all simple drawings of $G$. For the lower bound, the paper combines the extremal fact that any simple quasi-planar graph on $n$ vertices has at most $6.5n-20$ edges with a probabilistic argument: sample vertices independently with probability $p = \alpha n/e$, take expectations, and optimize $\alpha$. This yields $\operatorname{cr}_3(G) \ge \frac{\alpha-6.5}{\alpha^5}\frac{e^5}{n^4} + \frac{20}{\alpha^6}\frac{e^6}{n^6}$ for graphs with $e\ge \alpha n$, and the maximizing choice $\alpha=8.125$ gives $\operatorname{cr}_3(K_{11})\ge 3.5$, hence at least $4$. The upper bound is a single drawing in which the marked triples are claimed to be the only ones.
What would settle it
Make the drawing labeled Figure d explicit by listing the positions of the 11 vertices, compute all pairwise edge crossings, and count the triples of edges whose three pairwise pairs all cross; any count other than exactly four would refute the asserted value.
Extended reading notes
Core claim
The central claim is that $\operatorname{cr}_3(K_{11}) = 4$. A triple of pairwise crossing edges is a set of three edges in which every two meet at an interior point, and a simple drawing lets each pair of edges meet at most once. The paper proves that every simple drawing of $K_{11}$ contains at least four such triples, and it presents a drawing of $K_{11}$ in which the number of such triples is exactly four. Together these settle the value and place the threshold for simple quasi-planarity of complete graphs at $n=11$.
Load-bearing premise
The load-bearing premise is that Figure d, which is mentioned but not described in the text, really is a simple drawing of $K_{11}$ with exactly four triples of pairwise crossing edges; if that figure contains any additional crossing triple, the proposed upper bound fails.
Editorial extensions
If this is right
- For every $n\le 10$, $\operatorname{cr}_3(K_n)=0$, so $K_{11}$ is the smallest complete graph that is not simple quasi-planar.
- Any simple drawing of $K_{11}$, no matter how crossings are arranged, contains at least four triples of pairwise crossing edges.
- The lower-bound inequality applies to every graph with $e\ge 8.125n$, giving an explicit polynomial lower bound on $\operatorname{cr}_3(G)$ in terms of $e$ and $n$.
- The value of $\operatorname{cr}_3(K_{11})$ is now known exactly, so the remaining open case for complete graphs starts at $n=12$.
Reading between the lines
- Extending the paper's inequality (1) to $n=12$ gives $\operatorname{cr}_3(K_{12})\ge 8$; the paper does not state this number.
- If the Figure d drawing is made explicit, inspecting whether its four triples share a structural pattern could suggest the first non-trivial upper-bound constructions for $n\ge 12$; this is a line of inquiry the paper leaves open.
- A natural higher-order analogue would apply the same probabilistic amplification to drawings free of $k+1$ pairwise crossing edges, once the corresponding extremal edge bound is known; the paper does not pursue this.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper defines the simple quasi crossing number cr3(G) as the minimum number of triples of pairwise crossing edges over all simple drawings of G. It combines the Ackerman-Tardos bound of 6.5n−20 edges for simple quasi-planar graphs with a hitting-set argument to derive the lower bound cr3(G) ≥ e−6.5n+20. For K11 this gives cr3(K11) ≥ 3.5, hence at least 4. The paper then asserts, with reference to a figure, that there is a simple drawing of K11 with exactly four such triples, concluding cr3(K11)=4. A probabilistic improvement of the lower bound is also derived and applied to graphs with e≥8.125n, and two open problems are stated.
Significance. If the upper-bound drawing is supplied, the equality cr3(K11)=4 would be a clean, nontrivial exact value that goes beyond the known quasi-planarity of K_n for n≤10, and the lower-bound proof via the Ackerman-Tardos bound is mathematically sound. The lower-bound technique (inequality (1)) is simple and correct. However, as the manuscript stands, no verifiable drawing is provided, so the central equality is not established. The probabilistic improvement (2) is derived incorrectly; although it does not affect the K11 lower bound, it is a substantive error in the paper's general claim.
major comments (2)
- [Upper-bound paragraph ('In the following, we present a drawing...')] The assertion cr3(K11) ≤ 4 is supported only by 'Figure d', which is not present in the manuscript. No vertex coordinates, edge-routing prescription, rotation system, or other data are given from which the drawing can be reconstructed or verified. Since this upper bound is the second half of the equality cr3(K11)=4, the central claim is uncheckable as written. The manuscript must include the drawing (or an explicit combinatorial description) and a verification that it is a simple drawing of K11 containing exactly four triples of pairwise crossing edges.
- [Equation (2), paragraph beginning 'We improve this bound by the probabilistic method'] Inequality (1) is valid only for graphs with at least four vertices, but the derivation of (2) applies it to the random subgraph H without any restriction. For a subgraph with n_H=3 and e_H=1, inequality (1) would give cr3(H) ≥ 1.5, while cr3(H)=0, so the inequality is false for such H. Hence the expectation E[cr3(H)] ≥ E[e_H] − 6.5E[n_H] + 20 is not justified. This does not affect the K11 lower bound, but it invalidates the claimed probabilistic improvement (2) as stated and must be repaired, e.g., by conditioning on n_H≥4 or proving a version valid for all n_H.
minor comments (3)
- [Probabilistic method paragraph] The phrase 'Consider a random subgraph of H obtained by including each vertex of G independently' should read 'random subgraph of G'; as written, H is introduced both as the random subgraph and as the graph being sampled, which is confusing.
- [Figure references] The text and captions repeatedly refer to Figures a-d, but none of these figures appears in the manuscript; even apart from the missing verification of Figure d, the paper should either include all figures or describe the incremental construction in words.
- [First paragraph of the introduction] The references [3,5] are cited for the claim that K_n is simple quasi-planar for n≤10; reference [3] is a point-set order-type database, so it would be helpful to cite a direct source for the graph-drawing claim or to describe the construction.
Circularity Check
No circularity found: the K11 bound is derived from the external Ackerman–Tardos edge bound and an independent drawing, with no fitted input or self-citation chain.
full rationale
The paper's derivation chain is not circular. The lower bound cr3(K11) >= 4 is obtained by applying the external theorem of Ackerman and Tardos, which bounds the number of edges in a simple quasi-planar graph by 6.5n - 20, to the subgraph left after deleting at most one edge per pairwise-crossing triple. Substituting n=11 and e=55 gives 55 - cr3(K11) <= 6.5*11 - 20, hence cr3(K11) >= 3.5, so at least 4 triples are required. No parameter is fitted to the target value, and the target conclusion is not assumed in the argument. The upper bound is asserted by a drawing in Figure d, which is not visible in the provided manuscript and is not described by coordinates or routing rules; however, an unverifiable figure is a correctness or evidence issue, not circular reasoning. The probabilistic inequality (2) may have a technical gap when applied to random subgraphs with fewer than four vertices, but that is also a correctness concern rather than a circularity. There are no load-bearing self-citations, no uniqueness theorem imported from the authors' own prior work, and no ansatz smuggled in via citation. The derivation is self-contained against external benchmarks, so the appropriate circularity score is 0.
Assumptions & free parameters
assumptions (3)
- domain assumption Ackerman-Tardos bound: every simple quasi-planar graph with n >= 4 vertices has at most 6.5n - 20 edges.
- ad hoc to paper The drawing in Figure d is a simple drawing of K11 containing exactly four triples of pairwise crossing edges.
- ad hoc to paper Inequality (1) holds for every random subgraph H in the probabilistic argument.
Cite this review
Pith. "Pith review of On the Simple Quasi Crossing Number of $K_{11}$." pith.science (2026). https://pith.science/paper/HAKKIT6I
@misc{pith2026190807851,
author = {Pith},
title = {Pith review of: On the Simple Quasi Crossing Number of $K_11$},
year = {2026},
howpublished = {\url{https://pith.science/paper/HAKKIT6I}},
note = {Machine review of arXiv:1908.07851}
}
abstract
We show that the simple quasi crossing number of $K_{11}$ is $4$.
Reference graph
Works this paper leans on
-
[1]
E. Ackerman and G. Tardos. On the maximum number of edges in quasi-planar graphs. J. Comb. Theory, Ser. A, 114(3):563–571, 2007
work page 2007
-
[2]
P. K. Agarwal, B. Aronov, J. Pach, R. Pollack, and M. Sharir. Quasi-planar graphs have a linear number of edges. Combinatorica, 17(1):1–9, 1997
1997
-
[3]
O. Aichholzer and H. Krasser. The point set order type data base: A collection of applications and results. In Proc. 13th CCCG, Waterloo, Ontario, Canada, pages 17–20, 2001
work page 2001
- [4]
-
[5]
F. J. Brandenburg. A simple quasi-planar drawing of K10. In Proc. 24th GD, Athens, Greece, pages 603–604, 2016
work page 2016
- [6]
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.