Pith. sign in

REVIEW 1 major objections 4 minor 23 references

In planar graphs without shorter odd cycles, the maximum number of (2k+1)-cycles is exactly the product maximum h_k(n) for large n.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.5

2026-07-13 01:39 UTC pith:47MIA3VL

load-bearing objection Exact planar Turán number for every odd cycle under the shorter-odd-cycle ban; long but coherent combinatorial proof that matches a clean product construction. the 1 major comments →

arxiv 2607.09624 v1 pith:47MIA3VL submitted 2026-07-10 math.CO

The maximum number of odd cycles in planar graphs forbidding shorter odd cycles

Yichen Wang , Ervin Gy\H{o}ri , Zhen He This is my paper
classification math.CO MSC 05C3505C1005C38
keywords generalized planar Turán numberodd cyclesplanar graphsinducibilityC_{2k+1}forbidden short cycles
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper settles an exact generalized planar Turán problem: among n-vertex planar graphs that contain no odd cycle shorter than 2k+1, what is the largest possible number of copies of C_{2k+1}? For every k≥3 and all sufficiently large n the answer is the integer product maximum h_k(n) obtained by partitioning n-k-1 into k positive parts and multiplying them. The bound is realized by an explicit construction that starts with a single (2k+1)-cycle, blows up k-1 non-adjacent vertices into independent sets, and replaces one edge by an arbitrary tree whose bipartition is joined to the remaining two cycle vertices. Because shorter odd cycles are forbidden, every counted cycle is automatically induced, so the result also confirms a known conjecture on the inducibility of odd cycles in planar graphs under that extra restriction. The argument proceeds by first reducing any extremal graph to one that satisfies three technical regularity properties, then showing that those graphs must contain a large collection of degree-two vertices or special paths that force the structure to be close to the stated construction.

Core claim

For every integer k≥3 there exists N=N(k) such that every n-vertex planar graph free of all odd cycles of length at most 2k-1 contains at most h_k(n) copies of C_{2k+1}, where h_k(n) is the maximum of the product x_1…x_k over positive integers summing to n-k-1; the bound is attained by the blow-up-plus-tree construction of Figure 1.

What carries the argument

The three technical properties (minimum number of long cycles through every small vertex set, shared cycles for distinct degree-two neighborhoods, and correct interaction of degree-two vertices with special paths) that any extremal graph can be transformed into without decreasing the cycle count; once these hold, a large Δ_2 forces the graph to match the product-extremal construction.

Load-bearing premise

The claim that every planar graph free of short odd cycles can be rewritten, without losing C_{2k+1} copies, as a graph that obeys the three technical regularity properties used in the main counting argument.

What would settle it

Exhibit a single large planar graph free of odd cycles shorter than 2k+1 whose number of C_{2k+1} exceeds h_k(n), or show that one of the rewriting operations of Section 3 strictly decreases the cycle count on some infinite family.

Watch this falsifier — get emailed when new claim-graph text bears on it.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 4 minor

Summary. The paper determines the exact generalized planar Turán number ex_P(n, C_{2k+1}, {C_3,C_5,...,C_{2k-1}}) for every k≥3 and all sufficiently large n. The extremal value is the product maximum h_k(n) over positive integers summing to n-k-1, attained by an explicit construction that blows up k-1 non-adjacent vertices of a C_{2k+1} and replaces one edge by a tree. Because shorter odd cycles are forbidden, every counted C_{2k+1} is induced, so the result also confirms the planar inducibility conjecture of Ghosh–Győri–Janzer–Paulos–Salia–Zamora (and Savery) under that extra hypothesis. The proof reduces an arbitrary extremal graph to one satisfying three technical properties, then extracts large Δ_m quantities via empty-region and degree-two/special-path lemmas, and finally bootstraps the product structure.

Significance. Exact extremal numbers for planar graphs that forbid an infinite family of subgraphs are rare; the result gives a clean closed-form answer for odd cycles of arbitrary length. It also supplies a rigorous partial confirmation of a natural inducibility conjecture that has attracted recent attention. The layered combinatorial argument (reduction to three properties, empty-region analysis, unified treatment of degree-two vertices and special paths, Δ_m estimates, bootstrap) is technically substantial and of independent interest for other planar Turán problems. The matching construction is explicit and elementary, so the bound is sharp once the upper-bound analysis is accepted.

major comments (1)
  1. Section 3 (Lemmas 9–10 and the progressive-induction argument that derives Theorem 1 from Theorem 11): the claim that every extremal graph can be transformed into a graph satisfying properties (1)–(3) without decreasing f_k is load-bearing. The operations (delete-and-blow-up of degree-two vertices, edge swaps around special paths) are asserted to preserve planarity and C^o_<2k+1-freeness while never decreasing the cycle count, yet many intermediate verifications are declared “routine” and the potential-function analysis (q(G), number of degree-two vertices) is only sketched. A concrete verification that no simultaneous planarity/odd-cycle constraint can produce a net loss of C_{2k+1} under these operations is needed before the subsequent analysis of graphs with properties (1)–(3) can be said to control the original extremal number.
minor comments (4)
  1. Throughout Sections 4.1–4.4 several applications of Lemma 7 and the AM-GM estimates are abbreviated as “routine”; expanding the most frequently used inequalities (especially the passage from (7) to the final bound on Δ_m) would improve readability without lengthening the paper substantially.
  2. Figure 1 caption and the construction description after Theorem 1: the precise bipartition of the tree and the attachment of its two parts to u_1 and u_k should be stated more carefully so that the count of C_{2k+1} is immediate.
  3. The constants ℓ,ε,ε',ξ appearing in (1) are introduced without an explicit hierarchy of how large n must be relative to each of them; a short remark after (1) would clarify the order of quantifiers.
  4. In the proof of Lemma 15 the maximum matching argument assumes a cyclic order around u_2; a one-sentence justification that the embedding can be chosen so that this order is well-defined would remove a minor ambiguity.

Circularity Check

0 steps flagged

No circularity: the upper bound is derived by combinatorial counting under planarity and forbidden shorter odd cycles, matching an independently defined product maximum h_k(n).

full rationale

The target quantity h_k(n) is defined purely as the maximum of the product x_1…x_k over positive integers summing to n-k-1; it does not depend on any host graph or fitted parameter. Theorem 1 asserts that the extremal number equals this quantity for large n, and the proof proceeds by (i) reducing an arbitrary extremal graph to one satisfying three technical properties via explicit local operations that never decrease the number of C_{2k+1} (Section 3, Lemmas 9–10), (ii) establishing lower bounds on path counts Δ_m via degree-two vertices and special paths (Sections 4.1–4.4), and (iii) bootstrapping a large Δ_2 into a near-extremal blow-up structure whose remaining vertices are shown by direct counting (Lemma 27) to contribute at most h_k(n). All inequalities are combinatorial (AM-GM, forest bounds, planarity of regions) and do not recycle the target value. Self-citations supply only background planar-Turán results and the statement of Conjecture 2; none is load-bearing for the upper bound. The reduction risk flagged by the reader is a possible correctness gap, not a definitional or self-referential loop. Consequently the derivation is self-contained against its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 3 invented entities

The paper is a pure combinatorial existence/upper-bound argument. It relies only on standard graph-theoretic and planarity facts, plus three technical properties that are shown to be assumable without loss. No numerical parameters are fitted; the constants ℓ,ε,ε',ξ are existential and chosen sufficiently small relative to 1/k.

axioms (4)
  • standard math Every planar graph admits a plane embedding in which faces are well-defined open regions; edge crossings are forbidden.
    Used throughout Sections 4.1–4.5 to speak of empty regions and interior/exterior of cycles.
  • standard math A forest on m vertices has at most m-1 edges; bipartite forests satisfy the weighted bound of Lemma 3.
    Invoked repeatedly to bound path counts via Observation 6 and Lemma 3.
  • standard math Any circuit of odd length contains an odd cycle of at most that length.
    Used in Lemmas 4–5 and Claim 20 to derive contradictions from shorter odd circuits.
  • ad hoc to paper For n large enough relative to k, any extremal graph can be transformed into one satisfying properties (1)–(3) without decreasing the number of C_{2k+1}.
    The reduction of Section 3 (Lemmas 9–10 and the procedure before Theorem 11) is the key technical hypothesis that lets the rest of the proof assume those three properties.
invented entities (3)
  • special path (u1 x_ℓ y_ℓ u2) no independent evidence
    purpose: A local configuration of degree-three vertices that yields a large lower bound on p_{2k-2} via property (1).
    Defined after Lemma 7; used in Lemmas 8, 15, 16 and property (3).
  • t-path-decomposition {A1,…,A_{t-1}} of a pair (u,w) no independent evidence
    purpose: Partitions the internal vertices of all length-t paths so that planarity and forbidden short odd cycles force the Ai to be pairwise disjoint and the edges between consecutive Ai to form forests.
    Defined in (3); central to all Δ_m estimates and the bootstrap in Section 4.5.
  • properties (1), (2), (3) of C^o_<2k+1-free planar graphs no independent evidence
    purpose: Three local density and symmetry conditions that any extremal graph may be assumed to satisfy after the reduction of Section 3.
    Stated before Lemma 8; the entire proof of Theorem 11 works under these assumptions.

pith-pipeline@v1.1.0-grok45 · 41177 in / 3078 out tokens · 32554 ms · 2026-07-13T01:39:07.516173+00:00 · methodology

0 comments
read the original abstract

Given a graph $H$ and a family of graphs $\mathcal{F}$, the generalized planar Tur\'an number $\mathrm{ex}_\mathcal{P}(n, H, \mathcal{F})$ is the maximum number of copies of $H$ in an $n$-vertex planar graph that contains no graph $F \in \mathcal{F}$ as a subgraph. When only induced copies of $H$ are counted, we denote the corresponding generalized planar Tur\'an number by $\mathrm{ex}_\mathcal{P}(n, H^{\mathrm{ind}}, \mathcal{F})$. Gy\H{o}ri and Karim determined $\mathrm{ex}_\mathcal{P}(n, C_{5}, \{C_3\})$. In this paper, we determine the exact value of $\mathrm{ex}_\mathcal{P}(n, C_{2k+1}, \{C_3,C_5,\ldots,C_{2k-1}\})$ for every $k \ge 3$. Since all shorter odd cycles are forbidden, every $C_{2k+1}$ is induced. This problem is closely related to the inducibility of odd cycles in planar graphs. Ghosh, Gy\H{o}ri, Janzer, Paulos, Salia and Zamora~(and independently Savery) determined the exact value of $\mathrm{ex}_\mathcal{P}(n, C_5^{\mathrm{ind}}, \emptyset)$. Moreover, they established a conjecture for all odd cycles $C_{2k+1}$ with $k \ge 3$. Our result confirms their conjecture under the additional assumption that all shorter odd cycles are forbidden.

Figures

Figures reproduced from arXiv: 2607.09624 by Ervin Gy\H{o}ri, Yichen Wang, Zhen He.

Figure 1
Figure 1. Figure 1: The extremal construction in Theorem 1. 4. We have x1 + x2 + · · · + xk−1 + xk = n − k − 1. It is straightforward to verify that the number of copies of C2k+1 is at most hk(n), with equality when the xi differ by at most one. Note that the construction is not unique, since the tree may be chosen in many different ways. In the non-planar case, Grzesik and Kielak [9] proved for k ≥ 3, ex(n, C2k+1, C o <2k+1)… view at source ↗
Figure 2
Figure 2. Figure 2: The path from x1 to y3ℓ . However, it is not always possible to find such a structure. The following lemma shows that if u and w satisfy suitable hypotheses relative to their 3-path-decomposition (rather than having a large 2-path-decomposition), then we can still obtain a comparable lower bound on p2k−2(u, w) by appealing to property (1), at the expense of an ϵ factor. Lemma 8. Let G be a planar graph for… view at source ↗
Figure 3
Figure 3. Figure 3: The operations when G does not have property (3). Lemma 9. Let G be a planar graph on n vertices forbidding C o <2k+1 that does not satisfy property (2). Then there exists a planar graph G′ on n vertices forbidding C o <2k+1 with fk(G′ ) ≥ fk(G). Moreover, G′ has the following property. 1. Either G′ does not have property (1), fk(G′ ) ≥ fk(G); 2. or G′ has property (2), fk(G′ ) > fk(G); 3. or G′ has proper… view at source ↗
Figure 4
Figure 4. Figure 4: The cycle u1v1u2v2 in Lemma 12 and the cycle u1xyu2y ′x ′u1 in Lemma 14. As a corollary, we obtain the following. Corollary 13. Let G be a planar graph on n vertices forbidding C o <2k+1 with property (1). There exists n1 = n1(k) such that for all n ≥ n1, the following holds. Let (u1, u2) be a (2k − 1)-valid pair in G. If |N(u1)∩N(u2)| ≥ 800k k , then there exists a vertex of degree two in N(u1)∩N(u2). Pro… view at source ↗
Figure 5
Figure 5. Figure 5: The region Ri and the case when xi is adjacent to a vertex y in Ri other than yi and yi+1. The dotted line is an impossible edge. be adjacent to yi+2, since xi+1yi cannot be an edge by planarity. Continuing in this way, we obtain a path xiyi+1xi+1yi+2 . . . xi+3ℓyi+3ℓ+1 such that every xj , yj has degree three. Remark. In the statement of Lemma 15, {A1, A2} is the 3-path-decomposition of (u1, u2). If we re… view at source ↗
Figure 6
Figure 6. Figure 6: In the proof of Lemma 16. path. Thus there exists a vertex x1 ∈ A1 of degree two. Let y1 ∈ A2 be the neighbor of x1 other than u1 (see [PITH_FULL_IMAGE:figures/full_fig_p020_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The left figure is for Case 1, and the right figure is for Case 2 in the proof of Lemma 17. [PITH_FULL_IMAGE:figures/full_fig_p022_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: The cycle containing the path u1x1x2 and the path yiyi+1yi+2 in Claim 20. (2k − 3 − q) + (i + 2) = 2k − 1 − q + i. Therefore, 2k − 1 − q + i ≥ 2k + 1, and thus q ≤ i − 2. Hence q = i − 2. In particular, we easily get a contradiction when i < 2. Case 2: the cycle consists of u1x1x2, (x2, yi+2)-path of length q denoted by P ′ (x2, yi+2), yi+2yi+1yi , (u1, yi)-path of length 2k − 3 − q denoted by P ′ (u1, yi)… view at source ↗
Figure 9
Figure 9. Figure 9: The hollow points represent vertices of degree two. The red vertices form a special [PITH_FULL_IMAGE:figures/full_fig_p025_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Three cases in the proof of Lemma 19. Hollow vertices are of degree two. The path [PITH_FULL_IMAGE:figures/full_fig_p026_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: The structure of the graph in Lemma 27 and Proposition 28. [PITH_FULL_IMAGE:figures/full_fig_p034_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: The cycle containing v and a ′ 1 . The hollow vertices are special vertices. Now consider cycles of Type 3 (see the right figure in [PITH_FULL_IMAGE:figures/full_fig_p036_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: An illustration for the sets P and T. Combining this with the bounds for Types 1 and 2 proves the proposition. ■ We now complete the proof of Lemma 27. Let {P1, P2} be the 3-path-decomposition of (u2, aint 1 ) in Rint avoiding u1, that is, let Pi be the set of vertices that lie on a path from u2 to a int 1 of length three and avoid u1. Let P = P1 ∪ P2. By definition, P ⊆ X ∪ {w int 1 } (see [PITH_FULL_IM… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

23 extracted references · 4 linked inside Pith

  1. [1]

    A. F. Alameddine. On the number of cycles of length 4 in a maximal planar graph.Journal of Graph Theory, 4(4):417–422, 1980

    1980

  2. [2]

    Alon and Y

    N. Alon and Y. Caro. On the number of subgraphs of prescribed type of planar graphs with a given number of vertices. InNorth-Holland Mathematics Studies, volume 87, pages 25–36. Elsevier, 1984

    1984

  3. [3]

    A. C. Antonir and A. Shapira. Bounding the number of odd paths in planar graphs via convex optimization.Journal of Graph Theory, 107(2):330–343, 2024

    2024

  4. [4]

    Balogh, P

    J. Balogh, P. Hu, B. Lidick` y, and F. Pfender. Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle.European Journal of Combinatorics, 52:47–58, 2016

    2016

  5. [5]

    Cox and R

    C. Cox and R. R. Martin. Counting paths, cycles, and blow-ups in planar graphs.Journal of Graph Theory, 101(3):521–558, 2022

    2022

  6. [6]

    Cox and R

    C. Cox and R. R. Martin. The maximum number of 10-and 12-cycles in a planar graph. Discrete Mathematics, 346(2):113245, 2023. 39

    2023

  7. [7]

    Ghosh, E

    D. Ghosh, E. Gy˝ ori, O. Janzer, A. Paulos, N. Salia, and O. Zamora. The maximum number of inducedC 5’s in a planar graph.Journal of Graph Theory, 99(3):378–398, 2022

    2022

  8. [8]

    Grzesik, E

    A. Grzesik, E. Gy˝ ori, A. Paulos, N. Salia, C. Tompkins, and O. Zamora. The maximum number of paths of length three in a planar graph.Journal of Graph Theory, 101(3):493– 510, 2022

    2022

  9. [9]

    Grzesik and B

    A. Grzesik and B. Kielak. On the maximum number of odd cycles in graphs without smaller odd cycles.Acta Mathematica Universitatis Comenianae, 88(3):755–758, 2019

    2019

  10. [10]

    Gy˝ ori and H

    E. Gy˝ ori and H. H. Karim. Generalized planar Tur´ an numbers related to short cycles. arXiv preprint arXiv:2405.08162, 2024

    Pith/arXiv arXiv 2024

  11. [11]

    Gy˝ ori, A

    E. Gy˝ ori, A. Paulos, N. Salia, C. Tompkins, and O. Zamora. The maximum number of pentagons in a planar graph.arXiv preprint arXiv:1909.13532, 2019

    Pith/arXiv arXiv 1909

  12. [12]

    Gy˝ ori, A

    E. Gy˝ ori, A. Paulos, N. Salia, C. Tompkins, and O. Zamora. Generalized planar Tur´ an numbers.arXiv preprint arXiv:2002.04579, 2020

    Pith/arXiv arXiv 2002

  13. [13]

    S. L. Hakimi and E. F. Schmeichel. On the number of cycles of length k in a maximal planar graph.Journal of Graph Theory, 3(1):69–86, 1979

    1979

  14. [14]

    Heath, R

    E. Heath, R. R. Martin, and C. Wells. The maximum number of odd cycles in a planar graph.Journal of Graph Theory, 108(4):745–780, 2025

    2025

  15. [15]

    Hefetz and M

    D. Hefetz and M. Tyomkyn. On the inducibility of cycles.Journal of Combinatorial Theory, Series B, 133:243–258, 2018

    2018

  16. [16]

    Huynh, G

    T. Huynh, G. Joret, and D. R. Wood. Subgraph densities in a surface.Combinatorics, Probability and Computing, 31(5):812–839, 2022

    2022

  17. [17]

    Kr´ al’, S

    D. Kr´ al’, S. Norin, and J. Volec. A bound on the inducibility of cycles.Journal of Combinatorial Theory, Series A, 161:359–363, 2019

    2019

  18. [18]

    Z. Lv, E. Gy˝ ori, Z. He, N. Salia, C. Tompkins, and X. Zhu. The maximum number of copies of an even cycle in a planar graph.Journal of Combinatorial Theory, Series B, 167:15–22, 2024

    2024

  19. [19]

    Pippenger and M

    N. Pippenger and M. C. Golumbic. The inducibility of graphs.Journal of Combinatorial Theory, Series B, 19(3):189–203, 1975

    1975

  20. [20]

    A. A. Razborov. Flag algebras.The Journal of Symbolic Logic, 72(4):1239–1282, 2007

    2007

  21. [21]

    M. Savery. Planar graphs with the maximum number of induced 6-cycles.arXiv preprint arXiv:2110.07319, 2021. 40

    Pith/arXiv arXiv 2021

  22. [22]

    M. Savery. Planar graphs with the maximum number of induced 4-cycles or 5-cycles. Graphs and Combinatorics, 40(3):46, 2024

    2024

  23. [23]

    D. R. Wood. On the maximum number of cliques in a graph.Graphs and Combinatorics, 23(3):337–352, 2007. 41

    2007