## Abstract

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) ^{2}log (nd)) , improving on the previously known bound O((nd) ^{13}log (nd)) due to Kannan et al. (Rand Struct Algorithm 14(4):293–308, 1999) and O(n^{7}d^{18}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 ^{2}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.

Original language | English (US) |
---|---|

Pages (from-to) | 89-184 |

Number of pages | 96 |

Journal | Probability Theory and Related Fields |

Volume | 185 |

Issue number | 1-2 |

DOIs | |

State | Published - Feb 2023 |

## Keywords

- Mixing/relaxation time
- Poincaré and log-Sobolev inequalities
- Random regular graph
- Switch chain

## ASJC Scopus subject areas

- Analysis
- Statistics and Probability
- Statistics, Probability and Uncertainty