pith. sign in

arxiv: 2606.06987 · v1 · pith:EX7XG6KVnew · submitted 2026-06-05 · 🧮 math.CO

Tight Bound for Nikiforov's Spectral Even-Cycle Conjecture

Peiru Kuang , Feng Liu , Shuang Sun , Yan Wang , Jiasheng Zeng This is my paper

Pith reviewed 2026-06-27 21:57 UTC · model grok-4.3

classification 🧮 math.CO
keywords Nikiforov conjecturespectral radiuseven-cycle-free graphsA_alpha matrixextremal graph theorypath lemmaPerron vectorforbidden subgraphs
0
0 comments X

The pith

For α bounded away from 1, every sufficiently large C_{2k+2}-free graph has A_α-spectral radius at most that of S^+_{n,k} when n is linear in k.

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

The paper proves that for any fixed ε > 0 the graph S^+_{n,k} maximizes the A_α spectral radius among all n-vertex C_{2k+2}-free graphs, provided α ≤ 1 − ε, k is large enough, and n ≥ C_ε k. This strengthens earlier results that required n to grow much faster than k. The authors introduce a weighted rooted Erdős–Gallai type path lemma to control the structure of such graphs through their Perron vectors and thereby identify the unique maximizer. A reader would care because the result places the threshold for the conjecture in the linear range rather than a higher power of k.

Core claim

For every ε>0 there are constants C_ε and k_ε such that for all 0≤α≤1−ε, k≥k_ε and n≥C_ε k, every n-vertex C_{2k+2}-free graph G satisfies ρ_α(G)≤ρ_α(S^+_{n,k}), with equality if and only if G≅S^+_{n,k}. In particular the case α=0 answers the problem of determining the optimal exponent γ(k) in the linear range.

What carries the argument

Weighted rooted Erdős–Gallai type path lemma that bounds the growth of paths in C_{2k+2}-free graphs and is combined with Perron-vector analysis to force the extremal structure.

If this is right

  • When α=0 the adjacency spectral radius of C_{2k+2}-free graphs is maximized exactly by S^+_{n,k} for all n at least linear in k.
  • The same linear-size threshold and unique maximizer hold uniformly for every α in the interval [0, 1 − ε].
  • The method also produces asymptotically tight A_α bounds for the families of (K_1 ∨ P_ℓ)-free graphs and F_s-free graphs.
  • Equality holds only for the graph S^+_{n,k}, so the extremal example is identified precisely.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The linear threshold may allow the constants to be tracked explicitly enough for verification on moderate-sized instances.
  • Variants of the path lemma could be adapted to obtain linear thresholds for other forbidden even cycles or for odd-cycle problems.
  • The approach suggests that many spectral extremal problems with forbidden bipartite subgraphs stabilize once n exceeds a fixed multiple of the forbidden parameter.

Load-bearing premise

The weighted rooted Erdős–Gallai type path lemma correctly bounds the growth of paths in C_{2k+2}-free graphs and can be combined with Perron-vector analysis to force the extremal structure for all alpha bounded away from 1.

What would settle it

A single C_{2k+2}-free graph on n = C_ε k vertices whose A_α spectral radius strictly exceeds that of S^+_{n,k} for some fixed α ≤ 1 − ε and sufficiently large k.

read the original abstract

Nikiforov conjectured that, for every fixed $k\ge2$ and all sufficiently large $n$, the unique $n$-vertex $C_{2k+2}$-free graph with maximum adjacency spectral radius is $S^+_{n,k}$, where $S_{n,k}=K_k\vee\overline K_{n-k}$ and $S^+_{n,k}$ is obtained from $S_{n,k}$ by adding one edge inside the independent part. Cioab\u{a}, Desai and Tait proved this conjecture for $n\ge k^{O(k)}$. Later, Li and Ning raised the problem of determining the optimal exponent $\gamma=\gamma(k)$ such that the same conclusion holds for $n\ge \Omega(k^{\gamma(k)})$. We prove a stronger uniform theorem for Nikiforov's matrices $A_\alpha(G)=\alpha D(G)+(1-\alpha)A(G)$. More precisely, for every $\epsilon>0$ there are constants $C_\epsilon$ and $k_\epsilon$ such that for all $0\le\alpha\le1-\epsilon$, $k\ge k_\epsilon$ and $n\ge C_\epsilon k$, every $n$-vertex $C_{2k+2}$-free graph $G$ satisfies $\rho_\alpha(G)\le\rho_\alpha(S^+_{n,k})$, with equality if and only if $G\cong S^+_{n,k}$. In particular, the case when $\alpha=0$ answers the problem of Li and Ning in the linear range, and the $A_\alpha$-spectral even-cycle threshold is linear in $k$, uniformly for all $\alpha$ bounded away from $1$. Our proof introduces a weighted rooted Erd\H{o}s--Gallai type path lemma, which may be of independent interest in Perron-vector methods for spectral extremal graph problems. The same method also yields asymptotically tight $A_\alpha$-spectral bounds for two local forbidden-subgraph families, namely $(K_1\vee P_\ell)$-free graphs and $F_s$-free graphs, where $F_s$ denotes the friendship graph.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proves a uniform strengthening of Nikiforov's conjecture on the maximum A_α-spectral radius of C_{2k+2}-free graphs: for every ε>0 there exist C_ε, k_ε such that whenever 0≤α≤1-ε, k≥k_ε and n≥C_ε k, every n-vertex C_{2k+2}-free G satisfies ρ_α(G)≤ρ_α(S^+_{n,k}), with equality if and only if G≅S^+_{n,k}. The result also resolves the linear-range question of Li-Ning for α=0 and yields analogous tight bounds for (K_1∨P_ℓ)-free and F_s-free graphs. The proof rests on a new weighted rooted Erdős-Gallai-type path lemma combined with Perron-vector analysis.

Significance. If the new lemma holds, the result supplies the first uniform linear threshold (in k) that works simultaneously for all α bounded away from 1, improving the super-linear n≥k^{O(k)} bound of Cioabă-Desai-Tait. The lemma itself is presented as potentially reusable in other Perron-vector arguments; the paper also ships explicit equality cases and asymptotic tightness statements.

major comments (2)
  1. [§3, §4] §3 (the weighted rooted Erdős-Gallai lemma): the statement claims a uniform bound on the weighted length of paths in C_{2k+2}-free graphs that is independent of α (for α≤1-ε). The subsequent application in §4 to the Perron vector of an extremal graph appears to require that the weight function w(v) derived from the eigenvector satisfies the lemma's hypotheses exactly; a concrete verification that the eigenvector weights remain admissible for all α in [0,1-ε] is needed to confirm the uniformity claim.
  2. [Theorem 1.1] Theorem 1.1 (main result): the equality case asserts that equality holds only for S^+_{n,k}. The proof sketch indicates that any graph achieving the bound must be a blow-up or join with a single extra edge; however, the argument that no other C_{2k+2}-free graph can match the spectral radius when n is only linear in k relies on the path lemma giving a strict inequality unless the structure is exactly S^+_{n,k}. A short explicit check that the lemma produces a strict deficit for any other candidate (e.g., S_{n,k} itself or a different join) would strengthen the equality statement.
minor comments (2)
  1. [§3] The notation for the weighted path length in the new lemma is introduced without an explicit comparison table to the classical Erdős-Gallai bound; adding one sentence relating the two would help readers.
  2. [Figure 1] Figure 1 (extremal graphs) labels S^+_{n,k} but does not indicate the location of the added edge; a small arrow or caption clarification would remove ambiguity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, positive assessment, and recommendation for minor revision. The two major comments can be addressed by adding short clarifying paragraphs; we outline the responses below.

read point-by-point responses

  1. Referee: [§3, §4] §3 (the weighted rooted Erdős-Gallai lemma): the statement claims a uniform bound on the weighted length of paths in C_{2k+2}-free graphs that is independent of α (for α≤1-ε). The subsequent application in §4 to the Perron vector of an extremal graph appears to require that the weight function w(v) derived from the eigenvector satisfies the lemma's hypotheses exactly; a concrete verification that the eigenvector weights remain admissible for all α in [0,1-ε] is needed to confirm the uniformity claim.

    Authors: The weighted rooted Erdős-Gallai lemma in §3 is stated and proved for any non-negative weight function w satisfying the given normalization and support conditions; its bound is independent of α precisely because the proof uses only these properties together with the C_{2k+2}-freeness. For the Perron vector x of A_α(G) with 0≤α≤1-ε, the associated weights w(v)=x(v)^2 satisfy the hypotheses uniformly: non-negativity is immediate, the total weight is 1, and the minimum positive weight is bounded below by a positive constant depending only on ε (via the standard eigenvector bound ||x||_∞/||x||_2 ≤ √(2/(1-α)) and the fact that the graph is connected). We will insert a short verification paragraph at the beginning of §4 that records these uniform bounds explicitly, thereby confirming that the lemma applies verbatim for every α in the stated range. revision: yes

  2. Referee: [Theorem 1.1] Theorem 1.1 (main result): the equality case asserts that equality holds only for S^+_{n,k}. The proof sketch indicates that any graph achieving the bound must be a blow-up or join with a single extra edge; however, the argument that no other C_{2k+2}-free graph can match the spectral radius when n is only linear in k relies on the path lemma giving a strict inequality unless the structure is exactly S^+_{n,k}. A short explicit check that the lemma produces a strict deficit for any other candidate (e.g., S_{n,k} itself or a different join) would strengthen the equality statement.

    Authors: We agree that an explicit check strengthens the equality claim. In the proof of Theorem 1.1, once the weighted-path lemma is applied to the Perron vector, any graph that is not isomorphic to S^+_{n,k} necessarily admits a strictly shorter weighted path (by at least a positive constant depending only on ε and k), which forces ρ_α(G) ≤ ρ_α(S^+_{n,k}) - δ for some δ>0. This already rules out S_{n,k} (which lacks the extra edge and therefore realizes a shorter maximum weighted path) and any other join or blow-up structure. We will add a one-paragraph remark immediately after the proof that records this strict-deficit calculation for the two most natural alternative candidates, confirming that equality forces the precise structure of S^+_{n,k}. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The central result rests on a newly introduced and proved weighted rooted Erdős–Gallai-type path lemma combined with standard Perron-vector analysis. No step reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation chain; the lemma is external to the target bound and the derivation remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof is a mathematical argument that introduces one new lemma; it rests on standard facts about nonnegative matrices and spectral radii rather than fitted constants or new postulated objects.

axioms (1)
  • standard math Standard properties of the spectral radius of nonnegative symmetric matrices and the Perron-Frobenius theorem for irreducible nonnegative matrices
    Invoked implicitly when comparing rho_alpha(G) to rho_alpha(S^+_{n,k}) and when analyzing the eigenvector.

pith-pipeline@v0.9.1-grok · 5940 in / 1351 out tokens · 24916 ms · 2026-06-27T21:57:54.281209+00:00 · methodology

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

36 extracted references

  1. [1]

    Babai and B

    L. Babai and B. Guiduli. Spectral extrema for graphs: the Zarankiewicz problem.Electron. J. Combin., 16(1):Research Paper 123, 2009

    2009

  2. [2]

    Byrne, D

    J. Byrne, D. N. Desai, and M. Tait. A general theorem in spectral extremal graph theory. To appear in Trans. Amer. Math. Soc., 2025

    2025

  3. [3]

    M.-Z. Chen, S. Li, Z.-M. Li, Y. Yu, and X.-D. Zhang. AnAα-spectral Erdős–Sós theorem.Electron. J. Combin., 30(3):Paper No. 3.34, 2023

    2023

  4. [4]

    Chen, A.-M

    M.-Z. Chen, A.-M. Liu, and X.-D. Zhang. On theAα-spectral radius of graphs without linear forests.Appl. Math. Comput., 450:128005, 2023

    2023

  5. [5]

    S. M. Cioabă, D. N. Desai, and M. Tait. The spectral radius of graphs with no odd wheels. European J. Combin., 99:103420, 2022

    2022

  6. [6]

    S. M. Cioabă, D. N. Desai, and M. Tait. A spectral Erdős–Sós theorem.SIAM J. Discrete Math., 37(3):2228–2239, 2023

    2023

  7. [7]

    S. M. Cioabă, D. N. Desai, and M. Tait. The spectral even cycle problem.Combinatorial Theory, 4(1):Paper No. 10, 2024

    2024

  8. [8]

    Dvořák and B

    Z. Dvořák and B. Mohar. Spectral radius of finite and infinite planar graphs and of graphs of bounded genus.Journal of Combinatorial Theory, Series B, 100(6):729–739, 2010

    2010

  9. [9]

    Erdős and T

    P. Erdős and T. Gallai. On maximal paths and circuits of graphs.Acta Math. Acad. Sci. Hungar., 10:337–356, 1959

    1959

  10. [10]

    Füredi and M

    Z. Füredi and M. Simonovits. The history of degenerate (bipartite) extremal graph problems. In Erdős Centennial, volume 25 ofBolyai Soc. Math. Stud., pages 169–264. János Bolyai Math. Soc., 2013

    2013

  11. [11]

    Li and B

    B. Li and B. Ning. Eigenvalues and cycles of consecutive lengths.J. Graph Theory, 103(3):486–492, 2023

    2023

  12. [12]

    Li and B

    B. Li and B. Ning. Stability of Woodall’s theorem and spectral conditions for large cycles.Electron. J. Combin., 30(1):Paper No. 1.39, 2023

    2023

  13. [13]

    Li and Y

    S. Li and Y. Yu. OnAα spectral extrema of graphs forbidding even cycles.Linear Algebra Appl., 668:11–27, 2023

    2023

  14. [14]

    S. Li, Y. Yu, and H. Zhang. AnAα-spectral Erdős–Pósa theorem.Discrete Math., 346(9):113494, 2023

    2023

  15. [15]

    Liu and B

    L. Liu and B. Ning. Unsolved problems in spectral graph theory.arXiv preprint arXiv:2305.10290, 2023. 20

    arXiv 2023

  16. [16]

    W. Mantel. Problem 28.Wiskundige Opgaven met de Oplossingen, 10:60–61, 1907

    1907

  17. [17]

    Nikiforov

    V. Nikiforov. Bounds on graph eigenvalues II.Linear Algebra Appl., 427(2–3):183–189, 2007

    2007

  18. [18]

    Nikiforov

    V. Nikiforov. A spectral condition for odd cycles in graphs.Linear Algebra Appl., 428(7):1492–1498, 2008

    2008

  19. [19]

    Nikiforov

    V. Nikiforov. The spectral radius of graphs without paths and cycles of specified length.Linear Algebra Appl., 432(9):2243–2256, 2010

    2010

  20. [20]

    Nikiforov

    V. Nikiforov. Merging theA- and Q-spectral theories.Appl. Anal. Discrete Math., 11(1):81–107, 2017

    2017

  21. [21]

    Nikiforov and X

    V. Nikiforov and X. Yuan. Maxima of theQ-index: forbidden even cycles.Linear Algebra Appl., 471:636–653, 2015

    2015

  22. [22]

    E. Nosal. Eigenvalues of graphs. Master’s thesis, University of Calgary, 1970

    1970

  23. [23]

    R. P. Stanley. A bound on the spectral radius of graphs withe edges.Linear Algebra Appl., 87:267–269, 1987

    1987

  24. [24]

    M. Tait. The Colin de Verdière parameter, excluded minors, and the spectral radius.Journal of Combinatorial Theory, Series A, 166:42–58, 2019

    2019

  25. [25]

    Tait and J

    M. Tait and J. Tobin. Three conjectures in extremal spectral graph theory.J. Combin. Theory Ser. B, 126:137–161, 2017

    2017

  26. [26]

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

    1941

  27. [27]

    Verstraëte

    J. Verstraëte. On arithmetic progressions of cycle lengths in graphs.Combin. Probab. Comput., 9(4):369–373, 2000

    2000

  28. [28]

    Verstraëte

    J. Verstraëte. Extremal problems for cycles in graphs. InRecent Trends in Combinatorics, volume 159 ofIMA Vol. Math. Appl., pages 83–116. Springer, Cham, 2016

    2016

  29. [29]

    H. J. Voss and C. Zuluaga. Maximale gerade und ungerade kreise in graphen, I.Wissenschaftliche Zeitschrift der Technischen Hochschule Ilmenau, 23(4):57–70, 1977

    1977

  30. [30]

    J. Wang, L. Kang, and Y. Xue. On a conjecture of spectral extremal problems.J. Combin. Theory Ser. B, 159:20–41, 2023

    2023

  31. [31]

    H. S. Wilf. Spectral bounds for the clique and independence numbers of graphs.J. Combin. Theory Ser. B, 40(1):113–117, 1986

    1986

  32. [32]

    D. R. Woodall. Maximal circuits of graphs. I.Acta Math. Acad. Sci. Hungar., 28(1–2):77–80, 1976

    1976

  33. [33]

    Spectralextremaofgraphs: Forbiddenhexagon.Discrete Math., 343(10):112028, 2020

    M.ZhaiandH.Lin. Spectralextremaofgraphs: Forbiddenhexagon.Discrete Math., 343(10):112028, 2020

    2020

  34. [34]

    M. Zhai, B. Wang, and L. Fang. The spectral Turán problem about graphs with no6-cycle.Linear Algebra Appl., 590:22–31, 2020

    2020

  35. [35]

    W. Zhang. The spectral radius, maximum average degree and cycles of consecutive lengths of graphs.Graphs Combin., 40(2):Paper No. 32, 2024

    2024

  36. [36]

    W. Zhang. Spectral skeletons and applications.arXiv preprint arXiv:2501.14218, 2025. 21

    arXiv 2025