56 problems

$k$-ball cutoff conjecture. For $k=o(n)$, the balanced chain exhibits cutoff around the time

Mixing-time and cutoff conjecture. The following claims should hold:

Let $G$ be a connected regular graph on $n$ vertices, and let $\tau$ denote the relaxation time of its random walk, defined by … where $\eta_2$ is the second-largest eigenvalue of…

Let $Q_n$ be a uniform quadrangulation with $n$ vertices, let $Q_n^\dagger$ be its dual, and let $\tau_{Q_n}(\varepsilon)$, $\tau_{Q_n^\dagger}(\varepsilon)$ denote uniform mixing…

Let $G$ and $H$ be finite graphs that are $K$-roughly isometric, and suppose both have maximal degree at most $d$. Denote by $\tau_{\infty}(G)$ and $\tau_{\infty}(H)$ the…

Optimality conjecture. Under Assumption, $t_\gamma$ is optimal up to logarithmic factors.

Let $n$ particles evolve according to the Attracting Random Walks (ARW) model on an arbitrary graph, with interaction parameter $\beta<0$. The mixing time is measured with respect…

Let $(T_n(k))_{k \geq 0}$ denote the flip walk on triangulations of the sphere with $n$ vertices, and let its mixing time be measured with respect to the uniform distribution on su…

Let the graph be the $m$-dimensional torus with $n$ nodes, and let $\tau^\star$ denote the mixing time of the directed-edge process associated with consensus propagation. Consensus…

Let $m$ be the number of edges, let $n_0(\mathcal D)$ denote the number of vertices of degree zero, let $m^{\neq 2}$ denote the number of edges incident to vertices whose degrees a…

Multi-stack and restricted shuffle cutoff conjecture. Both chains exhibit cutoff, with the multi-stack chain around time

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…

Consider, for $n\geq 2$, the random transposition shuffle $(X_t^{(n)})_{t\geq 0}$ on the symmetric group $\mathfrak{S}_n$, in discrete or continuous time, and let…

Fix an arbitrary order on the positions of the corners of a Rubik's cube. Let $X_t$ denote the configuration of the cube at time $t$, and call two corners unlinked when they are un…

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

Let $X_t$ be the random transposition walk on the symmetric group, let $G_t$ be the graph formed by the transpositions selected up to time $t$, and let $C_t$ be the largest connect…

Let $P$ be the transition matrix of the biased random transposition shuffle on $N$ cards, let $U$ be the uniform distribution on permutations, let $d_{\operatorname{TV}}$ denote to…

Folklore conjecture. Let $\delta>0$ be a constant. If

Let $\mathcal G_\Delta$ be the class of graphs under consideration, let $\hat{\mu}_{G,\beta,\eta}$ be the fixed-magnetization Ising measure on $G\in\mathcal G_\Delta$, and let…

Let $N$ be the number of positions and let $k=o(N^{1/2})$. Denote by $t_{\mathrm{mix}}(\varepsilon)$ and $t_{\mathrm{mix}}^{\prime}(\varepsilon)$ the $4\varepsilon$4-mixing times o…

Let $G$ be a graph of maximum degree $\Delta$, and consider the Glauber dynamics for sampling proper $q$-colorings of $G$. Jerrum's conjecture. The Glauber dynamics for sampling…

Consider the symmetric simple exclusion process with reservoirs on a segment of size $N$, with parameters $p$ and $q$, and let $t^*$ denote the characteristic mixing-time scale. In…

Jara's conjecture. The mixing time is of order

Lacoin's conjecture. The mixing time is of order

Let $u$ be the uniform driving sequence on $B_r = B(0,r) \cap \mathbb{Z}^d$. Let $0 < \lambda < \infty$ be a constant sleep rate, and let $P$ be the simple random walk on $B_r$ wit…