pith. machine review for the scientific record. sign in

arxiv: 2605.05048 · v1 · submitted 2026-05-06 · 🧮 math.CO

Recognition: unknown

On spectral Tur\'an theorems: confirming a conjecture of Guiduli and two problems of Nikiforov

Lele Liu , Bo Ning
Authors on Pith no claims yet

Pith reviewed 2026-05-08 16:36 UTC · model grok-4.3

classification 🧮 math.CO
keywords spectral Turán theoremGuiduli conjectureNikiforov problemPerron eigenvectorTurán graphspectral radiusneighborhood spectral radius
0
0 comments X

The pith

If the spectral radius of G meets or exceeds that of the Turán graph T_r(n), then G is T_r(n) or some vertex has a neighborhood whose spectral radius exceeds the corresponding smaller Turán graph.

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

The paper proves a strengthened form of Guiduli's conjecture: reaching the spectral radius of the balanced complete r-partite graph T_r(n) forces the graph either to be exactly T_r(n) or to contain a vertex whose induced neighborhood exceeds the spectral radius of T_{r-1} on its degree number of vertices. When the spectral radius strictly exceeds the threshold, every vertex attaining the maximum entry in a nonnegative Perron eigenvector satisfies the neighborhood condition. The authors further show that the spectral inequality λ(G) < λ(T_r(n)) directly implies the strict edge inequality e(G) < e(T_r(n)), determining all equality cases, and that Nikiforov's least-eigenvalue bound on clique number recovers the classical statement of Turán's theorem.

Core claim

Let G be an n-vertex graph and T_r(n) the complete balanced r-partite graph on n vertices. If λ(G) ≥ λ(T_r(n)), then either G ≅ T_r(n) or there exists a vertex v such that λ(G[N(v)]) > λ(T_{r-1}(d(v))). When λ(G) > λ(T_r(n)), every maximum-entry vertex in any nonnegative Perron vector satisfies the neighborhood inequality. Moreover, λ(G) < λ(T_r(n)) implies e(G) < e(T_r(n)), and the equality cases are identified. Nikiforov's bound ω(G) ≥ 1 + 2e(G)/((n - d(G))(d(G) - λ_n(G))) implies the standard Turán theorem.

What carries the argument

The nonnegative Perron eigenvector of the adjacency matrix, used to locate vertices whose induced neighborhoods must satisfy an inductive spectral-radius inequality whenever the global spectral radius meets or exceeds the Turán threshold.

If this is right

  • The exact Turán edge threshold is recovered from the exact spectral threshold, with equality cases fully determined.
  • Nikiforov's least-eigenvalue lower bound on the clique number implies the concise form of Turán's theorem.
  • Every vertex of maximum Perron entry in a graph exceeding the spectral threshold has a neighborhood exceeding the smaller Turán spectral radius.

Where Pith is reading between the lines

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

  • The eigenvector localization technique may allow spectral conditions to substitute for direct edge counting in other Turán-type problems.
  • The neighborhood reduction suggests an inductive structure that could be tested on non-complete multipartite extremal graphs.
  • The results tighten the link between the largest eigenvalue and the classical edge-extremal function, making the spectral version a strict strengthening rather than an analogue.

Load-bearing premise

The argument requires that a nonnegative eigenvector for the largest eigenvalue exists and that its maximum entries correctly identify vertices whose local neighborhood spectral radii control the global extremal property.

What would settle it

A single graph G that is not isomorphic to T_r(n), satisfies λ(G) ≥ λ(T_r(n)), yet has λ(G[N(v)]) ≤ λ(T_{r-1}(d(v))) for every vertex v, would falsify the strengthened Guiduli claim.

read the original abstract

Let $G$ be an $n$-vertex graph, and let $\lambda(G)$ and $\lambda_n(G)$ denote the largest and smallest eigenvalues of its adjacency matrix. Write $e(G)$ for the number of edges of $G$, $d(G)=2e(G)/n$ for its average degree, and $T_r(n)$ for the $r$-partite Tur\'an graph on $n$ vertices. We prove four sharp results in spectral Tur\'an theory. First, we confirm Guiduli's spectral dense-neighborhood conjecture (1996) in a stronger form: if $\lambda(G)\ge \lambda(T_r(n))$, then either $G\cong T_r(n)$, or there exists a vertex $v$ such that $\lambda(G[N(v)]) > \lambda(T_{r-1}(d(v)))$. Moreover, when $\lambda(G)>\lambda(T_r(n))$, every vertex attaining the maximum entry in any nonnegative Perron eigenvector of $G$ has this property. Second, we answer a problem of Nikiforov (2009) by showing that the exact Tur\'an edge threshold is detected by the exact spectral threshold: for every $r\ge 2$ and every $n$, $\lambda(G)<\lambda(T_r(n))$, implying $e(G)<e(T_r(n)).$ Our proof also determines the equality cases. Third, we answer another question of Nikiforov (2009) by showing that his least-eigenvalue clique bound \[ \omega(G)\ge 1+\frac{2e(G)}{(n-d(G))(d(G)-\lambda_n(G))} \] does imply the concise form of Tur\'an's theorem. Finally, we discuss an open problem proposed by Ai et al. (2026) in \cite{ALNS26+}.

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 manuscript establishes four sharp results in spectral Turán theory. It confirms Guiduli's 1996 spectral dense-neighborhood conjecture in a stronger form: if λ(G) ≥ λ(T_r(n)), then either G ≅ T_r(n) or there exists v with λ(G[N(v)]) > λ(T_{r-1}(d(v))); moreover, when λ(G) > λ(T_r(n)), every maximum-entry vertex in a nonnegative Perron vector satisfies the neighborhood property. It resolves one Nikiforov (2009) problem by proving λ(G) < λ(T_r(n)) implies e(G) < e(T_r(n)), with equality cases. It resolves a second Nikiforov problem by showing his least-eigenvalue clique bound implies the concise Turán theorem. It also discusses an open problem of Ai et al. (2026).

Significance. If the proofs hold, the results are significant: they supply exact spectral thresholds that detect the Turán edge extremal number, furnish structural characterizations via Perron vectors, and confirm a long-standing conjecture with strengthened equality cases. The direct implication from spectral radius to edge count (without intermediate parameters) and the resolution of both Nikiforov questions represent concrete advances in spectral extremal graph theory.

major comments (2)
  1. [Main theorem on Guiduli conjecture (abstract and §3)] The stronger form of Guiduli's conjecture (abstract and main theorem) relies on nonnegative Perron vectors. For a disconnected graph the vector is supported only on the component(s) attaining λ(G); neighborhoods N(v) therefore lie entirely inside that component. The proof must explicitly reduce to the connected case or separately verify that any disconnected G with λ(G) ≥ λ(T_r(n)) is either isomorphic to T_r(n) or satisfies the neighborhood inequality inside its maximal component; otherwise the implication chain fails in full generality.
  2. [Proof of spectral-to-edge implication (likely §4)] The proof that λ(G) < λ(T_r(n)) implies e(G) < e(T_r(n)) (second main result) determines equality cases, but the derivation must be checked for its handling of the transition from the spectral hypothesis to the edge count; in particular, whether it uses the uniqueness of T_r(n) as the unique maximizer of λ among n-vertex graphs with the given number of edges.
minor comments (2)
  1. [Notation and abstract] Notation for the smallest eigenvalue is introduced as λ_n(G) in the abstract; ensure this symbol is used consistently in all statements involving the least-eigenvalue clique bound.
  2. [References] The reference to Ai et al. (2026) appears as a preprint or forthcoming work; confirm the citation details and arXiv number if available.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment point by point below and will incorporate clarifications to strengthen the exposition.

read point-by-point responses

  1. Referee: [Main theorem on Guiduli conjecture (abstract and §3)] The stronger form of Guiduli's conjecture (abstract and main theorem) relies on nonnegative Perron vectors. For a disconnected graph the vector is supported only on the component(s) attaining λ(G); neighborhoods N(v) therefore lie entirely inside that component. The proof must explicitly reduce to the connected case or separately verify that any disconnected G with λ(G) ≥ λ(T_r(n)) is either isomorphic to T_r(n) or satisfies the neighborhood inequality inside its maximal component; otherwise the implication chain fails in full generality.

    Authors: We appreciate the referee's observation on the disconnected case. Since λ(G) equals the spectral radius of its largest connected component and T_r(n) is connected, any disconnected G satisfying λ(G) ≥ λ(T_r(n)) has a principal component H with λ(H) ≥ λ(T_r(n)). The strengthened neighborhood property then applies directly to H (with N(v) ⊆ H), and G cannot be isomorphic to T_r(n). To make this reduction fully explicit, we will insert a short preliminary lemma at the beginning of Section 3 that reduces the general case to the connected case via the principal component. This preserves the statement and proof structure while addressing the concern. revision: yes

  2. Referee: [Proof of spectral-to-edge implication (likely §4)] The proof that λ(G) < λ(T_r(n)) implies e(G) < e(T_r(n)) (second main result) determines equality cases, but the derivation must be checked for its handling of the transition from the spectral hypothesis to the edge count; in particular, whether it uses the uniqueness of T_r(n) as the unique maximizer of λ among n-vertex graphs with the given number of edges.

    Authors: We thank the referee for requesting verification of the transition steps. Our argument in Section 4 proceeds by contraposition: if e(G) ≥ e(T_r(n)), then G contains a K_{r+1}-free subgraph with at least e(T_r(n)) edges, and the known spectral extremal result that T_r(n) uniquely maximizes λ among K_{r+1}-free n-vertex graphs yields λ(G) ≥ λ(T_r(n)). The uniqueness of this maximizer is indeed used to obtain the strict inequality and to classify equality cases. We have re-examined the derivation and it is correct, but we will add two clarifying sentences in the proof to explicitly flag the appeal to uniqueness and to spell out the transition from the spectral hypothesis to the edge count. revision: yes

Circularity Check

0 steps flagged

No circularity: results follow from Perron-Frobenius and standard spectral graph theory without self-referential reductions

full rationale

The paper states four results as direct implications from the spectral radius hypothesis λ(G) ≥ λ(T_r(n)) to structural conclusions (isomorphism or neighborhood spectral inequality) and edge-count comparisons. These rest on the Perron-Frobenius theorem for nonnegative matrices and the existence of a nonnegative eigenvector, both external to the paper. No parameter is fitted to data and then renamed as a prediction, no ansatz is smuggled via self-citation, and no uniqueness theorem is imported from the authors' prior work. The Guiduli conjecture confirmation and Nikiforov problem resolutions are presented as theorems proved from first principles in the manuscript, with equality cases determined explicitly. The derivation chain therefore remains self-contained and does not reduce any claimed result to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard results from linear algebra and graph theory rather than new postulates. No free parameters or invented entities are introduced.

axioms (2)
  • standard math Perron-Frobenius theorem for nonnegative irreducible matrices guarantees a positive eigenvector for the spectral radius.
    Invoked implicitly when discussing nonnegative Perron eigenvectors and maximum entries.
  • standard math The adjacency matrix of a simple undirected graph is symmetric and real, hence has real eigenvalues.
    Background fact used throughout spectral graph theory results.

pith-pipeline@v0.9.0 · 5644 in / 1480 out tokens · 51656 ms · 2026-05-08T16:36:50.043700+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

45 extracted references · 5 canonical work pages · 1 internal anchor

  1. [1]

    J. Ai, H. Lei, B. Ning, Y. Shi, Graph operations and a unified method for kinds of Tur´ an type problems on paths, cycles and matchings, to appear inCanad. J. Math.(2026), DOI: https://doi.org/10.4153/S0008414 X25101788. 1, 2, 17

    work page doi:10.4153/s0008414 2026

  2. [2]

    N. Alon, B. Sudakov, Bipartite subgraphs and the smallest eigenvalue,Combin. Probab. Comput.9(2000), no. 1, 1–12. 4

    2000

  3. [3]

    Bollob´ as, V

    B. Bollob´ as, V. Nikiforov, Cliques and the spectral radius,J. Combin. Theory Ser. B97 (2007), no. 5, 859–865. 2

    2007

  4. [4]

    Bollob´ as, A

    B. Bollob´ as, A. Thomason, Dense neighbourhoods and Tur´ an’s theorem,J. Combin. Theory Ser. B31(1981), no. 1, 111–114. 3

    1981

  5. [5]

    Bondy, Large dense neighbourhoods and Tur´ an theorem,J

    J.A. Bondy, Large dense neighbourhoods and Tur´ an theorem,J. Combin. Theory Ser. B34 (1983) 109–111. 3

    1983

  6. [6]

    Bondy, U.S.R

    J.A. Bondy, U.S.R. Murty, Graph Theory, Graduate Texts in Mathematics 244. Springer- Verlag, London, 2008. 5

    2008

  7. [7]

    Byrne, D.N

    J. Byrne, D.N. Desai, M. Tait, A general theorem in spectral extremal graph theory, to appear inTrans. Amer. Math. Soc.(2026), see also arXiv:2401.07266. 2

    work page arXiv 2026

  8. [8]

    D. M. Cardoso, H. Gomes, S. J. Pinheiro, TheH-join of arbitrary families of graphs – the universal adjacency spectrum,Linear Algebra Appl.,648(2022) 160–180. 16

    2022

  9. [9]

    Cioab˘ a, D.N

    S. Cioab˘ a, D.N. Desai, M. Tait, The spectral even cycle problem,Comb. Theory4 (2024), no. 1, Paper No. 10, 17 pp. 2

    2024

  10. [10]

    Cioab˘ a, L

    S. Cioab˘ a, L. Feng, M. Tait, X. Zhang, The maximum spectral radius of graphs without friendship subgraphs,Electron. J. Combin.27(2020), no. 4, Paper No. 4.22, 19 pp. 2

    2020

  11. [11]

    Cvetkovi´ c, M

    D.M. Cvetkovi´ c, M. Doob, H. Sachs, Spectra of Graphs, Academic Press, New York, 1980. 5

    1980

  12. [12]

    Erd˝ os, Some recent progress on extremal problems in graph theory, in: Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory and Computing, pp

    P. Erd˝ os, Some recent progress on extremal problems in graph theory, in: Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory and Computing, pp. 3–14, Utilitas Math., Winnipeg, 1975. 3

    1975

  13. [13]

    Erd˝ os, A.H

    P. Erd˝ os, A.H. Stone, On the structure of linear graphs,Bull. Amer. Math. Soc.52(1946), 1087–1091. 1 18

    1946

  14. [14]

    Erd˝ os, V.T

    P. Erd˝ os, V.T. S´ os, On a generalization of Tur´ an’s graph-theorem,Stud. Pure Math.pp. 181– 185, 1983. 3

    1983

  15. [15]

    Guiduli, Spectral Extrema for Graphs, Ph.D

    B. Guiduli, Spectral Extrema for Graphs, Ph.D. Thesis, University of Chicago, December

  16. [16]

    2, 3, 4, 14

    Available at http://people.cs.uchicago.edu/ laci/students. 2, 3, 4, 14

  17. [17]

    Hoffman, On eigenvalues and colorings of graphs, in: B

    A.J. Hoffman, On eigenvalues and colorings of graphs, in: B. Harris (ed.),Graph Theory and its Applications, Academic Press, New York, 1970, pp. 79–91. 4

    1970

  18. [18]

    Haemers, Interlacing eigenvalues and graphs,Linear Algebra Appl.226–228(1995), 593–616

    W.H. Haemers, Interlacing eigenvalues and graphs,Linear Algebra Appl.226–228(1995), 593–616. 4

    1995

  19. [19]

    Hansen, C

    P. Hansen, C. Lucas, Bounds and conjectures for the signless Laplacian index of graphs, Linear Algebra Appl.432(2010), 3319–3336. 4

    2010

  20. [20]

    M. R. Kannan, H. Kumar and S. Pragada, Localization of spectral Tur´ an-type theorems, arXiv:2512.01409, 2025. 2

    work page arXiv 2025

  21. [21]

    Y. Li, L. Feng, W. Liu, A survey on spectral conditions for some extremal graph problems, Adv. Math. (China),51(2) (2022) 193–258. 2

    2022

  22. [22]

    Y. Li, H. Liu, S. Zhang, More on Nosal’s spectral theorem: Books and 4-cycles,J. Combin. Theory Ser. B179(2026), 219–249. 2

    2026

  23. [23]

    Li and Y

    Y. Li and Y. Peng, Refinement on spectral Tur´ an’s theorem,SIAM J. Discrete Math.37 (2023), 2462–2485. 2

    2023

  24. [24]

    L. Liu, B. Ning, Unsolved problems in spectral graph theory,Oper. Res. Trans.27(2023), no. 4, 33–60. 2

    2023

  25. [25]

    L. Liu, B. Ning, Local properties of the spectral radius and Perron vector in graphs.J. Combin. Theory Ser. B176(2026), 241–253. 2

    2026

  26. [26]

    Liu and B

    L. Liu and B. Ning, A new spectral Tur´ an theorem for weighted graphs and consequences, arXiv:2510.26410, 2025. 2

    work page arXiv 2025

  27. [27]

    F. Liu, S. Sun, Y. Wang, Q. Wu, A local Tur´ an inequality for walks and the spectral radius, arXiv:2605.02191. 2

    work page internal anchor Pith review Pith/arXiv arXiv

  28. [28]

    M. Lu, F. Tian, H. Liu, Laplacian spectral bounds for clique and independence numbers of graphs,J. Combin. Theory Ser. B97(2007), 726–732. 4

    2007

  29. [29]

    Mantel, Vraagstuk XXVIII,Wiskundige Opgaven10(1907), 60–61

    W. Mantel, Vraagstuk XXVIII,Wiskundige Opgaven10(1907), 60–61. 1

    1907

  30. [30]

    McLeman, E

    C. McLeman, E. McNicholas, Spectra of coronae,Linear Algebra Appl.,435: 998–1007,

  31. [31]

    Nikiforov, Some inequalities for the largest eigenvalue of a graph,Combin

    V. Nikiforov, Some inequalities for the largest eigenvalue of a graph,Combin. Probab. Comput.11(2002) 179–189. 2 19

    2002

  32. [32]

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

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

    2007

  33. [33]

    Nikiforov, More spectral bounds on the clique and independence numbers,J

    V. Nikiforov, More spectral bounds on the clique and independence numbers,J. Combin. Theory Ser. B99(6) (2009) 819–826. 4

    2009

  34. [34]

    Nikiforov, A spectral Erd˝ os-Stone-Bollob´ as theorem, Combin

    V. Nikiforov, A spectral Erd˝ os-Stone-Bollob´ as theorem, Combin. Probab. Comput. 18 (2009), no. 3, 455–458. 2

    2009

  35. [35]

    Nikiforov, Some new results in extremal graph theory

    V. Nikiforov, Some new results in extremal graph theory. Surveys in combinatorics 2011, 141–181, London Math. Soc. Lecture Note Ser., 392, Cambridge Univ. Press, Cambridge,

    2011

  36. [36]

    Nikiforov, Tur´ an’s theorem implies Stanley’s bound,Discuss

    V. Nikiforov, Tur´ an’s theorem implies Stanley’s bound,Discuss. Math. Graph Theory40 (2020), no. 2, 601–605. 4

    2020

  37. [37]

    B. Ning, M. Zhai, Counting substructures and eigenvalues II: quadrilaterals. Electron. J. Combin. 32 (2025), no. 4, Paper No. 4.1, 15 pp. 2

    2025

  38. [38]

    B. Ning, M. Zhai, Counting substructures and eigenvalues I: triangles,European J. Combin. 110(2023), Paper No. 103685, 12 pp. 2

    2023

  39. [39]

    Nosal, Eigenvalues of Graphs, Master Thesis, University of Calgary, 1970

    E. Nosal, Eigenvalues of Graphs, Master Thesis, University of Calgary, 1970. 2

    1970

  40. [40]

    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. 1

    1966

  41. [41]

    Stanley, A bound on the spectral radius of graphs with e edges,Linear Algebra Appl

    R.P. Stanley, A bound on the spectral radius of graphs with e edges,Linear Algebra Appl. 87(1987), 267–269. 4

    1987

  42. [42]

    M. Tait, J. Tobin, Three conjectures in extremal spectral graph theory,J. Combin. Theory Ser. B126(2017), 137–161. 2

    2017

  43. [43]

    Tur´ an, On an extremal problem in graph theory,Mat

    P. Tur´ an, On an extremal problem in graph theory,Mat. Fiz. Lapok48(1941), 436–452. 1

    1941

  44. [44]

    J. Wang, L. Kang, Y. Xue, On a conjecture of spectral extremal problems,J. Combin. Theory Ser. B159(2023), 20–41. 2

    2023

  45. [45]

    Wilf, Spectral bounds for the clique and independence numbers of graphs,J

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

    1986