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
Series comments: Description: Monthly seminar on random matrices and random graphs
Organizers: | Guillaume Barraquand*, Laure Dumaz |
*contact for this listing |
Export talk to