Article

The Glauber dynamics on colourings of a graph with high girth and maximum degree

Author:

Michael MolloyAuthors Info & Claims

STOC '02: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing

Pages 91 - 98

https://doi.org/10.1145/509907.509924

Published: 19 May 2002 Publication History

Get Access

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 and M. Dyer. Path coupling: a technique for proving rapid mixing in Markov chains. Proceedings of the 28th Annual Symposium on Foundations of Computer Science (1997), 223--231.

Digital Library

Google Scholar

[2]

M. Dyer and A. Frieze. Randomly colouring graphs with bounds on girth and maximum degree. Proceedings of the 32nd Annual Symposium on Foundations of Computer Science (2001).

Digital Library

Google Scholar

[3]

M. Dyer, L. Goldberg, C. Greenhill, M. Jerrum and M. Mitzenmacher, An extension of path coupling and its application to theGlauber dynamics for path colourings, Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (2000), 355--363.

Digital Library

Google Scholar

[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.

Google Scholar

[5]

M. Dyer, C. Greenhill and M. Molloy. Very rapid mixing of the Glauber dynamics for proper colourings on bounded-degree graphs. Random Structures and Algorithms (to appear).

Digital Library

Google Scholar

[6]

M. Jerrum, A very simple algorithm for estimating the number of k-colourings of a low-degree graph. Random Structures and Algorithms 7 (1995), 157--165.

Crossref

Google Scholar

[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.

Google Scholar

[8]

M. Molloy. Very rapidly mixing Markov Chains for 2Δ-colourings and for independent sets in a 4-regular graph. Random Struc. & Alg. 18, 101--115 (2001).

Digital Library

Google Scholar

[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.

Crossref

Google Scholar

[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.

Google Scholar

[11]

E. Vigoda. Improved bounds for sampling colourings. J. (MATH)ematical Physics 41 (2000), 1555--1569.

Google Scholar

Cited By

View all

Cannon SRandall D(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
https://dl.acm.org/doi/10.5555/2884435.2884572
Boucher COmar M(2012)On the Hardness of Counting and Sampling Center StringsIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2012.849:6(1843-1846)Online publication date: 1-Nov-2012
https://dl.acm.org/doi/10.1109/TCBB.2012.84
Boucher COmar M(2010)On the hardness of counting and sampling center stringsProceedings of the 17th international conference on String processing and information retrieval10.5555/1928328.1928343(127-134)Online publication date: 11-Oct-2010
https://dl.acm.org/doi/10.5555/1928328.1928343
Show More Cited By

Index Terms

The Glauber dynamics on colourings of a graph with high girth and maximum degree
1. Mathematics of computing
  1. Probability and statistics
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree

We prove that the Glauber dynamics on the C-colorings of a graph G on n vertices with girth g and maximum degree $\Delta$ mixes rapidly if (i) $C=q\Delta$ and $q>q^*$, where $q^*=1.4890\ldots$ is the root of $(1-{\rm e}^{-1/q})^2+q{\rm e}^{-1/q}=1$; and ...
Fractional Chromatic Number, Maximum Degree, and Girth

We introduce a new method for computing bounds on the independence number and fractional chromatic number of classes of graphs with local constraints and apply this method in various scenarios. We establish a formula that generates a general upper bound for ...
Some new results on graph colorings and chordal graphs

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '02: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing

May 2002

840 pages

ISBN:1581134959

DOI:10.1145/509907

Conference Chair:
John Reif
Duke University

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 May 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC02

Sponsor:

SIGACT

STOC02: Symposium on the Theory of Computing

May 19 - 21, 2002

Quebec, Montreal, Canada

Acceptance Rates

STOC '02 Paper Acceptance Rate 91 of 287 submissions, 32%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
23
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Cannon SRandall D(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
https://dl.acm.org/doi/10.5555/2884435.2884572
Boucher COmar M(2012)On the Hardness of Counting and Sampling Center StringsIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2012.849:6(1843-1846)Online publication date: 1-Nov-2012
https://dl.acm.org/doi/10.1109/TCBB.2012.84
Boucher COmar M(2010)On the hardness of counting and sampling center stringsProceedings of the 17th international conference on String processing and information retrieval10.5555/1928328.1928343(127-134)Online publication date: 11-Oct-2010
https://dl.acm.org/doi/10.5555/1928328.1928343
Boucher C(2009)Faster Algorithms for Sampling and Counting Biological SequencesProceedings of the 16th International Symposium on String Processing and Information Retrieval10.1007/978-3-642-03784-9_24(243-253)Online publication date: 21-Aug-2009
https://dl.acm.org/doi/10.1007/978-3-642-03784-9_24
Randall D(2006)Rapidly Mixing Markov Chains with Applications in Computer Science and PhysicsComputing in Science and Engineering10.1109/MCSE.2006.308:2(30-41)Online publication date: 1-Mar-2006
https://dl.acm.org/doi/10.1109/MCSE.2006.30
Martinelli FSinclair AWeitz D(2006)Fast mixing for independent sets, colorings, and other models on treesRandom Structures & Algorithms10.1002/rsa.2013231:2(134-172)Online publication date: 4-Oct-2006
https://doi.org/10.1002/rsa.20132
Hayes TVigoda E(2005)Coupling with the stationary distribution and improved sampling for colorings and independent setsProceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/1070432.1070573(971-979)Online publication date: 23-Jan-2005
https://dl.acm.org/doi/10.5555/1070432.1070573
Martinelli FSinclair AWeitz DMunro I(2004)Fast mixing for independent sets, colorings and other models on treesProceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/982792.982857(456-465)Online publication date: 11-Jan-2004
https://dl.acm.org/doi/10.5555/982792.982857
Hayes TVigoda EMunro I(2004)Variable length path couplingProceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/982792.982806(103-110)Online publication date: 11-Jan-2004
https://dl.acm.org/doi/10.5555/982792.982806
Martinelli FSinclair AWeitz D(2004)Glauber Dynamics on Trees: Boundary Conditions and Mixing TimeCommunications in Mathematical Physics10.1007/s00220-004-1147-y250:2(301-334)Online publication date: 12-Aug-2004
https://doi.org/10.1007/s00220-004-1147-y
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree

Fractional Chromatic Number, Maximum Degree, and Girth

Some new results on graph colorings and chordal graphs