Randomly coloring graphs of girth at least five

ABSTRACT

We improve rapid mixing results for the simple Glauber dynamics designed to generate a random k-coloring of a bounded-degree graph.Let G be a graph with maximum degree Δ = Ω(log n), and girth ≥ 5. We prove that if k > Α Δ, where Α ≈ 1.763 then Glauber dynamics has mixing time O(n log n). If girth(G) ≥ 6 and k > Β Δ, where Β ≈ 1.489 then Glauber dynamics has mixing time O(n log n). This improves a recent result of Molloy, who proved the same conclusion under the stronger assumptions that Δ=Ω(log n) and girth Ω(log Δ). Our work suggests that rapid mixing results for high girth and degree graphs may extend to general graphs.Analogous results hold for random graphs of average degree up to n^¼, compared with polylog(n), which was the best previously known.Some of our proofs rely on a new Chernoff-Hoeffding type bound, which only requires the random variables to be well-behaved with high probability. This tail inequality may be of independent interest.

REFERENCES

• 1: G. Brightwell and P. Winkler. Random colorings of a Cayley tree. In B. Bollobas, editor, Contemporary Combinatorics, volume 10 of Bolyai Society Mathematical Studies. Springer Verlag, 2002.
• 2: 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
• 3: Devdatt Dubhashi, Simple proofs of occupancy tail bounds, Random Structures & Algorithms, v.11 n.2, p.119-123, Sept. 1997 [doi>10.1002/(SICI)1098-2418(199709)11:2<119::AID-RSA2>3.0.CO;2-V]
• 4: Devdatt Dubhashi , Desh Ranjan, Balls and bins: a study in negative dependence, Random Structures & Algorithms, v.13 n.2, p.99-124, Sept. 1998 [doi>10.1002/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M]
• 5: 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
• 6: 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]
• 7: T. Hayes. Randomly coloring bipartite graphs. Manuscript, in progress, 2003.
• 8: T. Hayes and E. Vigoda. A non-Markovian coupling technique. Technical Report TR-2003-02, University of Chicago, February 2003.
• 9: 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]
• 10: M R Jerrum , L G Valiant , V V Vazirani, Random generation of combinatorial structures from a uniform, Theoretical Computer Science, v.43 n.2-3, p.169-188, July 1986
• 11: Michael Molloy, The Glauber dynamics on colourings of a graph with high girth and maximum degree, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509924]
• 12: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 13: J. Salas and A. Sokal. Absence of phase transition for anti-ferromagnetic Potts models via the Dobrushin uniqueness theorem. Journal of Statistical Physics, 86:551--579, 1997.
• 14: E. Vigoda. Improved bounds for sampling colorings. J. Math. Phys., 41:155--169, 2000.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes; Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Theory

Keywords:
Chernoff bounds, Glauber dynamics, Markov chain Monte Carlo, concentration inequalities, graph coloring, posterior analysis