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

From papers

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 dTVd_{\operatorname{TV}} denote total-variation distance.

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

dTV(XtCt,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.

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

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

Solutions 0

No solutions have been posted yet.