A counterexample to a mixing-time conjecture for repeated averages on graphs

Source 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 $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 eigenvector: most of its squared $L^2$ mass lies on the leaf, while the balancing mass is spread across the clique.