View PDF HTML (experimental)

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):=\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 fixed $\varepsilon\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 $\kappa<3.47$, $$
d_n(n+c)\le C_\star 2^{-c}\quad(c\ge0),
\qquad
d_n(n-s)\ge 1-\kappa\,2^{\,n-\binom{s+1}{2}}\quad(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\bmod 4$; equivalently, its codimension is $0,1,n-1$, or $n$ according as $k\equiv2,0,3$, or $1\pmod4$.

Submission history

From: Jiangdong Ai [view email]
[v1] Mon, 2 Mar 2026 02:04:26 UTC (8 KB)
[v2] Fri, 6 Mar 2026 06:11:59 UTC (12 KB)
[v3] Sat, 11 Jul 2026 01:00:22 UTC (15 KB)