Computer Science/Discrete Mathematics Seminar II

We consider "local-update" Markov chains for sampling from independent sets and proper 3-colourings of a graph. An example of such a chain is the well-known Glauber dynamics, which updates the state of at most one vertex of the graph at each step. For independent sets, we show that if G is a regular, bipartite graph with reasonable expansion and if M is an ergodic Markov chain on the independent sets of G which updates the state of at most 10% of the vertices of G at each step and whose stationary distribution is uniform, then the mixing time of M is (essentially) exponential in the size of the vertex set of G. We generalize this to the case where M samples from the hard-core measure with activity \lambda for suitable \lambda. For uniform proper 3-colourings we prove an analogous result, except that here we also have to impose an odd-looking local condition on the graph G, a condition which is not satisfies, for example, by graphs with girth greater than 4. In particular, we get a lower bound of 2^{\Omega(2^d/(\sqrt{d}\log d))} on the mixing time of Glauber dynamics for sampling uniformly from the independent sets of the discrete hypercube Q_d, and the same bound for sampling uniformly from the proper 3-colourings of Q_d. Part of this work (the independent set part) is joint with Prasad Tetali, Georgia Tech.