Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

(MATH) We prove that the Glauber dynamics on the C-colourings of a graph G on n vertices with girth g and maximum degree $\D$ mixes rapidly if (i) $C=q\D$ and $q>q^*$ where $q^*=1.4890... $ is the root of $(1-\rme^{-1/q})^2+q\rme^{-1/q}=1$; and (ii) $\D\geq D\log n$ and $g\geq D\log\D$ for some constant $D=D(q)$. This improves the corresponding result with $q\geq1.763\D$ obtained by Dyer and Frieze [FOCS01] for the same class of graphs.

REFERENCES

• 1: R. Bubley , M. Dyer, Path coupling: A technique for proving rapid mixing in Markov chains, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.223, October 19-22, 1997
• 2: A. Frieze, Randomly Colouring Graphs with Lower Bounds on Girth and Maximum Degree, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.579, October 14-17, 2001
• 3: Martin Dyer , Leslie Ann Goldberg , Catherine Greenhill , Mark Jerrum , Michael Mitzenmacher, An extension of path coupling and its application to the Glauber dynamics for graph colourings (extended abstract), Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.616-624, January 09-11, 2000, San Francisco, California, United States
• 4: M.Dyer and C. Greenhill. Random walks on combinatorial objects. Surveys in Combinatorics, 1999, eds. J.D. Lamb and D.A. Preece. Cambridge University Press, 1999, 101--136.
• 5: Martin Dyer , Catherine Greenhill , Mike Molloy, Very rapid mixing of the Glauber dynamics for proper colorings on bounded-degree graphs, Random Structures & Algorithms, v.20 n.1, p.98-114, January 2002 [doi>10.1002/rsa.10020]
• 6: Mark Jerrum, A very simple algorithm for estimating the number of k-colorings of a low-degree graph, Random Structures & Algorithms, v.7 n.2, p.157-165, September 1995 [doi>10.1002/rsa.3240070205]
• 7: M. Jerrum, (MATH)ematical foundations of the Markov chain Monte Carlo method. Probabilistic Methods for Algorithmic Discrete (MATH)ematics, eds. M. Habib, C. McDiarmid, J. Ramirez-Alfosin and B. Reed. Springer, 1998, 116--165.
• 8: Michael Molloy, Very rapidly mixing Markov Chains for 2&Dgr;-colorings and for independent sets in a graph with maximum degree 4, Random Structures & Algorithms, v.18 n.2, p.101-115, March 1,2001 [doi>10.1002/1098-2418(200103)18:2<101::AID-RSA1000>3.0.CO;2-D]
• 9: J. Salas and A. Sokal. Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem. J. Stat. Physics 86 (1997), 551--579.
• 10: J. van den Berg and J. Steif. Percolation and the hard-core lattice gas model. Stochastic Processes and their Applications 49 (1994), 179--197.
• 11: E. Vigoda. Improved bounds for sampling colourings. J. (MATH)ematical Physics 41 (2000), 1555--1569.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Theory

Keywords:
Markov chain, rapidly mixing