Mixing time of the switch chain on regular bipartite graphs

Pierre Youssef (NYU Abu Dhabi)

12-Mar-2021, 14:30-15:30 (3 years ago)

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.

statistical mechanicsmathematical physicsprobability

Audience: researchers in the topic


Séminaire MEGA

Series comments: Description: Monthly seminar on random matrices and random graphs

Organizers: Guillaume Barraquand*, Laure Dumaz
*contact for this listing

Export talk to