CS&E Colloquium: Sampling Colorings with Markov Chains

The computer science colloquium takes place on Mondays from 11:15 a.m. - 12:15 p.m. This week's speaker, Charlie Carlson (University of California, Santa Barbara), will be giving a talk titled "Sampling Colorings with Markov Chains."

Abstract

Graph coloring is a fundamental problem at the intersection of computer science and mathematics. A graph is k-colorable if its vertices can be assigned k colors such that adjacent vertices receive different colors. The problems of finding or sampling such colorings play crucial roles in both theoretical and practical research; they serve as natural test beds for algorithm design techniques and arise in many engineering applications. While a simple greedy algorithm can efficiently find a (d+1)-coloring for a graph with maximum degree d, the problem of uniformly sampling such a coloring is significantly more challenging. A well-known conjecture states that it is possible to efficiently sample a (d+2)-coloring.

In this talk, we will explore the importance of sampling random colorings and the history of using Markov chains to address this conjecture. Our discussion will include a review of the recent breakthrough by Carlson and Vigoda, which demonstrates the rapid mixing of Flip dynamics and the existence of an efficient algorithm for sampling colorings when k > 1.809d. Along the way, we will introduce key concepts such as Glauber dynamics, path coupling, and Flip dynamics. We conclude with a discussion of open problems and future research directions for sampling colorings and analyzing similar Markov chains. 

Biography

Charlie Carlson is a postdoctoral researcher at SLMath and the University of California, Santa Barbara. She earned her PhD in Computer Science from the University of Colorado Boulder where she was advised by Alexandra Kolla. Her research interests lie mostly at the intersection of spectral graph theory, combinatorial optimization, and random algorithms. Recently, she has been investigating connections between different methods of analyzing Markov chains.