Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminars LFCS seminar: Guillem Perarnau: Rapid mixing of Glauber dynamics for graph colorings

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

— filed under: ,

What
  • LFCS Seminar
  • Upcoming events
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 well-known conjecture in computer science and statistical physics is that Glauber dynamics on the set of k-colorings 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 k-colorings 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)

Document Actions