Tighter Bounds on the Expected Absorbing Time of Ungarian Markov Chains
| Autor: | Shen, Eric |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | In 2023, Defant and Li defined the Ungarian Markov chain associated to a 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$. They defined $\mathcal{E}(L)$ to be the expected number of steps until the maximal element $\hat{1}$ of $L$ transitions into the minimal element $\hat{0}$ in the Ungarian Markov chain, and investigated its asymptotics when $L$ is the weak order on $S_n$, or the $n$th Tamari lattice $\textrm{Tam}_n$. This paper resolves a conjecture of Defant and Li and makes partial progress towards another, by proving that $\mathcal{E}(S_n)$ is linear in $n$, and proving an $n^{1 - o(1)}$ lower bound on $\mathcal{E}(\textrm{Tam}_n)$. Comment: 26 pages, 4 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|