Strong convergence in posets

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

p i = (x_{1}, x_{2}, ..., x_{n})

of the elements of a finite poset

(P, p r e c)

. 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} p r e c x_{i + 1}

, then it is allowed to move from

p i

to the ordering

(x_{1}, x_{2}, ..., x_{i - 1}, x_{i + 1}, x_{i}, x_{i + 2}, ..., 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.

Review text

The following solitaire game is considered. The game is played on a poset \((P,\prec)\) with n elements. The player is handed an arbitrary permutation \(\pi=(x_{1},x_{2},\dots,x_{n})\) of the elements in \(P\). At each round an element may swap positions with a smaller element preceding it. For example, if \(x_{i}\prec x_{i+1}\), then it is allowed to move from \(\pi\) to the permutation \((x_{1},x_{2},\dots,x_{i-1},x_{i+1},x_{i},x_{i+2},\dots,x_{n})\) of \(P\)'s elements. 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. It is shown that the final permutation is uniquely determined by the initial order of \(P\)'s elements. The proof works by constructing an appropriate system of invariants.

Recommendations

Cites work

Cited in

(3)

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)