Local Tur\'an inequalities for walks and the spectral radius

Feng Liu; Qi Wu; Shuang Sun; Yan Wang

arxiv: 2605.02191 · v2 · pith:QNALD3G3new · submitted 2026-05-04 · 🧮 math.CO

Local Tur\'an inequalities for walks and the spectral radius

Feng Liu , Shuang Sun , Yan Wang , Qi Wu This is my paper

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

Nikiforov's well-known spectral Tur\'an inequality for walks states that, for every graph $G$ with clique number $\omega(G)$, $\lambda^r(G)\le w_r(G)(1-1/\omega(G))$, where $\lambda(G)$ is the largest eigenvalue of the adjacency matrix of $G$, and $w_r(G)$ is the number of walks with $r$ vertices in $G$. For $r=1$, this is Wilf's inequality; for $r=2$, it gives Nikiforov's spectral Tur\'an theorem. Recently, Liu and Ning proved local versions of these two inequalities, strengthening both Wilf's inequality and Nikiforov's spectral Tur\'an theorem. It is natural to ask whether Nikiforov's spectral Tur\'an inequality for walks also admits a local strengthening. Motivated by this question, Kannan, Kumar, and Pragada conjectured the vertex-local bound $\lambda^r(G)\le \sum_{v\in V(G)} w_r(v)(1-1/c_G(v))$, where $w_r(v)$ denotes the number of walks with $r$ vertices starting at $v$, and $c_G(v)$ is the maximum order of a clique containing $v$. This conjecture is important because it gives the most natural local form of Nikiforov's spectral Tur\'an inequality for walks. In this paper, we confirm this conjecture. More precisely, for $r\ge 2$, we prove the stronger edge-local inequality $$\lambda^r(G) \le \sum_{uv\in E(G)} \frac{c_G(uv)-1}{c_G(uv)} \bigl(w_{r-1}(u)+w_{r-1}(v)\bigr),$$ where $c_G(uv)$ is the maximum order of a clique containing the edge $uv$. Our result implies Nikiforov's spectral Tur\'an inequality for walks and unifies several local spectral extremal results of Liu and Ning. We also determine all extremal graphs for both the edge-local and vertex-local inequalities. The main new ingredient is a Markov-chain estimate whose transition matrix is constructed from a Perron vector of $A(G)$; this estimate carries the local edge coefficient through walks of arbitrary length.

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.