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

• 成果类型: Article
• 署名作者: Tikhomirov, Konstantin; Youssef, Pierre
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-022-01172-7
• 发表日期: 2023
• 页码: 89-184
• 关键词: uniform generation; markov-chain; circular law; algorithms; Digraphs; models

摘要

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 Poincare 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(n log n). We show that both results are optimal. The Poincare 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:2(X)6.12021 ). The log-Sobolev inequality that we establish for constant d implies a bound O (n log(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.