Berestycki's total-variation mixing conjecture for the giant component of the random transposition walk

About 2 years old · traced to

Let XtX_t be the random transposition walk on the symmetric group, let GtG_t be the graph formed by the transpositions selected up to time tt, and let CtC_t be the largest connected component of GtG_t. Write USCtU_{\mathfrak{S}_{C_t}} for the uniform measure on the permutations of CtC_t, and let dTV⁡d_{\operatorname{TV}} denote total-variation distance.

With notation as above, suppose t≥cn/2t \geq cn/2 for c>1c > 1. Berestycki's conjecture.

dTV⁡(Xt∣Ct,USCt)=on(1).d_{\operatorname{TV}}(X_t|_{C_t}, U_{\mathfrak{S}_{C_t}}) = o_n(1).

The conjecture predicts that, once the associated random graph has entered the supercritical regime and its largest component is macroscopic, the restriction of the random transposition walk to that component is asymptotically uniform in total variation. Results on the cycle lengths of the largest cycles support this prediction, but the full total-variation statement remains open.

References

Primary source

Vishesh Jain and Mehtaab Sawhney, “Hitting time mixing for the random transposition walk”, arXiv:2410.23944 (2024).

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.