Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 12 (2007) > Paper 16 open journal systems 


Sampling 3-colourings of regular bipartite graphs

David J Galvin, University of Pennsylvania


Abstract
We show that if G=(V,E) is a regular bipartite graph for which the expansion of subsets of a single parity of V is reasonably good and which satisfies a certain local condition (that the union of the neighbourhoods of adjacent vertices does not contain too many pairwise non-adjacent vertices), and if M is a Markov chain on the set of proper 3-colourings of G which updates the colour of at most c|V| vertices at each step and whose stationary distribution is uniform, then for c < .22 and d sufficiently large the convergence to stationarity of M is (essentially) exponential in |V|. In particular, if G is the d-dimensional hypercube Q_d (the graph on vertex set {0,1}^d in which two strings are adjacent if they differ on exactly one coordinate) then the convergence to stationarity of the well-known Glauber (single-site update) dynamics is exponentially slow in 2^d/(log d d^(1/2)). A combinatorial corollary of our main result is that in a uniform 3-colouring of Q_d there is an exponentially small probability (in 2^d) that there is a colour i such the proportion of vertices of the even subcube coloured i differs from the proportion of the odd subcube coloured i by at most .22. Our proof combines a conductance argument with combinatorial enumeration methods.


Full text: PDF

Pages: 481-497

Published on: April 18, 2007
Bibliography
  1. D. Aldous and J. Fill. Reversible Markov Chains and Random Walks on Graphs. Monograph in preparation, available at http://stat-www.berkeley.edu/users/aldous/RWG/book.html. Math. Review number not available.
  2. I. Benjamini, O. Häggström and E. Mossel. On random graph homomorphisms into Z. J. Combinatorial Th. (B) 78 no. 1 (2000), 86--114. Math. Review 2001c:60135
  3. B. Bollobás. Extremal Graph Theory. Academic Press, New York, 1978. Math. Review 80a:05120
  4. B. Bollobás. Modern Graph Theory. Springer, New York, 1998. Math. Review 99h:05001
  5. B. Bollobás. Random Graphs. Cambridge University Press, Cambridge, 2001. Math. Review 2002j:05132
  6. C. Borgs, J. Chayes, A. Frieze, J. Kim, P. Tetali, E. Vigoda, V. Vu. Torpid Mixing of some Monte Carlo Markov Chain algorithms in Statistical Physics. Proc. IEEE FOCS '99 218--229. Math. Review MR1917562
  7. R. Bubley and M. Dyer. Path coupling: a technique for proving rapid mixing in Markov chains. Proc. IEEE FOCS '97 223--231. Math. Review number not available.
  8. H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statistics 23 (1952), 493--507. Math. Review 15,241c
  9. R. Diestel. Graph Theory. Springer, New York, 2005. Math. Review 2006e:05001
  10. M. Dyer, A. Frieze and M. Jerrum. On counting independent sets in sparse graphs. SIAM J. Comp. 31 (2002), 1527--1541. Math. Review 2003h:68043
  11. M. Dyer, C. Greenhill, M. Molloy. Very rapid mixing of the Glauber dynamics for proper colorings on bounded degree graphs. Random Struc. & Alg. 20 (2002), 98--114. Math. Review 2002i:60131
  12. D. Galvin. On homomorphisms from the Hamming cube to Z. Isr. J. Math. 138 (2003), 189--213. Math. Review 2005b:05158
  13. D. Galvin and D. Randall. Torpid Mixing of Local Markov Chains on 3-Colorings of the Discrete Torus. Proc. ACM--SIAM SODA '07 376--384. No Math. Review number available.
  14. D. Galvin and P. Tetali. Slow mixing of Glauber dynamics for the hard-core model on the Hamming cube. Random Structures & Alg. 28 (2006) 427-443. Math. Review 2007a:05127
  15. M. Jerrum. A very simple algorithm for estimating the number of k-colourings of a low-degree graph. Random Struc. & Alg. 7 (1995), 157--165. Math. Review 97f:68070
  16. M. Jerrum and A. Sinclair. Conductance and the rapid mixing property for Markov chains: the approximation of the permanent resolved. Proc. ACM STOC '88 235--243. No Math. Review number available.
  17. J. Kahn. Range of cube-indexed random walk. Isreal J. Math. 124 (2001) 189--201. Math. Review 2002k:60173
  18. A. Korshunov and A. Sapozhenko. The number of binary codes with distance 2. Problemy Kibernet. 40 (1983), 111--130. (Russian) Math. Review 85a:94026
  19. T. Łuczak and E. Vigoda. Torpid mixing of the Wang-Swendsen-Kotecký algorithm for sampling colorings. J. Discrete Alg. 3 no. 1 (2005), 92--100. Math. Review 2006d:68268
  20. M. Molloy. Very rapidly mixing Markov chains for 2Δ-colourings and for independent sets in a 4-regular graph. Random Struc. & Alg. 18 (2001), 101--115. Math. Review 2002b:68036
  21. R. Montenegro and P. Tetali. Mathematical aspects of mixing times in Markov chains. Foundations and Trends in Theoretical Computer Science 1 no. 3 (2006), 237--354. Math. Review number not available.
  22. D. Randall. Mixing. Proc. IEEE FOCS '03 4--15. Math. Review number not available.
  23. D. Randall. Personal communication. Math. Review number not available.
  24. J. Salas and A. Sokal. Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem. J. Stat. Phys. 86 (1997), 551--579. Math. Review 98b:82020
  25. 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) Math. Review 89i:05168
  26. A. A. Sapozhenko. The number of antichains in ranked partially ordered sets. Diskret. Mat. 1 (1989), 74--93. (Russian; translation in Discrete Math. Appl. 1 no. 1 (1991), 35--58) Math. Review 91h:06006
  27. A. Sokal. Chromatic Polynomials, Potts Models and All That. Physica A279 (2000), 324--332. Math. Review number not available.
  28. A. Sokal. A Personal List of Unsolved Problems Concerning Lattice Gases and Antiferromagnetic Potts Models. Markov Process. Related Fields 7 (2001), 21--38. Math. Review MR1835744
  29. E. Vigoda. Improved bounds for sampling colorings. J. Math. Phys. 41 (2000), 1555--1569. Math. Review 2001a:60085
















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | ECP

Electronic Journal of Probability. ISSN: 1083-6489