The poset of king permutations on a cylinder

Abstract

A permutation $\sigma =[{\sigma }_1,\dots ,{\sigma }_n]\in S_n$ is called a {\em cylindrical king permutation} if $|{\sigma }_{i+1}-{\sigma }_i|>1$ for each $1\le i\le n-1$ and $|{\sigma }_1-{\sigma }_n|>1$. The name comes from the the way one can see these permutations as describing locations of $n$ kings on a chessboard of order $n\times n$ in such a way that (each row and each column contains exactly one king and) no two kings are attacking each other, with the additional condition that a king can move off a certain row and reappear at the beginning of that row. In a recent paper, we dealt with the more general set of 'king permutations' i.e. the ones which satisfy only the first of the two conditions above. This set constitutes a poest under the well known containment relation on permutations. In this article we investigate the sub-poset of the cylindrical king permutations and its structure. We examine those cylindrical king permutations whose downset is as large as possible in the upper ranks. We use a modification of Manhattan distance of the plot of a permutation and some of its applications to the cylindrical context to find a criterion for such a permutation to be $k-$ prolific. One of our main results is that the maximal gap between two permutations in the poset of cylindrical permutations is $4$.

References in corpus (2)

• Separators - a new statistic for permutations
• Counting King Permutations on the Cylinder