REVIEW 2 major objections 3 minor 2 cited by
Strong spectral stabilities for $C_{2k+1}$-free graphs
T0 review · 2 major / 3 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read This paper proves a sharp spectral-radius bound for C_{2k+1}-free graphs with chromatic number at least r, with equality only for the graph formed by joining a K_r to the smaller part of a complete bipartite graph.
desk verdict A credible abstract claiming a real improvement in spectral extremal graph theory, but the load-bearing exact-stability lemma is hidden in the full text. 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 load-bearing tool is a structural stability decomposition: every n-vertex C_{2k+1}-free graph with chromatic number at least r, for n at least linear in k, can be obtained from a large bipartite graph by suspending small graphs whose total vertex count is at most r−2. This is what converts the extremal problem into an eigenvalue comparison on a bounded-modification bipartite graph, and it is also what forces the extremal configuration to be the clique attachment T_{n-r+1,2}∘K_r.
What would settle it
A concrete way to test the claim is to search, by computation, for an n-vertex C_{2k+1}-free graph with χ(G) ≥ r and n ≥ 712k whose adjacency spectral radius exceeds λ(T_{n-r+1,2}∘K_r); for instance, attaching the clique K_r to the larger partite set rather than the smaller one, or adding a single extra edge inside the bipartite core, would yield a candidate counterexample if its spectral radius is larger.
Extended reading notes
Core claim
The central claim is the spectral theorem: for 3 ≤ r ≤ 2k and n ≥ 712k, if G is an n-vertex C_{2k+1}-free graph with χ(G) ≥ r, then λ(G) ≤ λ(T_{n-r+1,2}∘K_r), with equality if and only if G = T_{n-r+1,2}∘K_r. The extremal graph is a complete bipartite Turán graph with an additional clique identifying a vertex of the clique with a vertex of the smaller bipartition class. This resolves the spectral extremal question for F-free graphs of high chromatic number in this family, extending earlier results that covered special cases.
Load-bearing premise
The entire proof depends on the structural stability theorem from the first part: that every C_{2k+1}-free graph with chromatic number at least r has a large bipartite core with at most r−2 suspended vertices once n is at least linear in k; if this decomposition admits exceptions, the spectral comparison and the equality case collapse.
Editorial extensions
If this is right
- If the spectral theorem holds, then for every r ≤ 2k the spectral radius of C_{2k+1}-free graphs of chromatic number at least r is maximized by the same explicit construction.
- The structural result yields a tight upper bound on the number of edges in such graphs, recovering and improving the previous quadratic bound with a linear condition on n.
- The equality case pins down the extremal graph uniquely, showing that any other graph with the same property is strictly spectrally smaller.
- The work provides the first solution to the spectral extremal problem for F-free graphs with high chromatic number in this setting.
- The linear bound n ≥ 712k is a quantitative improvement over earlier constraints that required n to grow quadratically in r and k.
Reading between the lines
- The linear dependence on k suggests that a similar decomposition might hold for other families of graphs defined by forbidden odd cycles or color-critical graphs, but this is not claimed by the paper.
- The choice of identifying the clique with the smaller partite set may be deliberate because it balances the spectral contributions; swapping to the larger side may produce a graph with smaller or larger radius depending on the parameters, a question not explored here.
- The threshold 712k is likely not optimal; one could test numerically whether smaller constants work for specific k and r, but the paper does not pursue that.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims two main results. First, for C_{2k+1}-free graphs on n vertices with at least the bipartite Turán number plus a clique term, it establishes a structural stability theorem: such graphs can be made bipartite by deleting at most r-2 vertices, and more strongly, they are obtained from a large bipartite graph by suspending small graphs whose total order is at most r-2. This improves prior bounds on n by Ren-Wang-Wang-Yang and by Yan-Peng. Second, for the spectral extremal problem, the paper claims that for 3≤r≤2k and n≥712k, every n-vertex C_{2k+1}-free graph with chromatic number at least r has spectral radius at most λ(T_{n-r+1,2}∘K_r), with equality only for the stated graph. The authors state this is the first solution to the spectral extremal problem for F-free graphs with high chromatic number.
Significance. If the proofs are correct, the spectral theorem is a significant advance: it unifies and extends the prior results of Guo-Lin-Zhao and Zhang-Zhao, and it gives the first spectral extremal result for F-free graphs with a chromatic number lower bound. The structural theorem also improves quantitative dependencies, replacing quadratic bounds with a linear bound (n≥712k for the spectral part), which is valuable. The paper has no fitted constants, and the equality cases are explicitly stated, both of which are strengths.
major comments (2)
- [Abstract, first paragraph] The structural theorem is stated only as 'roughly' describing G as a large bipartite graph plus 'some small graphs' with total vertex count at most r-2. This formulation is too weak to support the spectral theorem's unique equality case. The equality G = T_{n-r+1,2}∘K_r requires that the suspended part is exactly one K_r attached to a vertex of the smaller partite set, with no additional edges among suspended vertices and no other attachment pattern. Merely deleting r-2 vertices to make G bipartite does not determine the spectral radius, since different internal edges and attachment positions change λ without changing the deletion count. The abstract needs to state the exact decomposition lemma, or at least a precise version that constrains the suspended subgraph and its attachment, for the implication to be checkable.
- [Abstract, second paragraph] The proof of the spectral theorem is not described. The statement asserts an extremal graph with a unique equality case, but the abstract provides no indication of the argument connecting the structural decomposition to the spectral radius comparison. As written, the reader cannot verify whether the step from 'bipartite after deleting r-2 vertices' to 'the unique extremal graph is T_{n-r+1,2}∘K_r' is rigorous. This is a load-bearing gap in the summary. The full text may contain the required argument, but the abstract does not; since no full text is available for this review, the central claim remains uncheckable.
minor comments (3)
- [Abstract, first paragraph] The phrase 'suspending some small graphs' is informal; the paper should specify whether these graphs are cliques, independent sets, or arbitrary, and how they are attached to the bipartite core.
- [Abstract, second paragraph] The definition of T_{n-r+1,2}∘K_r says 'identifying a vertex of K_r and a vertex of the smaller partite set' but does not say which vertex of K_r; this should be made precise (the paper presumably specifies any vertex, but the abstract leaves it ambiguous).
- [Abstract, first paragraph] The improvement statement 'weakening the requirement on n and k' is vague; the prior results' hypotheses should be compared explicitly in the introduction/theorems.
Circularity Check
No circularity found in the abstract; the reported theorems rest on independent prior results and prove-based arguments, not on fitted inputs or self-referential definitions.
full rationale
The available text is the abstract only, and it presents two theorem-style results: a structural stability theorem for C_{2k+1}-free graphs with large chromatic number, and a spectral radius bound with a unique extremal graph. Neither statement defines its conclusion in terms of its input assumptions. The structural theorem is described as improving earlier work by Ren–Wang–Wang–Yang and Yan–Peng, cited as independent prior results; the spectral theorem is said to extend results of Guo–Lin–Zhao and Zhang–Zhao. There are no fitted parameters, no quantity is fitted to a subset of data and then called a prediction, and no uniqueness theorem is imported from the present authors' prior work. The abstract does not quote equations that reduce the claimed inequalities to their assumptions, so no specific circular reduction can be exhibited. The skeptical concern that the abstract omits an exact-stability lemma needed for the equality case is a possible correctness or completeness risk, not circularity: it does not show that any input was defined in terms of the output. With no quotable reduction and no self-citation chain carrying the argument, the honest finding is no significant circularity.
Assumptions & free parameters
assumptions (2)
- standard math Standard spectral graph theory tools: Perron-Frobenius theory for adjacency matrices, eigenvalue interlacing, and the spectral radius formula for bipartite Turan graphs.
- standard math Standard extremal graph theory background: Erdos-Stone-Simonovits bounds and prior stability theorems for odd-cycle-free graphs.
Cite this review
Pith. "Pith review of Strong spectral stabilities for $C_{2k+1}$-free graphs." pith.science (2026). https://pith.science/paper/GSECYZJJ
@misc{pith2026250813643,
author = {Pith},
title = {Pith review of: Strong spectral stabilities for $C_2k+1$-free graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/GSECYZJJ}},
note = {Machine review of arXiv:2508.13643}
}
abstract
A stability result due to Ren, Wang, Wang and Yang [SIAM J. Discrete Math. 38 (2024)] shows that if $3\le r \le 2k$ and $n\ge 318 (r-2)^2k$, and $G$ is a $C_{2k+1}$-free graph on $n$ vertices with $e(G)\ge \lfloor {(n-r+1)^2}/{4}\rfloor +{r \choose 2}$, then $G$ can be made bipartite by deleting at most $r-2$ vertices. Using a different method, we give a linear bound on $n$ in terms of $k$ and show a stronger structural result, which roughly says that $G$ can be obtained from a large bipartite graph by suspending some small graphs that the total number of vertices is at most $r-2$. This improves a result of Yan and Peng (2024) by weakening the requirement on $n$ and $k$. As a direct corollary, we obtain a tight upper bound on the size of an $n$-vertex $C_{2k+1}$-free graph with chromatic number $\chi (G)\ge r$ for every $r\le 2k$. The second part of this paper concerns the spectral extremal problem for $C_{2k+1}$-free graphs. We denote by $\lambda (G)$ the spectral radius of the adjacency matrix of a graph $G$. Let $T_{n-r+1,2}\circ K_r$ be the graph obtained by identifying a vertex of the complete graph $K_r$ and a vertex of the smaller partite set of the bipartite Tur\'{a}n graph $T_{n-r+1 ,2}$. Using the spectral techniques, we prove that if $3\le r\le 2k$ and $n\ge 712k$, and $G$ is an $n$-vertex $C_{2k+1}$-free graph with chromatic number $\chi (G) \ge r$, then $\lambda (G)\le \lambda (T_{n-r+1,2}\circ K_r)$, where the equality holds if and only if $G=T_{n-r+1,2}\circ K_r$. Our result not only extends a result of Guo, Lin and Zhao [Linear Algebra Appl. 627 (2021)] as well as a result of Zhang and Zhao [Discrete Math. 346 (2023)], but also provides the first solution to the spectral extremal problem for $F$-free graphs with high chromatic number.
Forward citations
Cited by 2 Pith papers
-
Strong Subgraph-Count Stability in $C_{2\ell+1}$-Free Graphs
Near-extremal path or even-cycle counts force C_{2ℓ+1}-free graphs into suspended Turán form, giving exact high-chromatic generalized Turán numbers.
-
Longest odd cycles in non-bipartite $C_{2k+1}$-free graphs
If an n-vertex C_{2k+1}-free graph has at least floor((n-r+1)^2/4) + C(r,2) edges, then every odd cycle in it has length at most r, and the bound is sharp.
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.