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

ABSTRACT:

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

Conferences/Seminars/Lectures

Events By Interest

Academic

Events By Audience

Public

Events By School

School of Science

Website

http://math.mit.edu/seminars/combin/

Department
Department of Mathematics
Add to my calendar

Recent Activity