248 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…

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…

Let $(athcal{M},\mathcal{W}^{a,b}_p)$ be the Wasserstein metric space of nonnegative measures on a finite Markov chain with state space $\mathcal{X}$, and let $t\mapsto\mu_t$ be a…

Let $G$ be a graph with vertex set $V$, $d=|V|$ vertices, maximum degree $Delta>1$, and $q$ colors. The Glauber dynamics conjecture. If $q\geq \Delta+\Omega(1)$, then the natural G…

Let a word be generated by an irreducible, doubly-stochastic, cyclic Markov chain on an alphabet of size $m$. Let its associated RSK Young-diagram shape be suitably centered and no…

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 a Markov chain have $n$ states, let $x$ and $y$ be states, and let $\tau_y$ be the hitting time of $y$ starting from $x$. For times $t>n$, consider the interval probability…

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))$.

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

Davies–Perkins conjecture. The down-up walk mixes in polynomial time whenever

Off-critical variance conjecture. There exists $C(p,q,d)\geq1$ such that, as $L\to\infty$,

Let $M$ be an indecomposable, doubly stochastic matrix indexed by an alphabet of size $k$, satisfying … where $k+1\equiv1$. A word of length $N$ is generated by the Markov chain wi…

Let $d\geq 3$, let $\ell>\ell_c(d)$, and let $\mathcal{G}(n,d)$ denote the random $d$-regular bipartite graph model. For a graph $G$ with bipartition $V_1\cup V_2$, let…

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…

Computation-tree correlation-decay conjecture. Correlation decay on the computation tree holds in this regime, at least when the number of colors $q$ is constant.

Purity conjecture. Any strongly clustering entangled Markov chain should generate a pure state on

Markov-chain approximation conjecture. As the diameter of the partition $\{\Delta_i\}_{i=1}^{W}$ tends to zero, a number of statistical features of the map $T$ can be obtained as l…

Contingency-table norm conjecture. For arbitrary table dimensions $m$ and $n$, table sum $\Sigma$, and row and column sums $r_k$ and $c_p$, this multi-decomposition is non-degenera…

Exact spectral-gap conjecture. The inequality relating the $m$-urn and two-urn gaps is an equality:

Consider the single-site nonlinear dynamics for the hard-core model on a graph of maximum degree $Delta$, in the density regime where the paper proves qualitative convergence. Exte…

Let $G$ be a graph and consider the mean-field and single-site nonlinear dynamics for the hard-core model in the irreducibility region covered by the paper's qualitative convergenc…

Let $H$ be a graph, let $Delta(H)$ denote its maximum degree, and let $q$ be a positive integer. Optimal-mixing conjecture. Glauber dynamics for proper $q$-colorings of $H$ should…