Pattern-avoiding shallow permutations

Kassie Archer, Aaron Geary, Robert P. Laudone · 2024

Read Pattern-avoiding shallow permutations by Kassie Archer, Aaron Geary, Robert P. Laudone (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-11999.txt.

Introduction

Kassie Archer, Aaron Geary, and Robert Laudone study shallow permutations, a special class in combinatorics, in a 2024 paper. Shallow permutations were defined in 1977 as those meeting a lower bound in a known inequality. Recent work has renewed interest in them, linking them to pattern rules in their cycle form and to unlinked cycle diagrams. One famous case, shallow permutations that avoid the pattern 321, shows up in many settings.

The authors ask which shallow permutations avoid each pattern of length three. They first prove broad structural results about shallow permutations in general. Then they apply those results to count the avoiders for every length-three pattern. The counts complete the picture for this size and give later work a firm base to build on.

Catalog record

CREATORKassie Archer, Aaron Geary, Robert P. Laudone
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE80 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-11999

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Pattern-avoiding shallow permutations Kassie Archer, Aaron Geary, Robert P. Laudone Abstract Shallow permutations were defined in 1977 to be those that satisfy the lower bound of the Diaconis-Graham inequality. Recently, there has been renewed interest in these permutations. In particular, Berman and Tenner showed they satisfy certain pattern avoidance conditions in their cycle form and Woo showed they are exactly those whose cycle diagrams are unlinked. Shallow permutations that avoid 321 have appeared in many contexts; they are those permutations for which depth equals the reflection length, they have unimodal cycles, and they have been called Boolean permutations. Motivated by this interest in 321-avoiding shallow permutations, we investigate σ \sigma -avoiding shallow permutations for all σ ∈ 𝒮 3 \sigma\in\mathcal{S}_{3} . To do this, we develop more general structural results about shallow permutations, and apply them to enumerate shallow permutations avoiding any pattern of length 3. 0 0 footnotetext: Keywords: permutations; avoidance; shallow; enumeration. 1 Introduction and background Let \mathcal{S}_{n} denote the set of permutations on [n]=\{1,2,\ldots,n\} and we write these permutations in their one-line notation as \pi=\pi_{1}\pi_{2}\ldots\pi_{n} where \pi_{i}:=\pi(i) . There are multiple measures of disorder or disarray of a permutation \pi\in\mathcal{S}_{n} . Three of these, namely the total displacement D(\pi) , the length I(\pi) , and the reflection length T(\pi) , are connected by the Diaconis-Graham inequalities [ 4 ] : I(\pi)+T(\pi)\leq D(\pi)\leq 2\,I(\pi). Here, the total displacement D(\pi) , also called Spearman’s measure of disarray, is given by D(\pi)=\sum_{i=1}^{n}|\pi_{i}-i|. The length I(\pi) is equal to the minimal number of simple transpositions required to produce \pi . It is also called the inversion number and is given by I(\pi)=\sum_{i=1}^{n}|\{i<j\;|\;\pi_{i}>\pi_{j}\}|. The reflection length T(\pi) is the minimal number of transpositions required to produce \pi from the identity permutation, which was shown by Cayley in 1849 to be T(\pi)=n-\cyc(\pi), where \cyc(\pi) denotes the number of cycles in the disjoint cycle decomposition of \pi. It is well-known that the upper Diaconis-Graham inequality is achieved, i.e., D(\pi)=2I(\pi) , when \pi avoids the pattern 321, meaning there is no set of indices i<j<k with \pi_{i}>\pi_{j}>\pi_{k} . A permutation is called shallow when it satisfies the lower inequality, i.e., when I(\pi)+T(\pi)=D(\pi) . We note that shallow permutations have recently been investigated from various perspectives: In [ 2 ] , the authors use pattern functions to characterize the cycle form of these permutations in terms of pattern-avoidance, and in [ 14 ] , the author proves that shallow permutations are exactly those permutations whose cycle diagram is equivalent to the unknot when viewed as a knot diagram. Permutations which satisfy both the upper and lower bound of the Diaconis-Graham inequalities have been well-studied in their own right. These permutations are exactly those that are shallow 321-avoiding permutations; these have been called Boolean permutations [ 10 , 11 , 13 ] , unimodal permutations [ 5 ] (because of their unimodal cycle form), and are characterized as avoiding both 321 and 3412 [ 9 ] . It was stated, without proof, in [ 4 ] , that these permutations are enumerated by F_{2n-1} , the (2n-1) -st Fibonacci number. A proof of this fact does appear in other places, including [ 9 ] , and we provide an independent proof of this fact in this paper, directly using shallowness. Motivated by this interesting answer regarding 321-avoiding shallow permutations, in this paper we investigate shallow permutations which avoid \sigma for \sigma\in\mathcal{S}_{3} . In Section 2 , we describe certain properties of general shallow permutations which we use in follow-on sections. In particular, we show how to build shallow permutations from smaller ones, and we prove that all shallow permutations necessarily avoid certain mesh patterns. In Sections 3 , 4 , 5 , and 6 we enumerate \sigma -avoiding shallow permutations for \sigma\in\mathcal{S}_{3} . Additionally, we enumerate \sigma -avoiding shallow permutations by number of descents and by three symmetry properties. In particular, we enumerate those shallow \sigma -avoiding permutations that are fixed under inverse, reverse-complement, and reverse-complement-inverse. The sections are ordered by the complexity of the proofs involved, with the exception of \sigma=321 , which we do last since these have been investigated in previous papers. We conclude the paper with open questions and directions for future study. \sigma number of shallow \sigma -avoiding permutations Theorem 132 t_{n}(\sigma)=F_{2n-1} Theorem 3.1 213 231 g.f. T_{\sigma}(x)=\dfrac{1-3x+2x^{2}-x^{3}-x^{4}-x^{5}}{1-4x+4x^{2}-2x^{3}-x^{4}-x^{5}} Theorem 4.1 312 123 g.f. T_{\sigma}(x)=\dfrac{1-3x+11x^{3}-13x^{4}+7x^{5}+6x^{6}+3x^{7}}{(1-x)^{4}(1-4x^{2}+x^{4})} Theorem 5.1 321 t_{n}(\sigma)=F_{2n-1} Theorem 6.1 Table 1: In this table, t_{n}(\sigma) denotes the number of shallow permutations avoiding a given pattern \sigma , and T_{\sigma}(x)=\sum_{n\geq 0}t_{n}(\sigma)x^{n} is the corresponding generating function. 2 Structure of shallow permutations Let \mathcal{T}_{n} denote the permutations \pi\in\mathcal{S}_{n} that are shallow and let t_{n}=|\mathcal{T}_{n}| . We will often make use of the following recursive formulation of shallow permutations that is due to Hadjicostas and Monico [ 7 ] . Theorem 2.1 . [ 7 , Theorem 4.1] Suppose \pi\in\mathcal{S}_{n} and for n\geq 2 , define \pi^{R}=\begin{cases}\pi_{1}\pi_{2}\ldots\pi_{n-1}&\pi_{n}=n\\ \pi_{1}\pi_{2}\ldots\pi_{j-1}\pi_{n}\pi_{j+1}\ldots\pi_{n-1}&\pi_{j}=n\text{ with }j<n\end{cases} Then \pi=1\in\mathcal{S}_{1} is shallow, and when n\geq 2, • if \pi_{n}=n , then \pi is shallow exactly when \pi^{R} is, and • if \pi_{j}=n with j<n , then \pi is shallow exactly when \pi^{R} is shallow and \pi^{R}_{j}=\pi_{n} is a left-to-right maximum or right-to-left minimum in \pi^{R} . Let us see an example. Suppose \pi=421635\in\mathcal{T}_{6} , a shallow permutation of 6 elements. Notice \pi_{4}=6 , and \pi_{6}=5 ; applying the \pi^{R} map we see 421\underline{\mathbf{6}}3\underline{\mathbf{5}}\xlongrightarrow{\pi^{R}}421\underline{\mathbf{5}}3, and 42153 is \in\mathcal{T}_{5} . Notice that we can use the inverse of this map to construct new shallow permutations from old ones. Given any \tau\in\mathcal{T}_{n-1} and any position i for which \tau_{i} is either a left-to-right maximum or a right-to-left minimum, we can construct a permutation \pi for which \pi^{R}=\tau by taking \pi_{j}=\tau_{j} for j\neq i , \pi_{i}=n , and \pi_{n}=\tau_{i}. Notice that we can get every shallow permutation on [n] from the shallow permutations on [n-1] in this way since every shallow permutation \pi\in\mathcal{T}_{n} has an image \tau=\pi^{R} in \mathcal{T}_{n-1}. We will define a similar operation \pi^{L} which acts on the left of \pi . To this end, let us define certain symmetries of permutations in general. We also give the names of permutations which are fixed under these symmetries, which will be relevant throughout this paper. • We denote by \pi^{-1} the algebraic inverse of \pi. That is, \pi^{-1}_{j}=i if and only if \pi_{i}=j . This corresponds to a reflection of the diagram of the permutation (given by points (j,\pi_{j}) for each j\in[n] ) about the main diagonal. Permutations which are their own inverse are called involutions . • We define \pi^{rc} to be the reverse-complement of \pi , so that \pi^{rc}_{n+1-i}=n+1-j if \pi_{i}=j . This corresponds to a 180^{\circ} rotation of the diagram of the permutation. Permutations satisfying \pi=\pi^{rc} are called centrosymmetric ; see for example [ 6 , 8 ] . • Finally, let \pi^{rci}:=(\pi^{rc})^{-1} be the reverse-complement-inverse of the permutation, corresponding to the reflection of the diagram of the permutation about the anti-diagonal. We will refer to permutations satisfying \pi=\pi^{rci} as persymmetric . In the following proposition we show that each of these three symmetries preserves shallowness. Proposition 2.2 . If \pi is shallow, then so are the permutations \pi^{-1} , \pi^{rc}, and \pi^{rci} . Proof. To see that \pi^{-1}\in\mathcal{T}_{n} notice first that

Read the complete text