Combinatorics Seminar

Wednesday, October 17, 2018 at 4:15pm to 5:15pm

Room 2-147

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.

Event Type


Events By Interest


Events By Audience


Events By School

School of Science


Department of Mathematics
Add to my calendar

Recent Activity