Pierre Youssef -- Mixing time of the switch chain on regular bipartite graphs
Channel: Matrices Et Graphes Aléatoires GDR CNRS
Date: 15/03/2021

Abstract: Given a fixed integer d, we consider the switch chain on the set of d-regular bipartite graphs on n vertices equipped with the uniform measure. We prove a sharp Poincaré and log-Sobolev inequality implying that the mixing time of the switch chain is at most O(n log^2n) which is optimal up to a logarithmic term. This improves on earlier results of Kannan, Tetali, Vempala and Dyer et al. who obtained the bounds O(n^13 log n) and O(n^7 log n) respectively. This is a joint work with Konstantin Tikhomirov.