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

K Tikhomirov, P Youssef - Probability Theory and Related Fields, 2023 - Springer
Probability Theory and Related Fields, 2023Springer
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 O d (n log 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) 2 log (nd)), improving on the previously known …
Abstract
Consider the switch chain on the set of d-regular bipartite graphs on n vertices with , for a small universal constant . 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 . We show that both results are optimal. The Poincaré inequality implies that in the regime the mixing time of the switch chain is at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O\big ((nd)^2 \log (nd)\big )$$\end{document}, improving on the previously known bound \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O\big ((nd)^{13} \log (nd)\big )$$\end{document} due to Kannan et al. (Rand Struct Algorithm 14(4):293–308, 1999) and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O\big (n^7d^{18} \log (nd)\big )$$\end{document} 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 on the mixing time of the chain which, up to the 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.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果