Theory Lunch Seminar

  • Gates Hillman Centers
  • ASA Conference Room 6115
  • Visiting Scholar
  • Computer Science Department
  • Carnegie Mellon University

Perfect Sampling of graph k -colorings for k > 3 Δ

We give an algorithm for perfect sampling from the uniform distribution on proper k -colorings of graphs of maximum degree Δ which terminates with a sample in expected time poly(k , n) whenever k ≥ 3 Δ (here, n is the number of vertices in the graph).

Inspired by the bounding chain approach pioneered independently by Häggström & Nelander (Scand. J. Statist., 1999) and Huber (STOC 1998) (who used the approach to give a perfect sampling algorithm requiring k > Δ2 + 2Δ for its expected running time to be a polynomial), our algorithm is based on a novel bounding chain for the coloring problem.

This is joint work with Sayantan Chakraborty at TIFR Mumbai.

CMU Youtube Theory Channel

For More Information, Please Contact: