×

Randomly coloring constant degree graphs. (English) Zbl 1272.05045

Summary: We study a simple Markov chain, known as the Glauber dynamics, for generating a random \(k\)-coloring of an \(n\)-vertex graph with maximum degree \(\Delta \). We prove that, for every \(\epsilon > 0\), the dynamics converges to a random coloring within \(O(n\log n)\) steps assuming \(k\geq k_{0}(\epsilon )\) and either: (i) \(k/\Delta > \alpha^\ast + \epsilon \) where \(\alpha^\ast\approx 1.763\) and the girth \(g\geq 5\), or (ii) \(k/\Delta >\beta^\ast + \epsilon \) where \(\beta^\ast\approx 1.489\) and the girth \(g\geq 7\). Our work improves upon, and builds on, previous results which have similar restrictions on \(k/\Delta \) and the minimum girth but also required \(\Delta = \Omega (\log n)\). The best known result for general graphs is \(O(n\log n)\) mixing time when \(k/\Delta > 2\) and \(O(n^{2})\) mixing time when \(k/\Delta > 11/6\). Related results of Goldberg et al apply when \(k/\Delta > \alpha^\ast\) for all \(\Delta \geq 3\) on triangle-free “neighborhood-amenable” graphs.

MSC:

05C15 Coloring of graphs and hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
05C35 Extremal problems in graph theory
05C07 Vertex degrees
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
68W20 Randomized algorithms
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] van den Berg, Percolation and the hard-core lattice gas model, Stoch Process Appl 49 pp 179– (1994) · Zbl 0787.60125 · doi:10.1016/0304-4149(94)90132-5
[2] Brightwell, Random colorings of a Cayley tree, Contemporary Combin 10 pp 247– (2002) · Zbl 1001.60108
[3] R. Bubley M. E. Dyer Path coupling: A technique for proving rapid mixing in Markov chains 1997 223 231
[4] Dyer, Randomly coloring graphs with lower bounds on girth and maximum degree, Random Struct Algorithms 23 pp 167– (2003) · Zbl 1028.05030 · doi:10.1002/rsa.10087
[5] M. Dyer A. Frieze T. P. Hayes E. Vigoda Randomly coloring constant degree graphs 2004 582 589 · Zbl 1272.05045
[6] Dyer, A random polynomial time algorithm for approximating the volume of convex bodies, J ACM 38 pp 1– (1991) · Zbl 0799.68107 · doi:10.1145/102782.102783
[7] Goldberg, Strong spatial mixing for lattice graphs with fewer colours, SIAM J Comput 35 pp 486– (2005) · Zbl 1091.60013 · doi:10.1137/S0097539704445470
[8] T. P. Hayes Randomly coloring graphs of girth at least five 2003 269 278
[9] T. P. Hayes Local Uniformity Properties for Glauber Dynamics on Graph Colorings 2011 http://www.cs.unm.edu/hayes/papers/hayes-uniformity-2011-04-05.pdf.
[10] T. P. Hayes J. C. Vera E. Vigoda Randomly coloring planar graphs with fewer colors than the maximum degree 2007 450 458 · Zbl 1231.05097
[11] Hayes, A general lower bound for mixing of single-site dynamics on graphs, Ann Appl Probab 17 pp 931– (2007) · Zbl 1125.60075 · doi:10.1214/105051607000000104
[12] T. P. Hayes E. Vigoda A non-Markovian coupling for randomly sampling colorings 2003 618 627
[13] Hayes, Variable length path coupling, Random Struct Algorithms 31 pp 251– (2007) · Zbl 1137.60032 · doi:10.1002/rsa.20166
[14] Jerrum, A very simple algorithm for estimating the number of k -colorings of a low-degree graph, Random Struct Algorithms 7 pp 157– (1995) · Zbl 0833.60070 · doi:10.1002/rsa.3240070205
[15] Jerrum, A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries, J ACM 51 pp 671– (2004) · Zbl 1204.65044 · doi:10.1145/1008731.1008738
[16] Jerrum, Random generation of combinatorial structures from a uniform distribution, Theor Comput Sci 43 pp 169– (1986) · Zbl 0597.68056 · doi:10.1016/0304-3975(86)90174-X
[17] Kannan, Random walks and an O*(n5) volume algorithm for convex bodies, Random Struct Algorithms 11 pp 1– (1997) · Zbl 0895.60075 · doi:10.1002/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO;2-X
[18] Levin, Markov chains and mixing times (2009)
[19] Lovász, Simulated annealing in convex bodies and an O*(n4) volume algorithm, J Comput Syst Sci 72 pp 392– (2006) · Zbl 1090.68112 · doi:10.1016/j.jcss.2005.08.004
[20] Martinelli, Fast mixing for independent sets, colorings, and other models on trees, Random Struct Algorithms 31 pp 134– (2007) · Zbl 1138.82020 · doi:10.1002/rsa.20132
[21] Molloy, The Glauber dynamics on colorings of a graph with high girth and maximum degree, SIAM J Comput 33 pp 712– (2004) · Zbl 1105.68116 · doi:10.1137/S0097539702401786
[22] Salas, Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem, J Stat Phys 86 pp 551– (1997) · Zbl 0935.82010 · doi:10.1007/BF02199113
[23] &0160;tefankovi&010D;, Adaptive simulated annealing: A near-optimal connection between sampling and counting, J ACM 56 pp 1– (2009) · Zbl 1325.68198
[24] P. Tetali J. C. Vera E. Vigoda L. Yang Phase transition for the mixing time of the Glauber dynamics for coloring regular trees 2010 1646 1656 · Zbl 1266.82043
[25] Vigoda, Improved bounds for sampling colorings, J Math Phys 41 pp 1555– (2000) · Zbl 0978.60083 · doi:10.1063/1.533196
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.