Strong Subgraph-Count Stability in $C_{2\ell+1}$-Free Graphs

Xiamiao Zhao; Yuanpei Wang

Strong Subgraph-Count Stability in $C_{2\ell+1}$-Free Graphs

T0 review · 0 major / 5 minor · reviewed 2026-07-11 · grok-4.5

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

Pith's one-line read Near-maximal path or even-cycle counts force C_{2ℓ+1}-free graphs into a suspended bipartite structure.

desk verdict Clean high-chromatic stability for paths and even cycles in C_{2ℓ+1}-free graphs, powered by a reusable bipartite counting lemma. read the letter →

arxiv 2607.04347 v1 pith:ZHM64CXI submitted 2026-07-05 math.CO

Yuanpei Wang , Xiamiao Zhao This is my paper · ORCID

classification math.CO MSC 05C3505C3805C75

keywords generalizedTuránproblemstabilityoddcyclesubgraphcountspathsevencyclessuspensionstructurematching-admissiblegraphs

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The classical Turán graph T_{n,2} maximises the number of paths and even cycles among n-vertex graphs that avoid a fixed odd cycle. This paper asks what happens when one also insists on high chromatic number, or when the count merely meets the value of a suspended construction rather than the absolute maximum. It proves that any sufficiently large C_{2ℓ+1}-free graph whose path or even-cycle count reaches that of the suspended extremal family must itself be one of those suspended graphs (or a coarser suspension with fewer outside vertices). The argument rests on a new counting lemma for nearly complete bipartite graphs: both part imbalance and missing cross-edges reduce the number of copies of any fixed matching-admissible bipartite F by a term whose leading coefficient is made explicit. That quantitative conversion turns a subgraph-count hypothesis into the edge threshold already known to force the desired suspension structure, yielding exact high-chromatic extremal numbers for paths and even cycles.

What carries the argument

The matching-admissible counting theorem (Theorem 1.7): for any fixed matching-admissible connected bipartite F, both part imbalance η and the number μ of missing cross-edges lower N(F,H) by κ_F(η+μ)s^{v(F)−2} plus a lower-order error. This converts a near-extremal subgraph count into the edge lower bound required by the existing structural theorem of Zou–Li–Peng.

What would settle it

For concrete small parameters (e.g. ℓ=2, t=5, r=3) construct or computationally search an n-vertex C_5-free graph whose P_5-count meets or exceeds b^P_{5,3}(n) yet whose structure is neither in G_{n,3} nor in S_{5,3}(n); any such example for large n would refute the claim.

Watch

Extended reading notes

Core claim

For fixed ℓ≥2, t≥4 and 3≤r≤2ℓ−1 (with the extra restriction r≤t−1 when t is odd), every sufficiently large n-vertex C_{2ℓ+1}-free graph G satisfying N(P_t,G)≥b^P_{t,r}(n) belongs either to the family G_{n,r} of graphs with at most r−2 outside vertices or to the suspended family S_{t,r}(n). An analogous statement holds for even cycles C_{2a}, replacing S_{t,r}(n) by R_r(n) when r<2a and by T^*(r,n) when r≥2a. Consequently the high-chromatic maxima are attained precisely by the suspended constructions.

Load-bearing premise

The paper relies on a prior edge-threshold theorem that already forces any C_{2ℓ+1}-free graph with enough edges into the desired suspension family; if that threshold or its exceptional case is slightly wrong, the counting argument cannot finish the structural conclusion.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

This paper does exactly what the abstract claims: it turns near-extremal counts of fixed paths or even cycles into the strong suspension structure for C_{2ℓ+1}-free graphs, and thereby settles the high-chromatic exact numbers for those families.

What is new is twofold. First, the matching-admissible counting theorem (1.7) for nearly complete bipartite graphs: both part imbalance and missing cross-edges cost a clean main-term coefficient κ_F times the edge defect. The proof is elementary Taylor plus inclusion-exclusion on a fixed matching, and it is independent of the odd-cycle condition. Second, the reduction that feeds the resulting edge lower bound into the Zou–Li–Peng threshold and checks the exceptional K_{r+1} suspension by a coarser asymptotic. The path and cycle cases are then handled uniformly, with the extremal families S_{t,r}(n) and T^*(r,n) identified by direct comparison of the suspension side.

The soft spots are minor and already flagged by the authors. For odd t the coefficient comparison forces the extra restriction r ≤ t-1; they isolate the remaining range as Problem 7.1 rather than papering over it. Everything else rests on two black-box stability results that are cited correctly and used only after the new counting work has produced the edge threshold. No free parameters, no circularity, and the asymptotic expansions are written out carefully enough that a referee can check the leading coefficients in an afternoon.

This is for people who already work on generalised Turán stability or spectral extremal problems for odd-cycle-free graphs. It will be cited for the counting lemma alone, and the high-chromatic corollaries close a natural gap left by Gerbner, Hei–Hou and Yan–Peng. I would send it to a serious referee without hesitation; the proofs are complete and the contribution is solid.

Referee Report

0 major / 5 minor

Summary. The paper proves strong subgraph-count stability for n-vertex C_{2ℓ+1}-free graphs. For fixed ℓ≥2, t≥4 and 3≤r≤2ℓ-1 (with the extra restriction r≤t-1 when t is odd), any such graph whose number of copies of P_t meets or exceeds the maximum attained by the suspended family G_{n,r+1}\G_{n,r} must itself lie in G_{n,r} or in the explicit suspended-clique family S_{t,r}(n). An analogous statement holds for every fixed even cycle C_{2a}, with extremal families R_r(n) (when r<2a) or T^*(r,n) (when r≥2a). The high-chromatic corollaries then give exact extremal numbers and unique extremal graphs under the additional constraint χ(G)≥r. The technical engine is a new counting theorem (Theorem 1.7) for matching-admissible connected bipartite graphs in nearly complete bipartite hosts: both part imbalance and missing cross-edges produce a loss whose leading coefficient is identified explicitly. This converts a near-extremal subgraph count into an edge lower bound that can be fed into the Zou–Li–Peng structural threshold.

Significance. The work supplies the first strong structural stability theorems for paths and all even cycles under an odd-cycle forbidden subgraph, thereby completing the high-chromatic extremal picture that was previously known only for edges, spectral radius and C_4. The matching-admissible counting lemma is independent of the forbidden cycle and is likely to be reusable for other bipartite host graphs. The coefficient comparisons that produce the edge thresholds are fully explicit, the exceptional suspension of K_{r+1} is checked by a coarser asymptotic, and the single open range (odd t with r≥t) is cleanly isolated as Problem 7.1. These features make the contribution both technically solid and immediately usable for further generalized Turán problems.

minor comments (5)

In the statement of Theorem 1.3 the parenthetical restriction “if t is odd, assume also that r≤t-1” appears only after the range 3≤r≤2ℓ-1 has already been fixed; a single sentence in the introduction that flags this restriction (and points to Problem 7.1) would help the reader anticipate the later discussion in Section 7.
Proposition 1.2 and the subsequent asymptotic expansions in Lemma 2.6 use the same symbols T^+(r,n) and T^-(r,n); a brief reminder of their definitions at the beginning of the proof of Lemma 2.6 would improve readability.
The constant C_0 appearing in Theorem 1.7 is never quantified beyond “C_0>0”; while the O-notation absorbs it, a parenthetical remark that C_0 may depend on F would make the dependence transparent.
In the proof of Proposition 2.4 the claim that every added edge lies in a copy of P_t is verified only for t=4 by an explicit construction; a one-line indication that the same alternating-path extension works for general fixed t would close the argument more cleanly.
Several arXiv preprints are cited (especially Zou–Li–Peng [16] and Yan–Peng [13,14]); once those papers appear in print the bibliographic entries should be updated.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: new counting estimates convert subgraph counts into edge thresholds that are then fed into independent external structural theorems.

full rationale

The derivation is self-contained and non-circular. Theorem 1.7 (and its extensions Prop. 4.1 / Cor. 4.2) is proved from first principles by Taylor expansion of the complete-bipartite embedding polynomial and inclusion-exclusion on missing matching edges; the resulting main coefficients κ_F are explicit and independent of the forbidden odd cycle. These coefficients are compared directly with the asymptotic expansions of b^P_{t,r}(n) and b^∘_{a,r}(n) (Lemmas 2.6–2.7) to force the edge lower bound (5.1)/(6.1). That bound is then handed to the external Zou–Li–Peng structural threshold (Thm 2.1) and the spectral bound of Zhai–Lin–Shu (Lemma 2.3). Both citations are arXiv preprints by distinct author sets; neither is used to define the quantities being counted, nor do the new counting lemmas feed back into them. The exceptional suspension of K_{r+1} is discarded by a coarser count of the same type, and the open range for odd paths with r≥t is isolated by the authors themselves (Problem 7.1). No fitted parameters, self-definitional identities, or load-bearing self-citations appear.

Assumptions & free parameters 0 free parameters · 4 assumptions · 2 invented entities

Pure combinatorial argument. No free parameters are fitted. The load-bearing external inputs are two published stability theorems and standard asymptotic expansions of falling factorials; the new entities are purely definitional families used to state the extremal constructions.

assumptions (4)

domain assumption Zou–Li–Peng strong edge-stability theorem: any n-vertex C_{2ℓ+1}-free graph with e(G)≥⌊(n−r)^2/4⌋+(r+1 choose 2) lies in G_{n,r+1} or is the exceptional suspension of K_{r+1} (Theorem 2.1).
Invoked after the counting lemma produces the edge lower bound; the entire structural conclusion rests on this black-box.
domain assumption Lemma 2.2 (consequence of Zou–Li–Peng): near-extremal C_{2ℓ+1}-free graphs contain a large bipartite induced subgraph of high minimum degree with only O(1) external vertices of bounded degree.
Used to reduce the general C_{2ℓ+1}-free case to the bipartite counting lemma.
domain assumption Spectral radius bound of Zhai–Lin–Shu: λ(G)≤√m+ℓ for C_{2ℓ+1}-free graphs with m edges.
Applied in Lemma 4.3 to convert a near-extremal subgraph count into a linear edge lower bound.
standard math Standard falling-factorial expansions and the formula for the number of paths/cycles in complete bipartite graphs.
Used throughout Sections 2–3 to obtain leading coefficients κ_F and the asymptotic formulae for b^P and b^∘.

invented entities (2)

Family G_{n,r} of graphs obtained by suspending total of at most r−2 outside vertices onto a bipartite core
purpose: Provides the structural language in which the stability statements are phrased.
Purely definitional; no independent physical or computational existence claimed.
Suspended extremal families S_{t,r}(n) and T^*(r,n)
purpose: Identify the unique maximisers of path and even-cycle counts among high-chromatic C_{2ℓ+1}-free graphs.
Constructed explicitly from the bipartite Turán graph plus a clique; existence is combinatorial, not empirical.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Strong Subgraph-Count Stability in $C_{2\ell+1}$-Free Graphs." pith.science (2026). https://pith.science/paper/ZHM64CXI

@misc{pith2026260704347,
  author       = {Pith},
  title        = {Pith review of: Strong Subgraph-Count Stability in $C_2\ell+1$-Free Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZHM64CXI}},
  note         = {Machine review of arXiv:2607.04347}
}

abstract

Starting from the stability theorem of Erd\H{o}s and Simonovits, stability problems for graphs forbidding a fixed subgraph have been studied in terms of edge numbers, spectral radii and subgraph counts. Let $\mathcal{N}(F,G)$ denote the number of unlabeled copies of $F$ in $G$. It is known that, for every fixed path $P_t$ and even cycle $C_{2a}$, the maximum number of copies in an $n$-vertex $C_{2\ell+1}$-free graph is attained by the bipartite Tur\'an graph $T_{n,2}$. In this paper we obtain strong structural stability for $C_{2\ell+1}$-free graphs in terms of copies of paths and even cycles. For fixed $\ell\ge2$ and $3\le r\le2\ell-1$, we show that if an $n$-vertex $C_{2\ell+1}$-free graph contains at least as many copies of $P_t$ or $C_{2a}$ as the corresponding suspended extremal construction, then it has the corresponding suspension structure. This gives exact high-chromatic extremal theorems for paths and even cycles. We also prove a counting theorem for nearly complete bipartite graphs. It shows that, for every fixed matching-admissible connected bipartite graph $F$, both imbalance between the two parts and missing cross-edges decrease the number of copies of $F$ by a term with a specified main coefficient. This theorem is independent of the forbidden odd cycle and converts subgraph-count assumptions into the edge bounds needed for the structural theorem.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 1 linked inside Pith

[1]

Alon and C

N. Alon and C. Shikhelman, ManyT copies inH-free graphs, J. Comb. Theory, Ser. B 121 (2016) 146–172

2016
[2]

Erdős and A.H

P. Erdős and A.H. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946) 1087–1091

1946
[3]

Erdős and M

P. Erdős and M. Simonovits, A limit theorem in graph theory, Studia Sci. Math. Hungar. 1 (1966) 51–57

1966
[4]

Erdős, On the number of complete subgraphs contained in certain graphs, Publ

P. Erdős, On the number of complete subgraphs contained in certain graphs, Publ. Math. Inst. Hungar. Acad. Sci. Ser. A 7 (1962) 459–464

1962
[5]

Füredi and D.S

Z. Füredi and D.S. Gunderson, Extremal numbers for odd cycles, Combin. Probab. Comput. 24 (2015) 641–645

2015
[6]

Gerbner, On Turán-good graphs, Discrete Math

D. Gerbner, On Turán-good graphs, Discrete Math. 344 (2021) 112445

2021
[7]

Gerbner and C

D. Gerbner and C. Palmer, Survey of generalized Turán problems – counting subgraphs, Electron. J. Comb., Dynamic Surveys DS27 (2026)

2026
[8]

Hei and X

D. Hei and X. Hou, The cycle of length four is strictlyF-Turán-good, Bull. Malays. Math. Sci. Soc. 47 (2024) 5

2024

Show all 16 references

[9]

Mantel, Problem 28, Wiskundige Opgaven 10 (1907) 60–61

W. Mantel, Problem 28, Wiskundige Opgaven 10 (1907) 60–61

1907
[10]

S. Ren, J. Wang, S. Wang and W. Yang, A stability result forC2k+1-free graphs, SIAM J. Discrete Math. 38 (2024) 1733–1756

2024
[11]

Simonovits, A method for solving extremal problems in graph theory, stability problems, in: Theory of Graphs (Proc

M. Simonovits, A method for solving extremal problems in graph theory, stability problems, in: Theory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968, pp. 279–319

1966
[12]

Turán, On an extremal problem in graph theory, Mat

P. Turán, On an extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941) 436–452. 18

1941
[13]

Yan and Y

Z. Yan and Y. Peng, Number of copies ofC4 guarantees strong structural stability of graphs forbiddingC 2k+1, Discrete Math. 349 (2026) 115132

2026
[14]

Yan and Y

Z. Yan and Y. Peng, A strong structural stability ofC2k+1-free graphs, J. Graph Theory 112 (2026) 151–160

2026
[15]

M. Zhai, H. Lin and J. Shu, Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs, Eur. J. Comb. 95 (2021) 103322

2021
[16]

L. Zou, Y. Li and Y. Peng, Strong spectral stabilities forC2k+1-free graphs, arXiv preprint, arXiv:2508.13643v2, 2025. 19

2025 arXiv

Pith tools

Reviewed July 11, 2026 · model on record in the stance chip above.

[1] [1]

Alon and C

N. Alon and C. Shikhelman, ManyT copies inH-free graphs, J. Comb. Theory, Ser. B 121 (2016) 146–172

2016

[2] [2]

Erdős and A.H

P. Erdős and A.H. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946) 1087–1091

1946

[3] [3]

Erdős and M

P. Erdős and M. Simonovits, A limit theorem in graph theory, Studia Sci. Math. Hungar. 1 (1966) 51–57

1966

[4] [4]

Erdős, On the number of complete subgraphs contained in certain graphs, Publ

P. Erdős, On the number of complete subgraphs contained in certain graphs, Publ. Math. Inst. Hungar. Acad. Sci. Ser. A 7 (1962) 459–464

1962

[5] [5]

Füredi and D.S

Z. Füredi and D.S. Gunderson, Extremal numbers for odd cycles, Combin. Probab. Comput. 24 (2015) 641–645

2015

[6] [6]

Gerbner, On Turán-good graphs, Discrete Math

D. Gerbner, On Turán-good graphs, Discrete Math. 344 (2021) 112445

2021

[7] [7]

Gerbner and C

D. Gerbner and C. Palmer, Survey of generalized Turán problems – counting subgraphs, Electron. J. Comb., Dynamic Surveys DS27 (2026)

2026

[8] [8]

Hei and X

D. Hei and X. Hou, The cycle of length four is strictlyF-Turán-good, Bull. Malays. Math. Sci. Soc. 47 (2024) 5

2024