Tighter bounds on the expected absorbing time of Ungarian Markov chains

Source abstract

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