Showing 2024Show all
2 papers · 1 filter
cs.DM2024
Flip Dynamics for Sampling Colorings: Improving Using a Simple Metric
Charlie Carlson, Eric Vigoda
We present improved bounds for randomly sampling -colorings of graphs with maximum degree ; our results hold without any further assumptions on the graph. The Glauber dynami…
cs.DM2024
Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree
Charlie Carlson, Xiaoyu Chen, Weiming Feng +1
We address the convergence rate of Markov chains for randomly generating an edge coloring of a given tree. Our focus is on the Glauber dynamics which updates the color at a randoml…