Mixing times of switch chains improve with high dimensional expansion
Mixing Times of Switch Chains via High-Dimensional Expansion
Discrete Mathematics
Summary
This paper studies how quickly a random process called the switch chain reaches a balanced state when rearranging edges in a graph with fixed degrees. The authors use a new geometric viewpoint and mathematical tools from high-dimensional expansion to analyze the process more precisely. They prove that the chain stabilizes quickly in many cases, including for graphs with irregular degrees, solving an old open problem. This means we can efficiently sample different graph arrangements uniformly, which has applications in network modeling and beyond.
What this means in practice
- •For network analysts: Efficiently generate random graphs matching degree constraints to test network algorithms.
- •For data modelers: Sample diverse network configurations that fit fixed degree data for robust statistical analysis.
A theory result. No direct application yet.
Authors
Sawyer Jack Robertson
Abstract
The switch chain is a Markov chain defined on the set of labelled realizations of a given graphical degree sequence. At each step, a pair of vertex-disjoint edges is chosen at random and the process attempts to replace them with a uniformly chosen perfect matching of the same four vertices, rejecting any proposal that would create a multiple edge. The resulting process is reversible with respect to the uniform distribution on all realizations. We investigate the mixing time of this chain by viewing realizations as the facets of a simplicial complex and studying a variant of the original process called the simplicial switch chain, which we analyze using tools from the theory of high-dimensional expansion. Our technical contributions include a proof that links of faces of sufficiently high codimension are strong spectral expanders and a comparison between the Dirichlet energies of large block updates and two-edge updates. Our main result is an $O(Δ^{2}m\log m)$ bound on the mixing time of both simplicial and classical switch chains whenever $m\ge CΔ^{8}$, where $m$ is the number of edges, $Δ$ is the maximum prescribed degree, and $C>0$ is an absolute constant. For sequences on $n$ vertices with fixed maximum degree, this proves that the chain mixes in $O(n\log n)$ steps, resolving a longstanding conjecture of Cooper, Dyer, and Greenhill and extending its conclusion to irregular degree sequences.