Tighter Bounds on the Expected Absorbing Time of Ungarian Markov Chains

Abstract

In $2023$, Defant and Li defined the Ungarian Markov chain ${\mathbf{U}}_L$ associated to a finite lattice $L$. This Markov chain has state space $L$, and from any state $x\in L$ transitions to the meet of $\{x\}\cup T$, where $T$ is a randomly selected subset of the elements of $L$ covered by $x$. For any lattice $L$, let $\mathcal{E}(L)$ be the expected number of steps until the maximal element of $L$ transitions into the minimal element in the Ungarian Markov chain. We show that $\mathcal{E}(L)$ is linear in $n$ when $L$ is the weak order on the symmetric group $S_n$, and satisfies an $n^{1-o(1)}$ lower bound when $L$ is the $n^{\text{th}}$ Tamari lattice. This completely resolves a conjecture by Defant and Li and partially resolves another.

41 pages, 9 figures