Ungarian Markov chains

DOI10.1214/23-EJP1056arXiv2301.08206OpenAlexW4389351736MaRDI QIDQ6136831FDOQ6136831

Rupert Li, Colin Defant

Publication date: 17 January 2024

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

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.

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)

Cites Work

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

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)