 |
Discrete Mathematics & Theoretical Computer Science |
vol. 22 no. 2, Permutation Patterns 2019
Special issue: Permutation Patterns 2019
----------------------------------------
The *Permutation Patterns* conference series was initiated in 2003, with a first meeting organized by Michael Albert and Mike Atkinson at the university of Otago, New Zealand. At this first conference of the series, three days of talks were the occasion of sharing results and challenges about the enumeration of pattern-avoiding permutations, a research area which was gaining popularity at the time.
Twenty years after, some challenges were solved, others remain open, and more were discovered. One sure thing is that the conference has become wider, both in terms of topics and of number of attendees. Next to permutations, many other structures and their patterns are now discussed during our meetings (like lattice paths, set partitions, or tree, to name a few). In addition to enumerative combinatorics, other points of view attracted attention (like computationnal complexity, algebra, or probability theory). And the 2019 edition of the conference gathered 65 participants, from all over the world.
This volume follows the 2019 edition of the *Permutation patterns* conference, which was held in Zürich, during the week June 17-21, 2019. This 2019 meeting was preceded by a 3-day introductory workshop, primarily intended for students or researchers entering the research area. This meeting was a success, gathering 37 participants for four mini-courses by junior researchers.
The articles gathered in this volume are a sample of some topics currently of interest in the research on permutation patterns. Some of the results were presented during the conference, but not all.
The call for papers for this special volume of DMTCS closed on December 31st, 2019, just before Covid hit our world. The final articles were published only early 2023, and the pandemic is the main culprit which prevented us from putting this volume together faster. The additional article \[1\] should actually have been included in this volume, had we (editors) been faster in publishing it. This article has been fully refereed, but the author left academia before we asked him to provide a revision accommodating minor changes.
We thank all authors who contributed their work to this volume, the referees for their expert opinion and constructive feedback, and Jens Gustedt for his support as DMTCS editor-in-chief. We are also grateful to the Permutation Patterns community in general, for making our yearly meetings a friendly place to learn new results and have scientific exchanges in a relaxed atmosphere. After two years of virtual meeting in 2020 and 2021, we have all been very grateful to meet again in person at the Valparaiso meeting in 2022, and look forward to the 20th anniversary of the conference in 2023 in Dijon!
**Miklós Bóna**, University of Florida — Gainesville, USA
**Mathilde Bouvel**, Loria, CNRS and Univ. Lorraine, France
**Lara Pudwell**, Valparaiso University, USA
**Vincent Vatter**, University of Florida — Gainesville, USA
**Reference**
\[1\] Sam Miner, Enumeration of several two-by-four classes, Arxiv preprint 1610.01908,
1. Bounded affine permutations I. Pattern avoidance and enumeration
We introduce a new boundedness condition for affine permutations, motivated by the fruitful concept of periodic boundary conditions in statistical physics. We study pattern avoidance in bounded affine permutations. In particular, we show that if $\tau$ is one of the finite increasing oscillations, then every $\tau$-avoiding affine permutation satisfies the boundedness condition. We also explore the enumeration of pattern-avoiding affine permutations that can be decomposed into blocks, using analytic methods to relate their exact and asymptotic enumeration to that of the underlying ordinary permutations. Finally, we perform exact and asymptotic enumeration of the set of all bounded affine permutations of size $n$. A companion paper will focus on avoidance of monotone decreasing patterns in bounded affine permutations.
2. Enumeration of Permutation Classes and Weighted Labelled Independent Sets
In this paper, we study the staircase encoding of permutations, which maps a permutation to a staircase grid with cells filled with permutations. We consider many cases, where restricted to a permutation class, the staircase encoding becomes a bijection to its image. We describe the image of those restrictions using independent sets of graphs weighted with permutations. We derive the generating function for the independent sets and then for their weighted counterparts. The bijections we establish provide the enumeration of permutation classes. We use our results to uncover some unbalanced Wilf-equivalences of permutation classes and outline how to do random sampling in the permutation classes. In particular, we cover the classes $\mathrm{Av}(2314,3124)$, $\mathrm{Av}(2413,3142)$, $\mathrm{Av}(2413,3124)$, $\mathrm{Av}(2413,2134)$ and $\mathrm{Av}(2314,2143)$, as well as many subclasses.
3. Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
We give three applications of a recently-proven "Decomposition Lemma," which allows one to count preimages of certain sets of permutations under West's stack-sorting map $s$. We first enumerate the permutation class $s^{-1}(\text{Av}(231,321))=\text{Av}(2341,3241,45231)$, finding a new example of an unbalanced Wilf equivalence. This result is equivalent to the enumeration of permutations sortable by ${\bf B}\circ s$, where ${\bf B}$ is the bubble sort map. We then prove that the sets $s^{-1}(\text{Av}(231,312))$, $s^{-1}(\text{Av}(132,231))=\text{Av}(2341,1342,\underline{32}41,\underline{31}42)$, and $s^{-1}(\text{Av}(132,312))=\text{Av}(1342,3142,3412,34\underline{21})$ are counted by the so-called "Boolean-Catalan numbers," settling a conjecture of the current author and another conjecture of Hossain. This completes the enumerations of all sets of the form $s^{-1}(\text{Av}(\tau^{(1)},\ldots,\tau^{(r)}))$ for $\{\tau^{(1)},\ldots,\tau^{(r)}\}\subseteq S_3$ with the exception of the set $\{321\}$. We also find an explicit formula for $|s^{-1}(\text{Av}_{n,k}(231,312,321))|$, where $\text{Av}_{n,k}(231,312,321)$ is the set of permutations in $\text{Av}_n(231,312,321)$ with $k$ descents. This allows us to prove a conjectured identity involving Catalan numbers and order ideals in Young's lattice.
4. Flip-sort and combinatorial aspects of pop-stack sorting
Flip-sort is a natural sorting procedure which raises fascinating combinatorial questions. It finds its roots in the seminal work of Knuth on stack-based sorting algorithms and leads to many links with permutation patterns. We present several structural, enumerative, and algorithmic results on permutations that need few (resp. many) iterations of this procedure to be sorted. In particular, we give the shape of the permutations after one iteration, and characterize several families of permutations related to the best and worst cases of flip-sort. En passant, we also give some links between pop-stack sorting, automata, and lattice paths, and introduce several tactics of bijective proofs which have their own interest.
5. Catalan words avoiding pairs of length three patterns
Catalan words are particular growth-restricted words counted by the eponymous integer sequence. In this article we consider Catalan words avoiding a pair of patterns of length 3, pursuing the recent initiating work of the first and last authors and of S. Kirgizov where (among other things) the enumeration of Catalan words avoiding a patterns of length 3 is completed. More precisely, we explore systematically the structural properties of the sets of words under consideration and give enumerating results by means of recursive decomposition, constructive bijections or bivariate generating functions with respect to the length and descent number. Some of the obtained enumerating sequences are known, and thus the corresponding results establish new combinatorial interpretations for them.
6. Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations
Defant, Engen, and Miller defined a permutation to be uniquely sorted if it has exactly one preimage under West's stack-sorting map. We enumerate classes of uniquely sorted permutations that avoid a pattern of length three and a pattern of length four by establishing bijections between these classes and various lattice paths. This allows us to prove nine conjectures of Defant.
7. Enumeration of Dumont permutations avoiding certain four-letter patterns
In this paper, we enumerate Dumont permutations of the fourth kind avoiding or containing certain permutations of length 4. We also conjecture a Wilf-equivalence of two 4-letter patterns on Dumont permutations of the first kind.
8. Fillings of skew shapes avoiding diagonal patterns
A skew shape is the difference of two top-left justified Ferrers shapes sharing the same top-left corner. We study integer fillings of skew shapes. As our first main result, we show that for a specific hereditary class of skew shapes, which we call D-free shapes, the fillings that avoid a north-east chain of size $k$ are in bijection with fillings that avoid a south-east chain of the same size. Since Ferrers shapes are a subclass of D-free shapes, this result can be seen as a generalization of previous analogous results for Ferrers shapes. As our second main result, we construct a bijection between 01-fillings of an arbitrary skew shape that avoid a south-east chain of size 2, and the 01-fillings of the same shape that simultaneously avoid a north-east chain of size 2 and a particular non-square subfilling. This generalizes a previous result for transversal fillings.
9. Two examples of Wilf-collapse
Two permutation classes, the X-class and subpermutations of the increasing oscillation are shown to exhibit an exponential Wilf-collapse. This means that the number of distinct enumerations of principal subclasses of each of these classes grows much more slowly than the class itself whereas a priori, based only on symmetries of the class, there is no reason to expect this. The underlying cause of the collapse in both cases is the ability to apply some form of local symmetry which, combined with a greedy algorithm for detecting patterns in these classes, yields a Wilf-collapse.
10. The undecidability of joint embedding for 3-dimensional permutation classes
As a step towards resolving a question of Ruškuc on the decidability of joint embedding for hereditary classes of permutations, which may be viewed as structures in a language of 2 linear orders, we show the corresponding problem is undecidable for hereditary classes of structures in a language of 3 linear orders.
11. Enumerating two permutation classes by the number of cycles
We enumerate permutations in the two permutation classes $\text{Av}_n(312, 4321)$ and $\text{Av}_n(321, 4123)$ by the number of cycles each permutation admits. We also refine this enumeration with respect to several statistics.
12. Permutations avoiding 4321 and 3241 have an algebraic generating function
We show that permutations avoiding both of the (classical) patterns 4321 and 3241 have the algebraic generating function conjectured by Vladimir Kruchinin.
13. The number of {1243, 2134}-avoiding permutations
We show that the counting sequence for permutations avoiding both of the (classical) patterns 1243 and 2134 has the algebraic generating function supplied by Vaclav Kotesovec for sequence A164651 in The On-Line Encyclopedia of Integer Sequences.