195 problems

Let $G$ be a random $\Delta$-regular bipartite graph on $2n$ vertices, and consider the anti-ferromagnetic $q$-state Potts model on $G$. Phase-transition conjecture. Whenever the p…

Fix $k\ge 2$, and for each $n$ let $K_n$ be the Burnside process on $(C_k^n,S_n)$. Consider starting states whose limiting empirical distribution on $C_k$ assigns a positive propor…

Let $(G_n)_{n\geq 1}$ be a sequence of finite rooted graphs, and let $t^n_{\textup{mix}}(\varepsilon)$ be the total-variation mixing time of the continuous-time simple random walk…

Aldous's conjecture. The relaxation time of the triangulation flip walk should be $\Theta(n^{3/2})$. This is a classical mixing-time conjecture for a Catalan structure; the supplie…

Maximal-current mixing-time conjecture. Theorem 1 remains valid in the maximal current phase for general $A,C\leq 1$.

Oliveira's conjecture. The mixing time of the interchange process on $G$ should be of the same order as the mixing time of the product chain.

Let $d$ and $n$ diverge with $n\leq 2^d$, let $G$ be a group of order $n$, and let $H=\mathbb{Z}_2^d$. For fixed $\varepsilon,\varepsilon'\in(0,1)$, write…

Peres's cutoff conjecture. A process exhibits cutoff if and only if it satisfies the product condition

Consider the Edwards–Anderson spin-glass model on a sparse random graph drawn from $\mathbold{G}(n,d/n)$, with inverse temperature $\beta>0$ satisfying … where $\mathbold{J}$ is a…

Consider the product replacement chain on the space of generating $n$-tuples … for a fixed finite group $G$, and let $C_G$ be a constant depending only on $G$. The chain has a unif…

Kozma's conjecture. The mixing time of a bounded-degree graph should be robust, up to constant factors, under rough isometry.

Let $q\geq 2$ and let $\beta_s$ denote the critical inverse temperature for the mean-field ferromagnetic Potts model. Consider the systematic scan dynamics at the critical temperat…

Kannan's conjecture. The swap chain mixes in polynomial time for every feasible choice of row and column sums.

Let $S_n$ be the symmetric group, and consider the general biased adjacent transposition shuffle in which an adjacent pair of elements $i$ and $j$ is selected and $i$ is placed ahe…

Fast mixing conjecture. The mixing time of the face-flip Markov chain on $T_{m,n}$ is $O(mn \log(mn))$.

Quadratic mixing-time conjecture. The correct order of the mixing time in Theorem 2 is $N^2$.

Diaconis's mixing-time conjecture. The mixing time of the torus shuffle is

Consider the non-conservative symmetric simple exclusion process on a segment of size $N$ with reservoirs, and let $t_{\mathrm{mix}}(\epsilon)$ denote its mixing time for fixed…

The mixing time is the time required for a Markov particle system to approach its stationary distribution. A particle system is in the maximal current phase when its stationary par…

Consider a general configuration model with a power-law degree sequence, and let $t_{\text{mix}}$ denote its mixing time. Polylogarithmic mixing-time conjecture. The known mixing r…

Lifshitz's law. The mixing time $T_{\rm mix}$ should be of order $L^2$. This conjecture predicts diffusive scaling for the time required by the zero-temperature stochastic Ising dy…

Constant mixing-time conjecture. The mixing time $\tau(G_{s,\beta}(N))$ is constant, independent of $N$.

Let a random $d$-regular graph be percolated by deleting each edge independently with probability $1-p$, and suppose that $p>1/(d-1)$ is fixed. Let $T$ denote the mixing time of th…

In the critical case $c=1$, consider the largest cluster of a random graph, whose diameter is of order $n^{1/3}$, and let $T$ denote the mixing time of random walk on the cluster.…

Let $\mathbb{P}$ be a Markov chain on state space $\mathcal{X}$, let $\gamma>0$, and define $\mathbf{Z}_S^{\gamma}$ as the number of states visited fewer than $\gamma$ times up to…