Centre for Discrete and Applicable Mathematics
	CDAM Research Report, LSE-CDAM-2000-01 January 2000

Abstract

Probability measures on the space of proper colorings of a Cayley tree (that is, an infinite regular connected graph with no cycles) are of interest not only in combinatorics but also in statistical physics, as states of the antiferromagnetic Potts model at zero temperature, on the ``Bethe lattice''.

We concentrate on a particularly nice class of such measures which remain invariant under parity-preserving automorphisms of the tree. Making use of a correspondence with branching random walks on certain bipartite graphs, we determine when more than one such measure exists. The case of ``uniform'' measures is particularly interesting, and as it turns out, plays a special role.

Some of the results herein are deducible from previous work of the authors and by members of the statistical physics community, but many are new. We hope that this work will serve as a helpful glimpse into the rapidly expanding intersection of combinatorics and statistical physics.

A compressed (gzip) PostScript file (256 kB) with the full contents of this report can be downloaded by clicking here.

Alternatively, if you like a free hard copy of this report, please send the number of this report, LSE-CDAM-2000-01, together with your name and postal address to:

		CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K.
		Phone: +44(0)-20-7955 7732. Fax: +44(0)-20-7955 6877. Email: info@maths.lse.ac.uk

		Introduction to the CDAM Research Report Series.
		CDAM Homepage.

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html.