Consider the switch chain on the set of d-regular bipartite graphs on n vertices with 3 ≤ d≤ nc, for a small universal constant c> 0. We prove that the chain satisfies a Poincaré inequality with a constant of order O(nd); moreover, when d is fixed, we establish a log-Sobolev inequality for the chain with a constant of order Od(nlog n). We show that both results are optimal. The Poincaré inequality implies that in the regime 3 ≤ d≤ nc the mixing time of the switch chain is at most O((nd) 2log (nd)) , improving on the previously known bound O((nd) 13log (nd)) due to Kannan et al. (Rand Struct Algorithm 14(4):293–308, 1999) and O(n7d18log (nd)) obtained by Dyer et al. (Sampling hypergraphs with given degrees (preprint). arXiv:2006.12021). The log-Sobolev inequality that we establish for constant d implies a bound O(nlog 2n) on the mixing time of the chain which, up to the log n factor, captures a conjectured optimal bound. Our proof strategy relies on building, for any fixed function on the set of d-regular bipartite simple graphs, an appropriate extension to a function on the set of multigraphs given by the configuration model. We then establish a comparison procedure with the well studied random transposition model in order to obtain the corresponding functional inequalities. While our method falls into a rich class of comparison techniques for Markov chains on different state spaces, the crucial feature of the method—dealing with chains with a large distortion between their stationary measures—is a novel addition to the theory.
- Mixing/relaxation time
- Poincaré and log-Sobolev inequalities
- Random regular graph
- Switch chain
ASJC Scopus subject areas
- Statistics and Probability
- Statistics, Probability and Uncertainty