A counterexample to a mixing-time conjecture for repeated averages on graphs
The repeated averages process is a stochastic averaging process on graphs whose mixing time is known for several structured families, but no general sharp expression is known for all connected graphs. It was conjectured that the $L^2\!\to\!L^1$ mixing time is of order $|E|\log n/λ_2$. We disprove this conjecture using the graph $G_n$ obtained by attaching one leaf to the complete graph $K_n$. We prove that $λ_2(G_n)=1$ and that \[ t_{\varepsilon,2\to1}(G_n)=Θ_{\varepsilon}(γ(G_n))=Θ_{\varepsilon}(n^2), \] with no additional $\log n$ factor. The example has a strongly localized Fiedler…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.21215
curl -X POST /api/v1/records/arxiv/2609.21215/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.21215/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'