Wilson's extremal mixing conjecture for random Cayley graphs

About 5 years old · traced to

Let dd and nn diverge with n≤2dn\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

k−log⁡2n≫1,log⁡k≪log⁡n,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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.