Wednesday, October 17, 2018 at 4:15pm to 5:15pm
SPEAKER: Sitan Chen (MIT)
TITLE: Improved bounds for sampling colorings via linear programming
This talk will be about the well-known problem of approximately sampling random k-colorings of graphs of maximum degree d. It is conjectured that a simple Markov chain, single-site Glauber dynamics, should suffice for any k > d + 1. In 1999, Vigoda showed that a different Markov chain based on flipping bichromatic components rapidly mixes for any k > 11*d/6. While there have been subsequent works obtaining better bounds for restricted families of graphs, Vigoda's result has remained the best known for general graphs. In this talk I will overview how to circumvent the 11/6 barrier via linear programming, showing that for some absolute constant η > 0, Vigoda's Markov chain rapidly mixes for any k > (11/6 - η)*d.