REVIEW 3 major objections 4 minor 23 references
An improved upper bound for the planar Tur\'an number of $C_8$
T0 review · 3 major / 4 minor · reviewed 2026-08-01 · deepseek-v4-flash
Pith's one-line read Every planar graph with no 8-cycle has at most 2.76(n−2) edges.
desk verdict A real improvement on C8 planar Turán: the human-checkable discharging is correct, and the finite-certificate layer is transparent enough that the only open question is independent verification. 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 proof is a discharging argument on the faces of a 2-connected plane graph. Each face starts with charge 2d(f)−4; every face sends α = 50/69 to each incident vertex, and every triangular face receives compensation (4/23)/|N(g)| split equally among its nearest 4+-faces, defining the equal-split load ℓ(f). The load is controlled by six finite certificates: bad-count maxima for small faces, at most six unique-nearest contributors to a 4-face, the dangerous 4-face case, a per-edge load bound of 9/2 for faces of degree at least 9, and an eight-vertex base case. These local bounds force every face to end with nonnegative charge, so Euler's formula gives 4n−8 ≥ 2α e(G), hence e(G) ≤ 69/25 (n−2).
What would settle it
Find a simple planar graph on n vertices with no 8-cycle and more than 69/25(n−2) edges, or exhibit a local rooted configuration that violates one of the certificates: a 4-face with seven triangles for which it is the unique nearest 4+-face, a boundary edge of a face of degree at least 9 carrying load above 9/2, or a planar non-Hamiltonian graph on eight vertices with 17 or 18 edges.
Extended reading notes
Core claim
The central claim is Theorem 1: for every n≥8, the planar Turán number ex_P(n, C8) is at most 69/25 (n−2). In plain terms, any simple planar graph on n vertices that contains no subgraph isomorphic to an 8-cycle has at most 2.76(n−2) edges. This supersedes the earlier bound (323/108)n − 6, which held for n≥27, and extends the bound to all n≥8. The authors are explicit that this is an improvement, not an exact determination: the best known construction still has leading coefficient 21/8 = 2.625, and equality cases are not characterized.
Load-bearing premise
The proof depends on the finite computer searches being exhaustive for every local configuration that can actually occur in a 2-connected, C8-free planar graph with minimum degree 3; the hand-written lifting argument that transfers those enumerated bounds to all such graphs is not machine-checked.
Editorial extensions
If this is right
- For every n≥8, no planar C8-free graph can exceed about 2.76(n−2) edges, improving the previous leading coefficient 323/108 ≈ 2.99 for n≥27.
- The gap between the upper bound 2.76 and the construction lower bound 2.625 remains open; the exact planar Turán number of C8 is not determined by this paper.
- The induction base handles n=8 via the finite fact that every planar graph on eight vertices with 17 or 18 edges is Hamiltonian.
- Degree-8 faces cannot appear in the extremal discharging argument, since an 8-face would itself be an 8-cycle; the bound survives through that exclusion.
Reading between the lines
- If the local certificates could be sharpened, the same discharging scheme might push the coefficient below 2.76, and the natural limit to test is the conjectured 21/8 from the construction.
- The heavy reliance on exhaustive local searches suggests the method could transfer to C9 or longer cycles, but the search space and certificates would grow substantially.
- A possible testable extension: run the same finite search on the dangerous 4-face case with a larger radius to see whether the extra nearest 4+-face can be forced at distance 2 rather than 3, which would improve the four-face load bound from 19/3.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves Theorem 1: every n-vertex simple planar graph with no (not necessarily induced) copy of C_8 has at most (69/25)(n−2) edges for every n ≥ 8. This improves the previous best bound (323/108)n − 6. The proof reduces to the 2-connected, minimum-degree-at-least-3 case by an induction on n, and then applies discharging. Faces receive initial charge 2d−4; each face sends α = 50/69 to each incident vertex; triangular faces are compensated from their nearest 4+-faces according to an equal-split load. The load bounds used in the discharging are ℓ(f) ≤ 19/3 for 4-faces, ℓ(f) ≤ 7,7,5,4 for faces of degree 5,6,7, and ℓ(f) ≤ 9d/2 for d ≥ 9. These bounds are derived from six finite certificates (C1)–(C6), which are asserted in Theorem 2 and verified by exhaustive plane-patch searches described at length in the appendix. The discharging then gives e(G) ≤ (2/α)(n−2) = (69/25)(n−2).
Significance. If the result holds, it is a meaningful improvement in the planar Turán problem for C_8, lowering the upper-bound coefficient from 323/108 ≈ 2.991 to 69/25 = 2.76 and narrowing the gap to the construction with coefficient 21/8 = 2.625. The paper's hand-checkable mathematics is sound: I checked the induction steps, the cut-vertex and low-degree reductions, the base case for n = 8, and the discharging algebra. The coefficients α = 50/69, 4/23, 19/3, and 9d/2 all work out as stated. The finite computations are described in unusual detail for a math paper, with pseudocode, state counts, and certificate-checking claims. The main weakness is not the mathematical framework but the verifiability of the finite certificates: the actual certificate files and code are not included in the manuscript and are only available on a personal homepage, and several load-bearing lifting steps are argued informally rather than machine-checked.
major comments (3)
- [§2, Theorem 2; Data and code availability, p.7] The theorem's central claim depends on the six finite certificates (C1)–(C6). The manuscript reports aggregate maxima and state counts, but the actual certificate files and source code are only available on a personal homepage, without a hash, archive DOI, or versioned repository. For a computer-assisted proof in a journal, this is not reproducible. Please deposit the code, recorded outputs, and machine-readable certificates in a permanent archive (e.g., arXiv ancillary files or Zenodo) with a checksum/DOI, or include the certificate data as supplementary material. Without this, an independent reader cannot verify that the reported maxima (7, 7, 5, 4, 6, 19/3, 9/2) are truly outputs of the described exhaustive searches.
- [A6, Algorithm 5 and Lemma 16] The quantities p_S(g), q_S(g), s_S(g), and λ_S(g) used to certify (C5) are not formally defined. Section 2 defines S_f(g), c_{f,e}(g), and L_f(e), but the appendix refers only to 'visible distinguished-entry count', 'visible shortest-entry count', and 'merged-nearest-face count' as if they had been defined in Section 2. Lemma 16's inequality c_{f,e}(g) ≤ λ_S(g) is load-bearing for the large-face bound, so the sealed dual graph D_S, the merging of H-seals, and the exact definitions of p_S, q_S, s_S must be stated precisely. As written, a reader cannot recompute or audit the terminal load values from the certificate.
- [A6, Lemma 17(2)] The layer-cutoff audit is described only in prose: at every reachable state the verifier 'retries every admissible third-vertex choice there with the construction-layer bound relaxed' and 'finds no legal relevant triangular branch above layer 6.' This audit is exactly what ensures that the construction-layer cutoff at 6 omits no genuine relevant configuration. The statement is not accompanied by a pseudocode block or a machine-checked certificate of its own, and the notion of 'legal relevant branch' is not formalized. Since Lemma 18 uses this audit to conclude that the sealed search is exhaustive, this gap is load-bearing and needs to be closed either by a precise algorithmic specification or by an independently checkable certificate.
minor comments (4)
- [§3, proof of Theorem 1] The notation p(m) is used before it is defined; it should be stated explicitly that p(m) denotes the maximum number of edges in an m-vertex planar graph (with p(1)=0, p(2)=1, p(m)=3m−6 for 3≤m≤7).
- [Lemma 3] In the case u ≤ 5, the inequality is correct but could be written more clearly as ℓ(f) ≤ u + (7−u)/2 ≤ 6, which makes the use of the bound b(f) ≤ 7 transparent.
- [§3, discharging] The statement 'A face of degree 8 cannot occur' relies on the fact that in a 2-connected plane graph every face boundary is a cycle; this should be said explicitly at that point for the reader's convenience.
- [Data and code availability] The URL is given with a line break and no version information. If the repository is updated, the certificate outputs in the paper could become impossible to match. A stable identifier and a note on the exact software versions used would help.
Circularity Check
No load-bearing circularity: finite certificates are independent outputs; the 69/25 coefficient is derived by discharging algebra.
full rationale
The derivation in the paper is self-contained and non-circular. Theorem 1 is proved by induction and a discharging argument whose local inputs are the finite certificates (C1)–(C6). Those certificates are computed by exhaustive enumerations that reject states containing an 8-cycle and respect only the hypotheses of the theorem (C8-free, simple, 2-connected, δ ≥ 3); the reported maxima (7, 7, 5, 4; 6; 19/3; 9/2) are outputs of the searches, not parameters chosen to force the final coefficient. The discharging parameter α = 50/69 is selected after the local bounds are proved, and the final bound e(G) ≤ (2/α)(n−2) = (69/25)(n−2) follows by conservation of charge. No equation or definition in the paper defines a quantity in terms of the conclusion, no fitted value is renamed as a prediction, and no load-bearing step relies on a self-citation: the paper’s references are all external, and no prior work of the same authors is used to justify the central premises. The only substantive concern is whether the computer-assisted lifting argument of Proposition 1 and Lemmas 6–17 is truly exhaustive and correctly implemented; that is a soundness/reproducibility risk, not a circularity. Accordingly, the circularity score is 0.
Assumptions & free parameters
free parameters (1)
- α (discharging charge-per-vertex rate) =
50/69
assumptions (5)
- standard math Euler's formula: V − E + F = 2 for connected plane graphs
- domain assumption In a 2-connected plane graph every face boundary is a cycle
- standard math Wagner's theorem: a finite graph is planar iff it has no K5 or K3,3 minor
- domain assumption Coverage of the finite searches: every genuine rooted C8-free configuration satisfying the radius hypotheses appears in the enumerated search trees, and no legal completion is lost
- domain assumption The recorded certificate outputs are accurate (e.g., 223,766 states, 136,987 terminal leaves, max terminal load 9/2, zero overbound terminals in Lemma 17)
Cite this review
Pith. "Pith review of An improved upper bound for the planar Tur\'an number of $C_8$." pith.science (2026). https://pith.science/paper/6GLM3OB3
@misc{pith2026260716103,
author = {Pith},
title = {Pith review of: An improved upper bound for the planar Tur\'an number of $C_8$},
year = {2026},
howpublished = {\url{https://pith.science/paper/6GLM3OB3}},
note = {Machine review of arXiv:2607.16103}
}
abstract
We prove that every $n$-vertex simple planar graph with no copy of $C_8$ has at most \[ \frac{69}{25}(n-2) \] edges, for every $n\ge 8$. This improves the best known bound \[ \frac{323}{108}n-6 \qquad \text{for every } n\ge 27. \]
Figures
Reference graph
Works this paper leans on
-
[1]
D. W. Cranston, B. Lidický, X. Liu, and A. Shantanam. Planar Turán numbers of cycles: a counterexample.Electron. J. Combin., 29(3):P3.31, 2022.doi:10.37236/10774
-
[2]
C. Dowden. ExtremalC4-free/C5-free planar graphs.J. Graph Theory, 83(3):213–230, 2016. doi:10.1002/jgt.21991
-
[3]
D. Ghosh, E. Győri, R. R. Martin, A. Paulos, and C. Xiao. Planar Turán number of the 6-cycle.SIAM J. Discrete Math., 36(3):2028–2050, 2022.doi:10.1137/21M140657X
-
[4]
E. Győri, A. Li, and R. Zhou. The planar Turán number of the seven-cycle. arXiv:2307.06909v2, 2023.arXiv:2307.06909v2,doi:10.48550/arXiv.2307.06909
-
[5]
Y. Lan, Y. Shi, and Z.-X. Song. Extremal theta-free planar graphs.Discrete Math., 342(12):111610, 2019.doi:10.1016/j.disc.2019.111610
arXiv 2019
-
[6]
Y. Lan, Y. Shi, and Z.-X. Song. Planar Turán number and planar anti-Ramsey number of graphs.Oper. Res. Trans., 25(3):201–216, 2021.doi:10.15960/j.cnki.issn.1007-6093. 2021.03.013
-
[7]
R. Shi, Z. Walsh, and X. Yu. Dense circuit graphs and the planar Turán number of a cycle. J. Graph Theory, 108(1):27–38, 2025.doi:10.1002/jgt.23165
-
[8]
R. Shi, Z. Walsh, and X. Yu. Planar Turán number of the 7-cycle.European J. Combin., 126:104134, 2025.doi:10.1016/j.ejc.2025.104134
arXiv 2025
Show all 23 references
-
[9]
P. Turán. On an extremal problem in graph theory.Mat. Fiz. Lapok, 48:436–452, 1941
1941
-
[10]
K. Wagner. Über eine Eigenschaft der ebenen Komplexe.Math. Ann., 114:570–590, 1937. doi:10.1007/BF01594196. Appendix. Verification details for the local inputs This appendix gives the verification details for the six finite local certificates (C1)–(C6) stated in Theorem 2. For...
1937 doi
-
[11]
Listed vertices map injectively to ambient vertices; every displayed real edge, listed trian- gular face, and shared-edge dual adjacency maps to the corresponding genuine object
-
[12]
Their interiors are pairwise disjoint and contain no listed vertex
The unlisted portions ofQare represented by ordered virtual subarcs. Their interiors are pairwise disjoint and contain no listed vertex. If a true triangular continuation has a new third vertex in the interior of a virtual subarc, the search has a virtual-anchor branch: it ins...
-
[13]
Consequently every8-cycle found by the search consists of eight distinct genuine vertices and real edges and is an8-cycle of the ambient graph
Virtual subarcs are never treated as graph edges. Consequently every8-cycle found by the search consists of eight distinct genuine vertices and real edges and is an8-cycle of the ambient graph
-
[14]
Restoring the still unlisted parts ofQand the faces incident with them may add root entries, a shorter root route, or additional non-root4+-competitors
Every triangle whose true contribution througheis nonzero is listed. Restoring the still unlisted parts ofQand the faces incident with them may add root entries, a shorter root route, or additional non-root4+-competitors. These changes can only enlarge a true de- nominator or ...
-
[15]
if every triangular face ofPat dual distance at mostk−2fromgis closed inP, then no 4+-face ofGis closer togthanf
-
[16]
All triangular witnesses needed for these tests lie within dual distance at most5fromf
if every triangular face ofPat dual distance at mostk−1fromgis closed inP, thenf is the unique-nearest4+-face tog. All triangular witnesses needed for these tests lie within dual distance at most5fromf. Proof.Suppose that a non-root4 +-face is tied with or closer togthanf. Fol...
-
[17]
the second incident face is triangular, and the search adds that triangle using an admissible old vertex, an ordinary new vertex, or a new virtual anchor on one of the current virtual subarcs
-
[18]
the second incident face is a non-root4+-face, recorded by anH-seal
-
[19]
TheR-branch is not allowed on the displayed root-window edges30,01,12, since the root face cannot lie on both sides of one of its own boundary edges
the edge is another entry edge of the same root face, recorded by anR-seal. TheR-branch is not allowed on the displayed root-window edges30,01,12, since the root face cannot lie on both sides of one of its own boundary edges. For a completed sealed stateS, the verifier evaluat...
-
[20]
The recorded search has exactly223766labelled states,223765parent-child edges, one root state, and136987terminal leaves. Every non-root state has a recorded parent, ev- ery recorded child is obtained by one legal transition of the sealed search, including every virtual-anchor ...
-
[21]
The certificate records201940states with such a difference,554355differing face records, and maximum excess5
A stored construction layer may exceed the current sealed root distance, but never under- estimates it. The certificate records201940states with such a difference,554355differing face records, and maximum excess5. Within the transition system specified above, at every reachabl...
-
[22]
A compressed two-vertex boundary consisting of one real side and one virtual subarc is retained as a search component
Every virtual-anchor transition records the new label between the endpoints of one current virtual subarc before splitting the boundary. A compressed two-vertex boundary consisting of one real side and one virtual subarc is retained as a search component. Such a component occu...
-
[23]
There are no overbound terminal states
Every terminal state has computed upper-bound load at most9/2. There are no overbound terminal states. The mathematical certificate assertions and accompanying regression totals are quantity certified value regression totals: states / edges / leaves 223766/223765/136987 constr...
Reviewed August 1, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.