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

Neal Madras ; Justin M. Troyka.
We introduce a new boundedness condition for affine permutations, motivatedby the fruitful concept of periodic boundary conditions in statistical physics.We study pattern avoidance in bounded affine permutations. In particular, weshow that if $\tau$ is one of the finite increasing oscillations, then every$\tau$-avoiding affine permutation satisfies the boundedness condition. We alsoexplore the enumeration of pattern-avoiding affine permutations that can bedecomposed into blocks, using analytic methods to relate their exact andasymptotic enumeration to that of the underlying ordinary permutations.Finally, we perform exact and asymptotic enumeration of the set of all boundedaffine permutations of size $n$. A companion paper will focus on avoidance ofmonotone decreasing patterns in bounded affine permutations.

2. Enumeration of Permutation Classes and Weighted Labelled Independent Sets

Christian Bean ; Émile Nadeau ; Henning Ulfarsson.
In this paper, we study the staircase encoding of permutations, which maps apermutation to a staircase grid with cells filled with permutations. Weconsider many cases, where restricted to a permutation class, the staircaseencoding becomes a bijection to its image. We describe the image of thoserestrictions using independent sets of graphs weighted with permutations. Wederive the generating function for the independent sets and then for theirweighted counterparts. The bijections we establish provide the enumeration ofpermutation classes. We use our results to uncover some unbalancedWilf-equivalences of permutation classes and outline how to do random samplingin 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 manysubclasses.

3. Enumeration of Stack-Sorting Preimages via a Decomposition Lemma

Colin Defant.
We give three applications of a recently-proven "Decomposition Lemma," whichallows one to count preimages of certain sets of permutations under West'sstack-sorting map $s$. We first enumerate the permutation class$s^{-1}(\text{Av}(231,321))=\text{Av}(2341,3241,45231)$, finding a new exampleof an unbalanced Wilf equivalence. This result is equivalent to the enumerationof permutations sortable by ${\bf B}\circ s$, where ${\bf B}$ is the bubblesort 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})$ arecounted by the so-called "Boolean-Catalan numbers," settling a conjecture ofthe current author and another conjecture of Hossain. This completes theenumerations 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 andorder ideals in Young's lattice.

4. Flip-sort and combinatorial aspects of pop-stack sorting

Andrei Asinowski ; Cyril Banderier ; Benjamin Hackl.
Flip-sort is a natural sorting procedure which raises fascinatingcombinatorial questions. It finds its roots in the seminal work of Knuth onstack-based sorting algorithms and leads to many links with permutationpatterns. We present several structural, enumerative, and algorithmic resultson permutations that need few (resp. many) iterations of this procedure to besorted. In particular, we give the shape of the permutations after oneiteration, and characterize several families of permutations related to thebest and worst cases of flip-sort. En passant, we also give some links betweenpop-stack sorting, automata, and lattice paths, and introduce several tacticsof bijective proofs which have their own interest.

5. Catalan words avoiding pairs of length three patterns

Jean-Luc Baril ; Carine Khalil ; Vincent Vajnovszki.
Catalan words are particular growth-restricted words counted by the eponymousinteger sequence. In this article we consider Catalan words avoiding a pair ofpatterns of length 3, pursuing the recent initiating work of the first and lastauthors and of S. Kirgizov where (among other things) the enumeration ofCatalan words avoiding a patterns of length 3 is completed. More precisely, weexplore systematically the structural properties of the sets of words underconsideration and give enumerating results by means of recursive decomposition,constructive bijections or bivariate generating functions with respect to thelength and descent number. Some of the obtained enumerating sequences areknown, and thus the corresponding results establish new combinatorialinterpretations for them.

6. Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations

Hanna Mularczyk.
Defant, Engen, and Miller defined a permutation to be uniquely sorted if ithas exactly one preimage under West's stack-sorting map. We enumerate classesof uniquely sorted permutations that avoid a pattern of length three and apattern of length four by establishing bijections between these classes andvarious lattice paths. This allows us to prove nine conjectures of Defant.

7. Enumeration of Dumont permutations avoiding certain four-letter patterns

Alexander Burstein ; Opel Jones.
In this paper, we enumerate Dumont permutations of the fourth kind avoidingor containing certain permutations of length 4. We also conjecture aWilf-equivalence of two 4-letter patterns on Dumont permutations of the firstkind.

8. Fillings of skew shapes avoiding diagonal patterns

Vít Jelínek ; Mark Karpilovskij.
A skew shape is the difference of two top-left justified Ferrers shapessharing the same top-left corner. We study integer fillings of skew shapes. Asour first main result, we show that for a specific hereditary class of skewshapes, which we call D-free shapes, the fillings that avoid a north-east chainof size $k$ are in bijection with fillings that avoid a south-east chain of thesame size. Since Ferrers shapes are a subclass of D-free shapes, this resultcan be seen as a generalization of previous analogous results for Ferrersshapes. As our second main result, we construct a bijection between 01-fillings of anarbitrary skew shape that avoid a south-east chain of size 2, and the01-fillings of the same shape that simultaneously avoid a north-east chain ofsize 2 and a particular non-square subfilling. This generalizes a previousresult for transversal fillings.

9. Two examples of Wilf-collapse

Michael Albert ; Vít Jelínek ; Michal Opler.
Two permutation classes, the X-class and subpermutations of the increasingoscillation are shown to exhibit an exponential Wilf-collapse. This means thatthe number of distinct enumerations of principal subclasses of each of theseclasses grows much more slowly than the class itself whereas a priori, basedonly on symmetries of the class, there is no reason to expect this. Theunderlying cause of the collapse in both cases is the ability to apply someform of local symmetry which, combined with a greedy algorithm for detectingpatterns in these classes, yields a Wilf-collapse.

10. The undecidability of joint embedding for 3-dimensional permutation classes

Samuel Braunfeld.
As a step towards resolving a question of Ruškuc on the decidability ofjoint embedding for hereditary classes of permutations, which may be viewed asstructures in a language of 2 linear orders, we show the corresponding problemis undecidable for hereditary classes of structures in a language of 3 linearorders.

11. Enumerating two permutation classes by the number of cycles

Kassie Archer.
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 permutationadmits. We also refine this enumeration with respect to several statistics.

12. Permutations avoiding 4321 and 3241 have an algebraic generating function

David Callan.
We show that permutations avoiding both of the (classical) patterns 4321 and3241 have the algebraic generating function conjectured by Vladimir Kruchinin.

13. The number of {1243, 2134}-avoiding permutations

David Callan.
We show that the counting sequence for permutations avoiding both of the(classical) patterns 1243 and 2134 has the algebraic generating functionsupplied by Vaclav Kotesovec for sequence A164651 in The On-Line Encyclopediaof Integer Sequences.