1.* Let be an irreducible transition matrix on
, and suppose that
is nonzero and satisfies
.
(a) Show that for all odd
.
(b) Deduce that there is a partition of into two sets
such that if
, then either
and
, or
and
.
2.* Let be an irreducible transition matrix on
, and suppose that
is a nonzero complex eigenfunction,
, where
may be complex and
. Show that there is some positive integer
such that
. Deduce that
for all
, provided that
is not divisible by
.
2.* Consider the Potts model on an square in the lattice. Show that if
is a large enough constant, then the mixing time of Glauber dynamics for this Potts model is at least
.
3. Consider the Potts model on an vertex graph of maximal degree five. Show that if
, then there is an absolute constant
so that the mixing time of Glauber dynamics for this Potts model is at most