[Colloquium] Seminar: Tom Hayes, Tuesday 4/15

[Eric Vigoda]

Tom Hayes will give a seminar this Tuesday (April 15)
at 2 PM in Ryerson 277 (the annex).
This will be a technical talk on some exciting work
hot off the press.

Title:  Non-Markovian Couplings and Sampling Graph Colorings

Abstract:

Let G be a graph with maximum degree D.  When k > D colors are
available, it is trivial to construct a k-coloring of G. When k > D+1,
there are exponentially many k-colorings; nevertheless, it is not
known how to efficiently sample from this set, or even how to estimate
its size efficiently.

The Glauber dynamics is a very simple Markov chain whose stationary
distribution is uniform on k-colorings.  It is conjectured that it
rapidly converges to this distribution whenever k > D+1, which means
that it can be used to to efficiently sample colorings nearly
uniformly at random.  However, this has only been proved in general
when k > 11D/6.

We show that the Glauber dynamics converges in time O(n log n)
whenever k > (1 + epsilon) D, for all epsilon > 0, for "locally
tree-like graphs" with D = Omega(log n) and girth Omega(log log n).
The best previously known result for this class of graphs required
k > 1.489D.

Our basic approach is the so-called "coupling" technique, in which
one specifies the joint evolution of two colorings, in such a way
that they rapidly become identical.  In the past, such couplings have
almost always been "Markovian" in the sense that the joint evolution
is itself a Markov chain on the square of the state space.  One of the
most interesting features of our work is that it relies on a coupling
which is profoundly non-Markovian.  This is the first application of a
non-Markovian coupling to improve upon previously known results.

This is joint work with Eric Vigoda.