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