# Week 8 - lecture 2

## TOP TOPIC

Date: 01/09/22

8.3. Lower bound for the trace of a transition matrix
8.4. The 3-1 tree
8.5. Proving fast mixing for Potts model via contraction
8.6. Swendsen-Wang dynamics and the random cluster model

## Homework

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

## Reference

[1] Glasner, Shmuel.
Almost periodic sets and measures on the torus.
Israel J. Math. 32 (1979), no. 2-3, 161–-172.

[2] Berend, Daniel and Peres, Yuval.
Asymptotically dense dilations of sets on the circle.
J. London Math. Soc. (2) 47 (1993), no. 1, 1–-17.

[3] N. Alon and Y. Peres, "Uniform dilations'', Geometric and Functional Analysis, vol. 2, No. 1 (1992), 1–28.

[4] Nair, R. and Velani, S. L.
Glasner sets and polynomials in primes.
Proc. Amer. Math. Soc. 126 (1998), no. 10, 2835–-2840.