6 papers
Sampling Simultaneous Edge-Colorings
Ezra Furtado-Tiwari, Eric Vigoda
We study the sampling problem for simultaneous edge colorings. Given a pair of graphs and which are on the same vertex set , a simultaneous edge colo…
Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local Uniformity
Vishesh Jain, Clayton Mizgerd, Eric Vigoda
Sampling graph colorings via local Markov chains is a central problem in approximate counting and Markov chain Monte Carlo (MCMC). We address the problem of sampling a random -c…
Critical window for approximate counting in dense Ising models
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
We study the complexity of approximating the partition function of dense Ising models in the critical regime. Recent work of Chen, Chen, Yin, and Zhang (FOCS 2025) established fast…
Mixing of general biased adjacent transposition chains
Reza Gheissari, Holden Lee, Eric Vigoda
We analyze the general biased adjacent transposition shuffle process, which is a well-studied Markov chain on the symmetric group . In each step, an adjacent pair of elements…
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…
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 dynamic…