Week 8 - lecture 2

Home » Week 8 - lecture 2

LECTURE presentation

Homework

1.* Let $P$ be an irreducible transition matrix on $V$ , and suppose that $f:V \to \mathbb R$ is nonzero and satisfies $Pf=- f$ .

(a) Show that $P^k(x,x)=0$ for all odd $k$ .

(b) Deduce that there is a partition of $V$ into two sets $A,B$ such that if $P^k(x,y)>0$ , then either $x \in A$ and $y \in B$ , or $x \in B$ and $y \in A$ .

2.* Let $P$ be an irreducible transition matrix on $V$ , and suppose that

$f:V \to \mathbb C$ is a nonzero complex eigenfunction, $Pf=\lambda f$ , where $\lambda$ may be complex and $|\lambda|=1$ . Show that there is some positive integer $k$ such that $\lambda^k=1$ . Deduce that $P^j(x,x)=0$ for all $x \in V$ , provided that $j$ is not divisible by $k$ .

2.* Consider the Potts model on an $\ell \times \ell$ square in the lattice. Show that if $\beta$ is a large enough constant, then the mixing time of Glauber dynamics for this Potts model is at least $e^\ell$ .

3. Consider the Potts model on an $n$ vertex graph of maximal degree five. Show that if $\beta \le 10$ , then there is an absolute constant $C$ so that the mixing time of Glauber dynamics for this Potts model is at most $e^{Cn}.$

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.

Week 8 - lecture 2

TOP TOPIC

LECTURE presentation

Video lecture

Homework

Reference

Contact Me