skip to main content
10.5555/1283383.1283423acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
Article

Torpid mixing of local Markov chains on 3-colorings of the discrete torus

Published: 07 January 2007 Publication History

Abstract

We study local Markov chains for sampling 3-colorings of the discrete torus TL, d = {0, ..., L--1}d. We show that there is a constant ρ ≈ .22 such that for all even L ≥ 4 and d sufficiently large, certain local Markov chains require exponential time to converge to equilibrium. More precisely, if M is a Markov chain on the set of proper 3-colorings of TL, d that updates the color of at most ρLd vertices at each step and whose stationary distribution is uniform, then the convergence to stationarity of M is exponential in Ld-1. Our proof is based on a conductance argument that builds on sensitive new combinatorial enumeration techniques.

References

[1]
D. Achlioptas, M. Molloy, C. Moore, and F. Van Bussel, Sampling grid colourings with fewer colours, Proc. of LATIN '04, 80--89.
[2]
C. Borgs, J. Chayes, A. Frieze, J. H. Kim, P. Tetali, E. Vigoda, V. Vu, Torpid Mixing of some Monte Carlo Markov Chain algorithms in Statistical Physics, Proc. of the IEEE FOCS '99, 218--229.
[3]
R. Bubley, M. Dyer and C. Greenhill, Beating the 2Δ bound for approximately counting colourings: a computer-assisted proof of rapid mixing, Proc. of the 9th ACM-SIAM SODA '98, 355--363.
[4]
M. Dyer, A. Frieze and M. Jerrum, On counting independent sets in sparse graphs, SIAM J. Comp. 31 (2002), 1527--1541.
[5]
S. J. Ferreira and A. D. Sokal, Antiferromagnetic Potts model on the square lattice: a high precision Monte Carlo study, J. Stat. Phys. 96 (1999), 461--530.
[6]
A. Frieze and E. Vigoda, A survey on the use of Markov chains to randomly sample colourings, to appear in Combinatorics, Complexity and Chance.
[7]
D. Galvin, Sampling independent sets from the discrete torus, submitted (preprint available on the web at www.math.upenn.edu/~dgalvin/pdf/indmixZd.pdf).
[8]
D. Galvin and J. Kahn, On phase transition in the hard-core model on Z d , Comb. Prob. Comp. 13 (2004), 137--164.
[9]
D. Galvin, J. Kahn, D. Randall and G. Sorkin, On phase transition in the 3-coloring model on Z d , in preparation.
[10]
L. A. Goldberg, R. Martin and M. Paterson, Random sampling of 3-colourings in Z2, Random Structures and Algorithms 24 (2004), 279--302.
[11]
T. Hayes and E. Vigoda, Coupling with the stationary distribution and improved sampling for colorings and independent sets, Proc. of the 16th Annual ACM-SIAM SODA '05, 971--979.
[12]
M. R. Jerrum, A very simple algorithm for estimating the number of k-colorings of a low-degree graph, Random Structures and Algorithms 7 (1995), 157--165.
[13]
M. Jerrum and A. Sinclair, The Monte Carlo Markov chain method: an approach to approximate counting and integration, in Approximation Alorithms for NP-hard problems, PWS, 1996.
[14]
G. F. Lawler and A. D. Sokal, Bounds on the L 2 spectrum for Markov chains and Markov processes: a generalization of Cheeger's inequality, Trans. Amer. Math. Soc. 309 (1988), 557--580.
[15]
M. Luby, D. Randall, and A. J. Sinclair, Markov Chains for Planar Lattice Structures, SIAM Journal on Computing 31 (2001), 167--192.
[16]
A. A. Sapozhenko, On the number of connected subsets with given cardinality of the boundary in bipartite graphs, Metody Diskret. Analiz. 45 (1987), 42--70. (Russian.)
[17]
A. J. Sinclair, Algorithms for random generation & counting: a Markov chain approach, Birkhääuser, Boston, 1993.
[18]
L. E. Thomas, Bound on the mass gap for finite volume stochastic Ising models at low temperature, Commun. Math. Phys. 126 (1989), 1--11.
[19]
J. S. Wang, R. H. Swendsen, and R. Kotecký, Three-state antiferromagnetic Potts models: A Monte Carlo study, Phys. Rev. B 42 (1990) 2465--2474.
[20]
D. Welsh, Complexity: Knots, Colourings, and Counting, London Math. Soc. Lec. Note Series 186, 1993.

Cited By

View all
  • (2017)Exponential segregation in a two-dimensional schelling model with tolerant individualsProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039748(984-993)Online publication date: 16-Jan-2017
  • (2016)Sampling on lattices with free boundary conditions using randomized extensionsProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884572(1952-1971)Online publication date: 10-Jan-2016
  • (2012)Approximate counting via correlation decay in spin systemsProceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms10.5555/2095116.2095190(922-940)Online publication date: 17-Jan-2012
  • Show More Cited By
  1. Torpid mixing of local Markov chains on 3-colorings of the discrete torus

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms
    January 2007
    1322 pages
    ISBN:9780898716245
    • Conference Chair:
    • Harold Gabow

    Sponsors

    Publisher

    Society for Industrial and Applied Mathematics

    United States

    Publication History

    Published: 07 January 2007

    Check for updates

    Qualifiers

    • Article

    Acceptance Rates

    SODA '07 Paper Acceptance Rate 139 of 382 submissions, 36%;
    Overall Acceptance Rate 411 of 1,322 submissions, 31%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)1
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 15 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2017)Exponential segregation in a two-dimensional schelling model with tolerant individualsProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039748(984-993)Online publication date: 16-Jan-2017
    • (2016)Sampling on lattices with free boundary conditions using randomized extensionsProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884572(1952-1971)Online publication date: 10-Jan-2016
    • (2012)Approximate counting via correlation decay in spin systemsProceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms10.5555/2095116.2095190(922-940)Online publication date: 17-Jan-2012
    • (2012)H-coloring toriJournal of Combinatorial Theory Series B10.1016/j.jctb.2012.05.003102:5(1110-1133)Online publication date: 1-Sep-2012
    • (2009)Sampling biased lattice configurations using exponential metricsProceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms10.5555/1496770.1496779(76-85)Online publication date: 4-Jan-2009
    • (2007)Slow Mixing of Markov Chains Using Fault Lines and Fat ContoursProceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques10.1007/978-3-540-74208-1_39(540-553)Online publication date: 20-Aug-2007

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media