We consider the space of d-regular directed simple graphs, where two graphs are connected whenever there is a simple switching operation transforming one graph to the other. For constant d, we prove optimal bounds on the Modified Log-Sobolev Constant of the associated Markov chain on the space of graphs. This implies that the total variation mixing time of the chain is of order n log(n), which settles an old open problem. Based on joint work with Pierre Youssef.
Probability and Combinatorics
Tuesday, February 28, 2023 - 3:30pm
Konstantin Tikhomirov
Carnegie Mellon University
Other Events on This Day
-
Definable sets in ordered Abelian groups of finite dp-rank
Logic and Computation Seminar
2:00pm
-
Fluid Instabilities near animal motions
MathBio Seminar
4:00pm