4 problems

Let $G$ be a random $\Delta$-regular bipartite graph, and let $Z_{G,q}(\beta)$ be the partition function of the anti-ferromagnetic $q$-state Potts model on $G$. Random-regular-grap…

Let $\Delta$ be a maximum-degree bound, let $q\ge 2\Delta$, and consider graphs of maximum degree at most $\Delta$. A $q$-list packing assigns colors from each vertex's list so tha…

Bounded-complexity rapid-mixing conjecture. The Markov chain $\mathcal{MC}_{\sf SVT}(\lambda,N,S)$ is rapidly mixing for every $(\lambda,N,S)\in\mathcal{F}_d$.

Mossel–Weitz–Wormald conjecture. Unless $\mathrm{NP}=\mathrm{RP}$, there does not exist a fully polynomial approximation scheme for the partition function of the hardcore model wit…