Answers are grounded in this paper and cite their sources.
For the simple random walk on a connected graph with n vertices, let τ₀ be Kemeny's constant and τ₂ the relaxation time. Aldous and Fill conjectured that the maxima of both quantities over all connected n-vertex graphs are asymptotic to n³/54. We prove this. Every connected graph on n vertices satisfies τ₂≤τ₀≤ n³/54+37/8n5/2, and the barbell made of two cliques on about $n/3$ vertices joined by a path on about $n/3$ vertices has τ₂≥(n-2)(n-5)(n+3)/54. The upper bound comes from the electrical formula for Kemeny's constant: the vertices near high-degree vertices are grouped into components of small total diameter, the rest of the graph is compared with a tree, and each edge of the tree is shown to contribute at most s²/8 plus a lower-order term, where s is the number of grouped vertices.
No takes yet. Share an insight, caveat, or question.
Yitzchak Shmalo (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: