Publications related to:
Coupling Method; Markov Chains for Colorings and Independent Sets

• Reconstruction for Colorings on Trees
  N. Bhatnagar, J. Vera, E. Vigoda, and D. Weitz
  Preprint.
  Download from arXiv
• Randomly coloring planar graphs with fewer colors than the maximum degree.
  T. Hayes, J. Vera and E. Vigoda.
  STOC 2007.
  Download full version from arXiv
• A Survey on the use of Markov Chains to Randomly Sample Colorings
  A. Frieze and E. Vigoda
  In Combinatorics, Complexity and Chance, Oxford University Press, 2007.
  Download: PDF
  
• Randomly Coloring Sparse Random Graphs with Fewer Colors than the Maximum Degree.
  M. Dyer, A. Flaxman, A. Frieze, and E. Vigoda
  Random Structures and Algorithms, 29(4):450-465, 2006.
  Download: PDF
• Coupling with the Stationary Distribution and Improved Sampling for Colorings and Independent Sets.
  T. Hayes, and E. Vigoda
  Annals of Applied Probability, 16(4):1297-1318, 2006.
  Preliminary version appears in SODA 2005.
  Download: PDF
  
• Randomly coloring constant degree graphs.
  M. Dyer, A. Frieze, T. Hayes, and E. Vigoda
  FOCS 2004.
  Download: PS or PDF
• Variable Length Path Coupling.
  T. Hayes and E. Vigoda
  Random Structures and Algorithms, 31(3):251-272, 2007.
  Preliminary version appears in SODA 2004.
  Download: PDF
• A Non-Markovian Coupling for Randomly Sampling Colorings.
  T. Hayes and E. Vigoda
  Preliminary version appears in FOCS 2003.
  Download: PDF
• Improved bounds for sampling colorings.
  E. Vigoda
  Journal of Mathematical Physics, 41(3):1555-1569, 2000.
  A preliminary version appears in FOCS 1999.
  Machtey award co-winner for best student paper at FOCS 1999.
  Download: PS
• A note on the Glauber dynamics for sampling independent sets.
  E. Vigoda
  Electronic Journal of Combinatorics, 8(1), Research paper 8, 2001.
  Download: PS
  
  This paper subsumes:
  • Fast convergence of the Glauber dynamics for sampling independent sets.
    M. Luby and E. Vigoda
    Random Structures and Algorithms, 15(3-4):229-241, 1999.
  • Approximately Counting up to Four.
    M. Luby and E. Vigoda
    STOC 1997.
• Torpid mixing of the Wang-Swendsen-Kotecky algorithm for sampling colorings.
  T. Luczak, and E. Vigoda
  Journal of Discrete Algorithms, 3(1):92-100, 2005.
  Download: PS
• Torpid Mixing of Some Monte Carlo Markov Chain Algorithms in Statistical Physics
  C. Borgs, J. T. Chayes, J-H. Kim, A. Frieze, P. Tetali, E. Vigoda, and V. H. Vu
  FOCS 1999.
  Download: PDF