$\newcommand{\Cat}{{\rm Cat}}$ $\newcommand{\A}{\mathcal A}$ $\newcommand{\freestar}{ \framebox[7pt]{\star} }$

## 1. Spin systems

Open questions proposed for spin systems, primarily the Ising and Potts models and variants therein.

Recall that the Ising model on a graph $G=(V,E)$ is a distribution on $\Omega=\{\pm 1\}^{V(G)}$ with probability $\mathbb P(\sigma)\propto \exp(\beta \sum_{(i,j)\in E} \sigma_i \sigma_j)\,.$ and the $q$-state Potts model is a random assignment of colors $\sigma\in \{1,...,q\}^{V(G)}$ with probability $\mathbb P(\sigma)\propto \exp(\beta \sum _{(i,j)\in E} \boldsymbol 1\{\sigma_i =\sigma_j\})$
1. ### Universal lower bound for Potts

#### Problem 1.1.

[Yuval Peres] Consider the $q$-Potts model or uniform $q$ proper colorings on a general graph $G$. Is there a universal $\asymp n\log n$ lower bound on the mixing time uniform in the temperature? Is there always an $\frac {n\log n}2$ lower bound?
[Hayes, Sinclair] proved an $\frac {n\log n}d$ lower bound on graphs of maximum degree $d$.

[Ding, Peres] proved an $\frac {n\log n}2$ lower bound for the Ising model on general graphs.
• ### Spin glass with i.i.d. couplings

#### Problem 1.2.

[Andrea Montanari] Consider the spin glass model on $\mathbb{Z}_n^d$ with i.i.d. couplings, i.e. with Hamiltonian given by $$H_n(\sigma)= \sum_{(i,j)\in E_n} J_{ij}\sigma_i\sigma_j\, ,$$ where $J=(J_{ij})$ is a random symmetric matrix with i.i.d. $\pm 1$ entries. The Gibbs distribution is given by $$\mu_n(\sigma)= \frac{1}{Z_n}\exp(\beta H_n)\, .$$ Fix a realization of $J_{ij}$ and consider the Glauber dynamics. Does there exist $\beta_0$ and $\varepsilon>0$ such that, for all $\beta\geq\beta_0$, the mixing time of this chain is at least $\exp(n^\varepsilon)$?
• ### Fast mixing for anti-ferromagnetic Ising at high temperature

#### Problem 1.3.

[Allan Sly] Take a (random) $d$-regular graph, and consider the anti-ferromagnetic Ising model, i.e. $J_{ij}=-1$ for all $i,j$. Can we show show fast mixing $O(n\log n)$ up to $$(d-1)\tanh(\beta)<1 \, ?$$
This is known for the ferromagnetic Ising model, i.e. when $J_{ij}=1$ [Mossel, Sly 2013]. Also known: explicit sampling, decay of correlations.
• ### Mixing time for ferromagnetic Ising at critical temperature

#### Problem 1.4.

[Eyal Lubetzky] What is the mixing time for the ferromagnetic Ising model at critical temperature $\beta=\beta_c$ on a random $d$-regular graph? Is it $n^c$?
• ### Censoring for the Potts model

#### Problem 1.5.

[Yuval Peres] Consider the $q$-state Potts model (say with $q=3$ for concreteness) and start from all green. Is it the case that deterministically censoring a sequence of spin flips can only increase the total variation distance to stationarity?
This is known for monotone chains by [Peres, Winkler].
• ### Diagnostics

We seek diagnostic tests for knowing that a general spin system is mixed on a general graph $G$.

#### Problem 1.6.

1. Consider the ferromagnetic Ising model on a general graph $G$. Which two $x,y\in\Omega$ maximize $\|P^t(x,\cdot)-P^t(y,\cdot)\|_{TV}$? More generally, is it true that in any monotone reversible chain, the maximal and minimal initial configurations maximize the total variation distance between two chains?

2. Can one use a diagnostic to estimate $t_{\mbox{mix}}$ up to $O(1)$? Of course, answering question (1) would answer this as well.

3. Consider the $3$-Potts model for a general graph $G$. Can one devise a diagnostic to differentiate between $t_{\mbox{mix}}=O(n\log n)$ and $\exp(\Omega(n))$?
For monotone spin systems, the answer to (1) is known up to a multiplicative factor that is on the order of the volume of the system. This implies that (2) is known up to $O(\log n)$ using the distance between the all plus and all minus initial configurations.
• ### Noisy majority model

The noisy majority model with parameter $\epsilon\in (0,1)$ is a spin system on a graph $G$ that is the stationary distribution of the following Markov chain on $\Omega=\{\pm 1\}^{V(G)}$: assign each vertex a rate-$1$ Poisson clock. When the clock at a site rings, the spin at that vertex randomizes according to a $\mbox{Ber}(\frac 12)$ with probability $\epsilon$ and chooses the majority of the spins of its neighbors and itself with probability $1-\epsilon$ (flipping a coin in the event of a tie).

#### Problem 1.7.

Consider the noisy majority model on $\mathbb Z_n^d$ for $d>1$. Show there exists a fixed $\epsilon>0$ such that $t_{\mbox{mix}}\gtrsim \exp(n^{\epsilon})$ (should be true for $\exp(cn)$).

Cite this as: AimPL: Markov chain mixing times, available at http://aimpl.org/markovmixing.