Kemeny's constant via matrix compression and eigenvalue interlacing

A. Abiad, Á. Carmona, A. M. Encinas, E. Ghorbani, M. J. Jiménez, Á. Samperio

arXivarxiv/2609.17481Sep 15, 2026math.COscore 0

Kemeny's constant quantifies the expected time for a random walk to reach a randomly chosen vertex, capturing global properties of a Markov chain. We develop a matrix-analytic framework for bounding Kemeny's constant of a finite connected weighted graph using degree-weighted compressions of the normalized adjacency matrix, pinching inequalities, and eigenvalue interlacing. Our main partition theorem gives lower bounds in terms of the compressed spectrum, with complete equality characterizations, and converts structural graph information into spectrally computable estimates. For instance,…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2609.17481
curl -X POST /api/v1/records/arxiv/2609.17481/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.17481/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'