Research Seminars @ Illinois

View Full Calendar

Tailored for undergraduate researchers, this calendar is a curated list of research seminars at the University of Illinois. Explore the diverse world of research and expand your knowledge through engaging sessions designed to inspire and enlighten.

To have your events added or removed from this calendar, please contact OUR at ugresearch@illinois.edu

THEORY SEMINAR: Charlie Carlson, "Sampling Colorings with Markov Chains"

Event Type
Seminar/Symposium
Sponsor
Michael A. Forbes
Location
Siebel 3401
Date
Nov 11, 2024   10:00 am  
Speaker
Charlie Carlson
Views
3
Originating Calendar
Siebel School Speakers Calendar

Theory seminar: Please join us on Nov 11th at 10am in the Siebel 3401 where Charlie Carlson (Simons Laufer Mathematical Sciences Institute) will give a talk, “Sampling Colorings with Markov Chains”.  Please see their abstract below:

 Abstract: We review the history of sample random k-colorings with and without Markov chains. We also present a new result for sampling random k-colorings in graphs with maximum degree ∆; our results hold without any further assumptions on the graph and are stronger than all previous results for general graphs. This talk is based on a paper with Eric Vigoda that will appear at the Symposium on Discrete Algorithms in 2025.

       The Glauber dynamics is a simple single-site update Markov chain. Jerrum (1995) proved an optimal O(n log n) mixing time bound for Glauber dynamics whenever k > 2∆ where ∆ is the maximum degree of the input graph. This bound was improved by Vigoda (1999) to k > (11/6)∆ using a “flip” dynamics which recolors (small) maximal 2-colored components in each step. Vigoda’s result was the best known for general graphs for 20 years until Chen et al. (2019) established optimal mixing of the flip dynamics for k > (11/6 − ε)∆ where ε ≈ 10−5. In this talk we present the first substantial improvement over these results. We prove an optimal mixing time bound of O(n log n) for the flip dynamics when k ≥ 1.809∆. This yields, through recent spectral independence results, an optimal O(n log n) mixing time for the Glauber dynamics for the same range of k/∆ when ∆ = O(1). Our proof utilizes path coupling with a simple weighted Hamming distance for “unblocked” neig hbors.

link for robots only