Ungarian Markov chains

DOI10.1214/23-EJP1056MaRDI QIDQ6136831OpenAlexFDO

Authors Colin Defant, Rupert Li

Publication date 17 January 2024

Published in Electronic Journal of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2301.08206

zbMATH Keywords

Markov chainCoxeter groupweak orderCambrian latticeTamari latticetrim lattice

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Structure theory of lattices (06B05) Other generalizations of distributive lattices (06D75) Combinatorial aspects of groups and algebras (05E16)

Abstract: We introduce the Ungarian Markov chain $$ associated to a finite lattice $L$. The states of this Markov chain are the elements of $L$. When the chain is in a state $xinL$, it transitions to the meet of $xcupT$, where $T$ is a random subset of the set of elements covered by $x$. We focus on estimating $mathcalE(L)$, the expected number of steps of $$ needed to get from the top element of $L$ to the bottom element of $L$. Using direct combinatorial arguments, we provide asymptotic estimates when $L$ is the weak order on the symmetric group $S_n$ and when $L$ is the $n$-th Tamari lattice. When $L$ is distributive, the Markov chain $$ is equivalent to an instance of the well-studied random process known as last-passage percolation with geometric weights. One of our main results states that if $L$ is a trim lattice, then $mathcalE(L)leqmathcalE(extspine(L))$, where $extspine(L)$ is a specific distributive sublattice of $L$ called the spine of $L$. Combining this lattice-theoretic theorem with known results about last-passage percolation yields a powerful method for proving upper bounds for $mathcalE(L)$ when $L$ is trim. We apply this method to obtain uniform asymptotic upper bounds for the expected number of steps in the Ungarian Markov chains of Cambrian lattices of classical types and the Ungarian Markov chains of $u$-Tamari lattices.

Cites work

• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 3955215 (Why is no real title available?)
• scientific article; zbMATH DE number 4002104 (Why is no real title available?)
• scientific article; zbMATH DE number 3178652 (Why is no real title available?)
• scientific article; zbMATH DE number 3722110 (Why is no real title available?)
• scientific article; zbMATH DE number 3779340 (Why is no real title available?)
• scientific article; zbMATH DE number 7524066 (Why is no real title available?)
• 2N noncollinear points determine at least 2N directions
• A recursion on maximal chains in the Tamari lattices
• A stack and pop stack in series
• An analogue of distributivity for ungraded lattices
• Cambrian fans.
• Cambrian lattices.
• Chains of maximum length in the Tamari lattice.
• Circular support in random sorting networks
• Clusters, Coxeter-sortable elements and noncrossing partitions
• Combinatorial frameworks for cluster algebras
• Counting smaller elements in the Tamari and \(m\)-Tamari lattices
• Enumerating permutations sortable by \(k\) passes through a pop-stack
• Essential Chains and Homotopy Type of Posets
• Geometry of $\nu $-Tamari lattices in types $A$ and $B$
• Higher trivariate diagonal harmonics via generalized Tamari posets
• Local statistics for random domino tilings of the Aztec diamond
• Non-equilibrium behaviour of a many particle process: Density profile and local equilibria
• Noncrossing partitions and representations of quivers.
• On the Sets of Directions Determined by n Points
• On the maximum and its uniqueness for geometric random samples
• On the wildness of Cambrian lattices
• Pop-stack-sorting for Coxeter groups
• Random sorting networks
• Rings of sets
• Rowmotion in slow motion
• Sortable elements and Cambrian lattices.
• The Archimedean limit of random sorting networks
• The Directions Determined by n Points in the Plane
• The enumeration of generalized Tamari intervals
• The local limit of random sorting networks
• The number of intervals in the \(m\)-Tamari lattices
• The pop-stack-sorting operator on Tamari lattices
• The representation of the symmetric group on \(m\)-Tamari intervals
• The surprising mathematics of longest increasing subsequences
• Two-stack-sorting with pop stacks

Cited in

(1)

• The Ungar games

This page was built for publication: Ungarian Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6136831)