The Maximum Commute Time of Regular Graphs
For a connected simple regular graph $G$, let $τ(G)$ be the maximum commute time for simple random walk, and let $t_n$ be the maximum of $τ(G)$ over all such graphs of order $n$. Aldous and Fill conjectured that $t_n\sim3n^2/2$. We determine $t_n$ exactly and classify all maximizers for every even $n\geq10$ and every odd $n\geq15$; both thresholds are best possible. The maximizers are cubic block chains joined by bridges at even orders and quartic block chains joined at cut vertices at odd orders. The exact formulas specify the linear corrections according to the order modulo four and five,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.25800
curl -X POST /api/v1/records/arxiv/2610.25800/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.25800/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'