Random orbits on colourings, or nested Markov chains

I promised after reporting Catherine Greenhill’s talk last week that I would advertise this little problem; so here goes.

How do we pick a random proper colouring of a graph Γ? There is a simple Markov chain for this, also known as Glauber dynamics. Start with any proper colouring (or indeed, with any probability distribution on colourings). One step in the chain is as follows: choose a random vertex v and a random colour c; recolour v with c if possible, otherwise do nothing. The limiting distribution is uniform. Moreover, if the number of colours available is more than twice the maximum valency, then Mark Jerrum showed (using the coupling method) that the chain is rapidly mixing.

Now suppose that we have a group G of automorphisms of Γ, and we want to choose a random G-orbit on proper colourings. What do we do?

The good news is that Mark Jerrum devised a Markov chain method for choosing a random orbit of a group G acting on a set X. Take the bipartite graph with vertex set XG, with an edge from x to g whenever g fixes x. Start from a point of X (or a probability distribution on X), and take a random walk with an even number of steps. The limiting distribution is uniform on orbits (that is, the probability of ending at x is inversely proportional to the size of the orbit containing x). The proof is almost the same as that of the Orbit-counting Lemma. With Leslie Goldberg, Mark showed that sometimes the chain is rapidly mixing, and sometimes it is not.

Can we apply Jerrum’s method to orbits on colourings? The two steps of the random walk ask for the following.

  1. Given a colouring, choose a random automorphism in G fixing it. This has a smell of “graph isomorphism” about it; Laci Babai’s recent big result encourages us to think that this is not as hard as it might appear. In practice, a program like nauty will work efficiently.
  2. Given an automorphism g, choose a random colouring fixed by g. We know that g fixes some colouring; so a cycle of g (acting on vertices) contains no edges. We can form a graph Γ/g by shrinking each cycle of g to a single vertex. Any colouring of this graph extends uniquely to a colouring of Γ fixed by g. SO our job is to choose a random colouring of Γ/g.

We could use the recolouring chain for this. But then our problem is that one Markov chain (recolouring) is nested in the other (random orbit). We cannot run the recolouring chain for infinitely many steps during each step of the random orbit chain! If we stop after a bounded number of steps, we will be at a certain distance from the uniform distribution. How does this affect the performance of the random orbits chain? In particular, can we tune the amount of time spent on each of the two kinds of chain so that the limiting distribution tends to uniform? If so, can we say anything about the mixing time?

There may be a different way to choose a random orbit on colourings. But even if so, it might still be worth thinking about the above questions, since this may be an exemplar of a more general situation of nested Markov chains.


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, open problems and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s