PreprintarXiv licencearXiv
A counterexample to a mixing-time conjecture for repeated averages on graphs
Abstract
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 L2 → L1 mixing time is of order |E|log n/λ2. We disprove this conjecture using the graph Gn obtained by attaching one leaf to the complete graph Kn. We prove that λ2(Gn)=1 and that tε,2→1(Gn)=Θε(γ(Gn))=Θε(n2), with no additional log n factor. The example has a strongly localized Fiedler eigenvector: most of its squared L2 mass lies on the leaf, while the balancing mass is spread across the clique.
Related
- A Counterexample to the Alon-Krivelevich Conjecture and a New Lower Bound for Choosability of Bipartite Graphs
- A counterexample to a conjecture of Duncan on versal actions
- A Counterexample to the Eventual Stability Conjecture
- A non-klt counterexample to Shokurov's index conjecture
- A counterexample to the wrapping number conjecture
BibTeX
@misc{gupta2026counterexample,
title = {{A counterexample to a mixing-time conjecture for repeated averages on graphs}},
author = {Nikash Gupta},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.21215},
eprint = {2609.21215},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.21215},
}
RIS
TY - UNPB
TI - A counterexample to a mixing-time conjecture for repeated averages on graphs
AU - Nikash Gupta
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2609.21215
UR - https://arxiv.org/abs/2609.21215
AB - 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 → 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_ε,2→1(G_n)=Θ_ε(γ(G_n))=Θ_ε(n^2), with no additional log n factor. The example has a strongly localized Fiedler eigenvector: most of its squared L^2 mass lies on the leaf, while the balancing mass is spread across the clique.
ER -