TY - JOUR

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

AU - Tikhomirov, Konstantin

AU - Youssef, Pierre

N1 - Funding Information:
The authors would like to thank Catherine Greenhill for bringing to their attention the paper []. This project was initiated when the first named author visited the second named author at New York University Abu Dhabi. Both authors would like to thank the institution for excellent working conditions. The first named author was partially supported by the Sloan Fellowship.
Funding Information:
The authors would like to thank Catherine Greenhill for bringing to their attention the paper [22 ]. This project was initiated when the first named author visited the second named author at New York University Abu Dhabi. Both authors would like to thank the institution for excellent working conditions. The first named author was partially supported by the Sloan Fellowship.
Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature.

PY - 2023/2

Y1 - 2023/2

N2 - 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.

AB - 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.

KW - Mixing/relaxation time

KW - Poincaré and log-Sobolev inequalities

KW - Random regular graph

KW - Switch chain

UR - http://www.scopus.com/inward/record.url?scp=85142544283&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85142544283&partnerID=8YFLogxK

U2 - 10.1007/s00440-022-01172-7

DO - 10.1007/s00440-022-01172-7

M3 - Article

AN - SCOPUS:85142544283

VL - 185

SP - 89

EP - 184

JO - Probability Theory and Related Fields

JF - Probability Theory and Related Fields

SN - 0178-8051

IS - 1-2

ER -