Article

A Non-Markovian Coupling for Randomly Sampling Colorings

Authors:

Thomas P. Hayes,

Eric VigodaAuthors Info & Claims

FOCS '03: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science

Page 618

Published: 11 October 2003 Publication History

Publisher Site

Abstract

We study a simple Markov chain, known as the Glauber dynamics, for randomly sampling (proper) k-colorings of an input graph G on n vertices with maximum degree \Delta and girth g. We prove the Glauber dynamics is close to the uniform distribution after 0(n log n) steps whenever k > (1 + \varepsilon)\Delta for all \varepsilon > 0, assuming g 9 and \Delta= \Omega (\log n). The best previously known bounds were k > 11\Delta/6 for general graphs, and k > 1.489\Delta for graphs satisfying girth and maximum degree requirements.Our proof relies on the construction and analysis of a non-Markovian coupling. This appears to be the first application of a non-Markovian coupling to substantially improve upon known results.

Cited By

View all

Feng WGuo HYin YZhang CMarx D(2021)Rapid mixing from spectral independence beyond the boolean domainProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458159(1558-1577)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458159
Chen ZGalanis AŠtefankovič DVigoda EMarx D(2021)Rapid mixing for colorings via spectral independenceProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458158(1548-1557)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458158
Chen SDelcourt MMoitra APerarnau GPostle LChan T(2019)Improved bounds for randomly sampling colorings via linear programmingProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310569(2216-2234)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310569
Show More Cited By

Index Terms

A Non-Markovian Coupling for Randomly Sampling Colorings
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
      2. Graph enumeration
  2. Probability and statistics
    1. Probabilistic representations
      1. Markov networks
    2. Stochastic processes
      1. Markov processes
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Machine learning theory
      1. Markov decision processes

Recommendations

On colourings of graphs
Some new results on graph colorings and chordal graphs
$$[1,1,t]$$-Colorings of Complete Graphs

Given non-negative integers $$r, s,$$ and $$t,$$ an $$[r,s,t]$$ - coloring of a graph $$G = (V(G),E(G))$$ is a mapping $$c$$ from $$V(G) \cup E(G)$$ to the color set $$\{1,\ldots ,k\}$$ such that $$\left|c(v_i) - c(v_j)\right| \ge r$$ for every two adjacent vertices $$v_i,v_j, \left|c({e_i}) - c(e_j)\right| \ge s$$ for every two adjacent edges $$e_i,e_j,$$ and $$\left|c(v_i) - c(e_j)\right| \ge t$$ for all pairs of incident vertices and edges, respectively. The $$[r,s,t]$$ - ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

FOCS '03: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science

October 2003

ISBN:0769520405

Publisher

IEEE Computer Society

United States

Publication History

Published: 11 October 2003

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 19 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Feng WGuo HYin YZhang CMarx D(2021)Rapid mixing from spectral independence beyond the boolean domainProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458159(1558-1577)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458159
Chen ZGalanis AŠtefankovič DVigoda EMarx D(2021)Rapid mixing for colorings via spectral independenceProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458158(1548-1557)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458158
Chen SDelcourt MMoitra APerarnau GPostle LChan T(2019)Improved bounds for randomly sampling colorings via linear programmingProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310569(2216-2234)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310569
Efthymiou CHayes TŠtefankovič DVigoda ECzumaj A(2018)Sampling random colorings of sparse random graphsProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175420(1759-1771)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175420
Guo HLiao CLu PZhang CDiakonikolas IKempe DHenzinger M(2018)Counting hypergraph colourings in the local lemma regimeProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188934(926-939)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188934
Lu PYang KZhang CZhu MKlein P(2017)An FPTAS for counting proper four-colorings on cubic graphsProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039803(1798-1817)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039803
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
Li LLu PYin Y(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
https://dl.acm.org/doi/10.5555/2095116.2095190
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

Abstract

Cited By

Index Terms

Recommendations

On colourings of graphs

Some new results on graph colorings and chordal graphs

$$[1,1,t]$$-Colorings of Complete Graphs

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Share

Share this Publication link

Share on social media

Affiliations