Strong convergence in posets

DOI10.1016/J.JCTA.2012.03.006MaRDI QIDQ423649zbMATHOpenAlexFDO

Authors Amir Ban, Nathan Linial

Publication date 4 June 2012

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

strong convergenceorderposet

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial games (91A46)

Abstract: We consider the following solitaire game whose rules are reminiscent of the children's game of leapfrog. The player is handed an arbitrary ordering $pi=(x_1,x_2,\mathrm{...},x_n)$ of the elements of a finite poset $(P,prec)$. At each round an element may "skip over" the element in front of it, i.e. swap positions with it. For example, if $x_{i}prec{x}_{i+1}$, then it is allowed to move from $pi$ to the ordering $(x_1,x_2,\mathrm{...},x_{i-1},x_{i+1},x_i,x_{i+2},\mathrm{...},x_n)$. The player is to carry out such steps as long as such swaps are possible. When there are several consecutive pairs of elements that satisfy this condition, the player can choose which pair to swap next. Does the order of swaps matter for the final ordering or is it uniquely determined by the initial ordering? The reader may guess correctly that the latter proposition is correct. What may be more surprising, perhaps, is that this question is not trivial. The proof works by constructing an appropriate system of invariants.

Recommendations

• Strong convergence and the polygon property of 1-player games
• scientific article; zbMATH DE number 2124071
• Strong convergence and a game of numbers
• A non-messing-up phenomenon for posets
• scientific article; zbMATH DE number 15085

Cites work

• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 2050057 (Why is no real title available?)
• Reflection Sequences
• Reflection processes on graphs and Weyl groups
• Strong convergence and a game of numbers

Cited in

(2)

• Fertility, Strong Fertility, and Postorder Wilf Equivalence
• Long-concave functions and poset probabilities

This page was built for publication: Strong convergence in posets

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