Triangular cutoff threshold for the inversion walk on tournaments and the state space of restricted inversions
Given a labelled tournament on $[n]$, \emph{inverting} a vertex subset $X$ means reversing every edge with both endpoints in $X$. Alon, Powierski, Savery, Scott, and Wilmer~\cite{AlonPowierskiSaveryScottWilmer2024} asked for the mixing time of the Markov chain that repeatedly inverts a uniformly random subset of $[n]$. We show that this \emph{inversion walk} has a triangular cutoff threshold. Let $T(s):=\binom{s+1}{2}$. For every integer sequence $s_n\in[0,n]$, $$ d_n(n-s_n)\longrightarrow \begin{cases} 1,& T(s_n)-n\to+\infty, 0,& T(s_n)-n\to-\infty. \end{cases} $$ Consequently, for every…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2603.01368
curl -X POST /api/v1/records/arxiv/2603.01368/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.01368/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'