LFCS seminar: Guillem Perarnau: Rapid mixing of Glauber dynamics for graph colorings
What 


When 
Sep 25, 2018 from 04:00 PM to 05:00 PM 
Where  IF 4.31/4.33 
Add event to calendar 
vCal iCal 
Abstract: A wellknown conjecture in computer science and statistical physics is that Glauber dynamics on the set of kcolorings of a graph G on n vertices with maximum degree \Delta is rapidly mixing for k \ge \Delta+2. In 1999, Vigoda showed rapid mixing of flip dynamics with certain flip parameters on the set of proper kcolorings for k > (11/6)\Delta, implying rapid mixing for Glauber dynamics. In this paper, we obtain the first improvement beyond the (11/6)\Delta barrier for general graphs by showing rapid mixing for k > (11/6  \eta)\Delta for some positive constant \eta. The key to our proof is combining path coupling with a new kind of metric that incorporates a count of the extremal configurations of the chain. Additionally, our results extend to list coloring, a widely studied generalization of coloring. Combined, these results answer two open questions from Frieze and Vigoda’s 2007 survey paper on Glauber dynamics for colorings. (Joint work with Michelle Delcourt and Luke Postle)