Triangular cutoff threshold for the inversion walk on tournaments and the state space of restricted inversions

Abstract

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):=\left(\genfrac{}{}{0ex}{}{s+1}{2}\right)$. For every integer sequence $s_n\in [0,n]$, $$d_n(n-s_n)⟶\{\begin{array}{llc}1,& T(s_n)-n\to +\infty ,0,& T(s_n)-n\to -\infty .\end{array}$$ Consequently, for every fixed $\epsilon \in (0,1)$, $ t_{\mix}^{(n)}(\varepsilon)=n-\sqrt{2n}+O(1).$ We also prove quantitative one-sided bounds, with absolute constants $C_{\star }<0.36$ and $\hat{I}º<3.47$, $$d_n(n+c)\le C_{\star }{2}^{-c}(c\ge 0),d_n(n-s)\ge 1-\hat{I}º2^{n-\left(\genfrac{}{}{0ex}{}{s+1}{2}\right)}(0\le s\le n).$$ As a second result, we characterise the state space of the \emph{$k$-restricted inversion walk}, which inverts a uniformly random $k$-subset at each step. For $n\ge 4$ and $2\le k\le n-2$, the reachable states form a coset of a subgroup $H_k\le\F_2^{\binom{n}{2}}$ whose defining parity constraints are determined by $k\mathrm{mod}4$; equivalently, its codimension is $0,1,n-1$, or $n$ according as $k\equiv 2,0,3$, or $1(\mathrm{mod}4)$.

15 pages