Rowmotion Markov chains

DOI10.1016/J.AAM.2023.102666MaRDI QIDQ6153614zbMATH OpenOpenAlexWikidataFDO

Authors Colin Defant, Rupert Li, Evita Nestoridi

Publication date 14 February 2024

Published in Advances in Applied Mathematics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Structure and representation theory of distributive lattices (06D05) Other generalizations of distributive lattices (06D75) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: Rowmotion is a certain well-studied bijective operator on the distributive lattice $J(P)$ of order ideals of a finite poset $P$. We introduce the rowmotion Markov chain $$ by assigning a probability $p_x$ to each $xinP$ and using these probabilities to insert randomness into the original definition of rowmotion. Barnard and Thomas--Williams extended the definition of rowmotion from distributive lattices to semidistributive lattices and trim lattices, respectively. Recently, the first author and Williams further generalized rowmotion to the even broader class of semidistrim lattices. Given a semidistrim lattice $L$, we assign a probability $p_j$ to each join-irreducible element $j$ of $L$ and use these probabilities to construct a rowmotion Markov chain $$. Under the assumption that each probability $p_j$ is strictly between $0$ and $1$, we prove that $$ is irreducible. We bound the mixing time of $$ for an arbitrary semidistrim lattice $L$, and we provide more precise bounds when $L$ is a chain or a Boolean lattice. We compute the stationary distribution of $$ for an arbitrary finite poset $P$. We also compute the stationary distribution of the rowmotion Markov chain of the lattice obtained from a disjoint union of two chains $x_1<cdots<x_a$ and $y_1<cdots<y_b$ by adding a minimal element and a maximal element.

Cites work

• P-strict promotion and B-bounded rowmotion, with applications to tableaux of many flavors
• Antichain toggling and rowmotion
• Cambrian lattices.
• Clusters, Coxeter-sortable elements and noncrossing partitions
• Combinatorial Markov chains on linear extensions
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Promotion and rowmotion
• Properties of the promotion Markov chain on linear extensions
• Rowmotion and generalized toggle groups
• Rowmotion in slow motion
• Semidistrim Lattices
• The canonical join complex
• The CDE property for skew vexillary permutations
• Toggling independent sets of a path graph
• Unified theory for finite Markov chains

This page was built for publication: Rowmotion Markov chains

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