arxiv: 2605.02191 · v1 · submitted 2026-05-04 · 🧮 math.CO

Recognition: 2 theorem links

· Lean Theorem

A local Tur\'an inequality for walks and the spectral radius

Feng Liu , Shuang Sun , Yan Wang , Qi Wu

Authors on Pith no claims yet

Pith reviewed 2026-05-08 18:49 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C5005C35

keywords spectral radiusTurán inequalitywalks in graphslocal clique numberextremal graph theoryMarkov chainPerron vectoradjacency matrix

0 comments

The pith

For any graph G and integer r at least 1, the spectral radius to the power r is at most the sum over vertices of the number of r-walks from each vertex times one minus the reciprocal of its largest clique size.

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

The paper proves an inequality that bounds the r-th power of the spectral radius of any finite simple graph by a sum that weights each vertex's r-walk count by the fraction (c(v) - 1)/c(v), where c(v) is the size of the largest clique containing v. This result confirms a conjecture of Kannan, Kumar, and Pragada while strengthening an earlier walk inequality of Nikiforov. It also unifies the localized Wilf theorem and the degree-local Turán inequality into one statement. The argument uses the stationary distribution of a Markov chain built from the Perron vector of the adjacency matrix together with a weighted local spectral Turán theorem, and it identifies all graphs that achieve equality.

Core claim

For every finite simple graph G and every integer r ≥ 1, λ₁(G)^r ≤ ∑_{v∈V(G)} w_r(v) (c_G(v)−1)/c_G(v), where w_r(v) counts the walks on r vertices that begin at v and c_G(v) is the order of the largest clique containing v. This confirms the conjecture of Kannan, Kumar, and Pragada. The proof proceeds by constructing a Markov chain whose transition matrix comes from a Perron vector of the adjacency matrix A(G), invoking a weighted local spectral Turán theorem on that chain, and characterizing the extremal graphs.

What carries the argument

The stationary distribution of a Markov chain whose transition probabilities are derived from a Perron vector of the adjacency matrix, combined with a weighted local spectral Turán theorem that supplies the clique-size weighting.

If this is right

Nikiforov's walk inequality is strengthened because the new right-hand side is at least as large as the earlier one.
The localized Wilf theorem and the degree-local Turán inequality of Liu and Ning both follow as special cases.
All graphs attaining equality in the inequality are completely determined.
The result supplies a uniform spectral bound that incorporates local clique information at every vertex.

Where Pith is reading between the lines

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

The same Markov-chain technique might yield local versions of other spectral inequalities, such as those involving the number of closed walks.
Because the bound is local, it could be used to derive vertex-wise estimates that improve global bounds on chromatic number or clique number when the graph is far from regular.
Testing the inequality on random graphs or on graphs with known clique distributions would give a practical way to check how tight the bound is away from the extremal cases.

Load-bearing premise

The weighted local spectral Turán theorem must hold for the particular weighting induced by the Markov chain's stationary distribution.

What would settle it

A concrete counterexample would be any graph G and integer r where λ₁(G)^r exceeds the sum over v of w_r(v) times (c_G(v)−1)/c_G(v), or a weighting for which the auxiliary weighted local spectral Turán theorem fails.

read the original abstract

For a vertex $v$, let $c_G(v)$ be the order of the largest clique containing $v$, and let $w_r(v)$ be the number of walks with $r$ vertices starting at $v$. We prove that, for every finite simple graph $G$ and every integer $r\ge 1$, \begin{flalign*} \lambda_1(G)^r \le \sum_{v\in V(G)} w_r(v)\frac{c_G(v)-1}{c_G(v)}. \end{flalign*} This confirms a conjecture of Kannan, Kumar, and Pragada. It strengthens Nikiforov's walk inequality and extends, in a unified form, the localized Wilf theorem and the degree-local Tur\'an inequality of Liu and Ning. The proof is based on the stationary distribution of a Markov chain whose transition matrix is constructed from a Perron vector of $A(G)$, together with a weighted local spectral Tur\'an theorem. We determine all the extremal graphs.

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.

Desk Editor's Note private letter to a colleague

This paper proves the Kannan-Kumar-Pragada conjecture with a Markov-chain argument and unifies several earlier walk and local Turán bounds as corollaries.

read the letter

The punchline is that the authors deliver the first proof of the conjectured inequality λ₁(G)^r ≤ ∑ w_r(v) (c_G(v)−1)/c_G(v) for every graph and r ≥ 1. They also show it recovers Nikiforov’s walk bound, the localized Wilf theorem, and the Liu-Ning degree-local version in one statement, while pinning down the equality cases as complete graphs and certain blow-ups. The argument works for disconnected graphs by restricting to the component carrying the largest eigenvalue. That is the concrete advance. The proof route is straightforward once you accept the auxiliary weighted local spectral Turán theorem they establish in Section 3. They construct a reversible Markov chain from the Perron vector x of the adjacency matrix, with transitions P_ij = A_ij x_j / (λ x_i), take its stationary distribution π, and bound the one-step growth of the weighted walk measure using the local clique number at each vertex. The steps line up with standard Perron-Frobenius and stationary-distribution facts, and there is no circularity or hidden fitting. The only point worth a referee’s extra look is the weighted local Turán theorem itself; its statement and proof are supplied, but the weighting must be checked against all the edge cases that arise from the Perron vector. Nothing else looks fragile. This is for spectral graph theorists who care about Turán-type problems phrased in terms of walks or local clique orders. Anyone who has seen the earlier conjectures or the Nikiforov and Liu-Ning inequalities will get immediate value from the unification. The paper is coherent on its own terms and supplies enough detail for verification, so it deserves a serious referee.

Referee Report

0 major / 2 minor

Summary. The paper proves that for every finite simple graph G and integer r ≥ 1, λ₁(G)^r ≤ ∑_{v∈V(G)} w_r(v) ⋅ (c_G(v)−1)/c_G(v), where w_r(v) counts walks with r vertices starting at v and c_G(v) is the order of the largest clique containing v. This confirms the conjecture of Kannan, Kumar, and Pragada. The proof constructs a reversible Markov chain from the Perron vector x of the adjacency matrix A(G) with transitions P_{ij} = A_{ij} x_j / (λ x_i), derives the stationary distribution π, and applies a weighted local spectral Turán theorem (proved in §3) to bound the one-step growth of the weighted walk measure. The argument restricts to the component achieving λ₁ for disconnected graphs and characterizes equality cases as complete graphs and certain blow-ups. It strengthens Nikiforov's walk inequality and unifies localized Wilf and degree-local Turán results.

Significance. If the result holds, it supplies a sharp local refinement of spectral Turán theory that directly incorporates clique information at each vertex. The Markov-chain approach via the Perron vector yields a parameter-free derivation and explicitly identifies extremal graphs, which strengthens the paper's contribution beyond the conjecture confirmation. The weighted local spectral Turán theorem in §3 appears to be a reusable technical tool.

minor comments (2)

§2, definition of w_r(v): the phrase 'number of walks with r vertices starting at v' is standard but should be explicitly equated to the number of walks of length r−1 (i.e., w_r(v) = (A^{r−1} 1)_v) to avoid any ambiguity when r=1.
§4, equality cases: the description of the blow-up graphs achieving equality should include a short explicit construction or reference to the precise family (e.g., complete multipartite graphs with equal part sizes) so that readers can immediately verify the equality condition.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our results, the assessment of their significance, and the recommendation to accept the manuscript.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper establishes its main inequality by first constructing a reversible Markov chain from the Perron vector of A(G) and then proving a weighted local spectral Turán theorem internally in Section 3. The target bound on λ₁(G)^r follows by applying this theorem to control the one-step growth of the weighted walk measure w_r(v) using the local clique number c_G(v). All supporting ingredients (Perron-Frobenius, stationary distributions for reversible chains, and the auxiliary theorem) are either standard or derived within the manuscript rather than presupposed via self-citation or defined circularly in terms of the final result. Equality cases are identified explicitly, and the argument remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof rests on standard background results in linear algebra and Markov chains with no free parameters fitted to data and no newly postulated entities.

axioms (2)

standard math Perron-Frobenius theorem guaranteeing a positive eigenvector for the adjacency matrix of a connected graph
Used to construct the transition matrix of the Markov chain from the Perron vector.
standard math Existence and uniqueness of the stationary distribution for an irreducible finite-state Markov chain
Central to weighting the walk counts in the inequality.

pith-pipeline@v0.9.0 · 5481 in / 1408 out tokens · 33407 ms · 2026-05-08T18:49:01.194389+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

On spectral Tur\'an theorems: confirming a conjecture of Guiduli and two problems of Nikiforov
math.CO 2026-05 unverdicted novelty 8.0

The authors confirm Guiduli's spectral conjecture in strengthened form and prove that the spectral Turán threshold exactly detects the edge Turán threshold for all r and n, with equality cases.

Reference graph

Works this paper leans on

27 extracted references · 5 canonical work pages · cited by 1 Pith paper

[1]

Adak and L

R. Adak and L. S. Chandran, Vertex-based localization of Turán’s theorem, arXiv:2504.02806, 2025

work page arXiv 2025
[2]

Berman and R

A. Berman and R. J. Plemmons,Nonnegative Matrices in the Mathematical Sciences, Classics in Applied Mathematics, vol. 9, SIAM, Philadelphia, 1994

1994
[3]

Bollobás and V

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

2007
[4]

Bradač,A generalization of Turán’s theorem, arXiv:2205.08923

D. Bradač, A generalization of Turán’s theorem, arXiv:2205.08923, 2022

work page arXiv 2022
[5]

A. E. Brouwer and W. H. Haemers,Spectra of Graphs, Universitext, Springer, New York, 2012

2012
[6]

D. M. Cvetković, M. Doob and H. Sachs,Spectra of Graphs: Theory and Application, Academic Press, New York, 1980

1980
[7]

M.D.DonskerandS.R.S.Varadhan, Onavariationalformulafortheprincipaleigenvalue for operators with maximum principle,Proc. Nat. Acad. Sci. U.S.A.72 (1975), 780–783

1975
[8]

Elphick, W

C. Elphick, W. Linz and P. Wocjan, Two conjectured strengthenings of Turán’s theorem, Linear Algebra Appl.684 (2024), 23–36

2024
[9]

C. S. Edwards and C. H. Elphick, Lower bounds for the clique and chromatic numbers of a graph,Discrete Appl. Math.5 (1983), 51–64

1983
[10]

Friedland and S

S. Friedland and S. Karlin, Some inequalities for the spectral radius of non-negative matrices and applications,Duke Math. J.42 (1975), no. 3, 459–490

1975
[11]

Hong, A bound on the spectral radius of graphs,Linear Algebra Appl.108 (1988), 135–139

Y. Hong, A bound on the spectral radius of graphs,Linear Algebra Appl.108 (1988), 135–139

1988
[12]

Hong, J.-L

Y. Hong, J.-L. Shu and K. Fang, A sharp upper bound of the spectral radius of graphs, J. Combin. Theory Ser. B81 (2001), 177–183

2001
[13]

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

work page arXiv 2025
[14]

Kirsch and J

R. Kirsch and J. D. Nir, A localized approach to generalized Turán problems,Electron. J. Combin.31 (2024), no. 3, Paper No. P3.34. 14

2024
[15]

Liu and B

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

work page arXiv 2025
[16]

Liu and B

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

2026
[17]

Li and B

B. Li and B. Ning, Localized and weighted versions of extremal problems, arXiv:2509.17055, 2025

work page arXiv 2025
[18]

D.MalecandC.Tompkins, Localizedversionsofextremalproblems,European J. Combin. 112 (2023), Paper No. 103715, 11 pp

2023
[19]

T. S. Motzkin and E. G. Straus, Maxima for graphs and a new proof of a theorem of Turán,Canad. J. Math.17 (1965), 533–540

1965
[20]

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), no. 2, 179–189

2002
[21]

Nikiforov, Walks and the spectral radius of graphs,Linear Algebra Appl.418 (2006), no

V. Nikiforov, Walks and the spectral radius of graphs,Linear Algebra Appl.418 (2006), no. 1, 257–268

2006
[22]

Nikiforov, Some new results in extremal graph theory, inSurveys in Combinatorics 2011, London Math

V. Nikiforov, Some new results in extremal graph theory, inSurveys in Combinatorics 2011, London Math. Soc. Lecture Note Ser., vol. 392, Cambridge Univ. Press, Cambridge, 2011, pp. 141–182

2011
[23]

Nosal,Eigenvalues of Graphs, Master’s thesis, University of Calgary, 1970

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

1970
[24]

Seneta,Non-negative Matrices and Markov Chains, Springer Series in Statistics, Springer, New York, 2006

E. Seneta,Non-negative Matrices and Markov Chains, Springer Series in Statistics, Springer, New York, 2006

2006
[25]

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

1987
[26]

Turán, Eine Extremalaufgabe aus der Graphentheorie,Mat

P. Turán, Eine Extremalaufgabe aus der Graphentheorie,Mat. Fiz. Lapok48 (1941), 436–452

1941
[27]

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

1986