Wilson's extremal mixing conjecture for random Cayley graphs

From papers

Let dd and nn diverge with n2dn\leq 2^d, let GG be a group of order nn, and let H=Z2dH=\mathbb{Z}_2^d. For fixed ε,ε(0,1)\varepsilon,\varepsilon'\in(0,1), write tmix(ε,Gk)t_{\mathrm{mix}}(\varepsilon,G_k) for the mixing time of the random walk on GkG_k. Wilson's conjecture. If

klog2n1,logklogn,k-\log_2 n\gg 1,\qquad \log k\ll\log n,

then, with high probability,

tmix(ε,Gk)tmix(ε,Hk)1+o(1).\frac{t_{\mathrm{mix}}(\varepsilon,G_k)}{t_{\mathrm{mix}}(\varepsilon',H_k)}\leq 1+o(1).

Thus the random walk on GkG_k is no slower than that on Z2dk\mathbb{Z}_2^d{}_k, up to lower-order terms. The paper proves the corresponding statement for Abelian groups, but the all-groups conjecture remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Jonathan Hermon and Sam Olesker-Taylor, “Cutoff for Almost All Random Walks on Abelian Groups”, arXiv:2102.02809 (2025).

Solutions 0

No solutions have been posted yet.