Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs

Consider the switch chain on the set of d-regular bipartite graphs on n vertices with 3 ≤ d≤ n^c, 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 O_d(nlog n). We show that both results are optimal. The Poincaré inequality implies that in the regime 3 ≤ d≤ n^c the mixing time of the switch chain is at most O((nd) ²log (nd)) , improving on the previously known bound O((nd) ¹³log (nd)) due to Kannan et al. (Rand Struct Algorithm 14(4):293–308, 1999) and O(n⁷d¹⁸log (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 ²n) 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.