vol. 27:1, Permutation Patterns 2024

---

1. Sorting inversion sequences

Toufik Mansour ; Howard Skogman ; Rebecca Smith.

We consider the avoidance of patterns in inversion sequences that relate sorting via sorting machines including data structures such as pop stacks and stacks. Such machines have been studied under a variety of additional constraints and generalizations, some of which we apply here. We give the classification of several classes of sortable inversion sequences in terms of pattern avoidance. We are able to provide an exact enumeration of some of the sortable classes in question using both classical approaches and a more recent strategy utilizing generating trees.

---

2. On the asymptotic enumeration and limit shapes of monotone grid classes of permutations

Noura Alshammari ; David Bevan.

We exhibit a procedure to asymptotically enumerate monotone grid classes of permutations. This is then applied to compute the asymptotic number of permutations in any connected one-corner class. Our strategy consists of enumerating the gridded permutations, finding the asymptotic distribution of points between the cells in a typical large gridded permutation, and analysing in detail the ways in which a typical permutation can be gridded. We also determine the limit shape of any connected monotone grid class.

---

3. Key-avoidance for alternating sign matrices

Mathilde Bouvel ; Rebecca Smith ; Jessica Striker.

We initiate a systematic study of key-avoidance on alternating sign matrices (ASMs) defined via pattern-avoidance on an associated permutation called the \emph{key} of an ASM. We enumerate alternating sign matrices whose key avoids a given set of permutation patterns in several instances. We show that ASMs whose key avoids $231$ are permutations, thus any known enumeration for a set of permutation patterns including $231$ extends to ASMs. We furthermore enumerate by the Catalan numbers ASMs whose key avoids both $312$ and $321$. We also show ASMs whose key avoids $312$ are in bijection with the gapless monotone triangles of [Ayyer, Cori, Gouyou-Beauchamps 2011]. Thus key-avoidance generalizes the notion of $312$-avoidance studied there. Finally, we enumerate ASMs with a given key avoiding $312$ and $321$ using a connection to Schubert polynomials, thereby deriving an interesting Catalan identity.

---

4. Desarrangements revisited: statistics and pattern avoidance

Chadi Bsila ; Caroline E. Cox ; Anna S. Hugo ; Lindsey A. Styron ; Yan Zhuang.

A desarrangement is a permutation whose first ascent is even. Desarrangements were introduced in the 1980s by Jacques Désarménien, who proved that they are in bijection with derangements. We revisit the study of desarrangements, focusing on two themes: the refined enumeration of desarrangements with respect to permutation statistics, and pattern avoidance in desarrangements. Our main results include generating function formulas for counting desarrangements by the number of descents, peaks, valleys, double ascents, and double descents, as well as a complete enumeration of desarrangements avoiding a prescribed set of length 3 patterns. We find new interpretations of the Catalan, Fine, Jacobsthal, and Fibonacci numbers in terms of pattern-avoiding desarrangements.

---

5. Pattern Avoiding Permutations Enumerated by Inversions

Atli Fannar Franklín.

Permutations are usually enumerated by size, but new results can be found by enumerating them by inversions instead, in which case one must restrict one's attention to indecomposable permutations. In the style of the seminal paper by Simion and Schmidt, we investigate all combinations of permutation patterns of length at most 3.

---

6. The complexity of recognizing $ABAB$-free hypergraphs

Gábor Damásdi ; Balázs Keszegh ; Dömötör Pálvölgyi ; Karamjeet Singh.

The study of geometric hypergraphs gave rise to the notion of $ABAB$-free hypergraphs. A hypergraph $\mathcal{H}$ is called $ABAB$-free if there is an ordering of its vertices such that there are no hyperedges $A,B$ and vertices $v_1,v_2,v_3,v_4$ in this order satisfying $v_1,v_3\in A\setminus B$ and $v_2,v_4\in B\setminus A$. In this paper, we prove that it is NP-complete to decide if a hypergraph is $ABAB$-free. We show a number of analogous results for hypergraphs with similar forbidden patterns, such as $ABABA$-free hypergraphs. As an application, we show that deciding whether a hypergraph is realizable as the incidence hypergraph of points and pseudodisks is also NP-complete.

---

7. Fixed Point Homing Shuffles

Jonathan Parlett.

We study a family of maps from $S_n \to S_n$ we call fixed point homing shuffles. These maps generalize a few known problems such as Conway's Topswops, and a card shuffling process studied by Gweneth McKinley. We show that the iterates of these homing shuffles always converge, and characterize the set $U_n$ of permutations that no homing shuffle sorts. We also study a homing shuffle that sorts anything not in $U_n$, and find how many iterations it takes to converge in the worst case.

---

8. Generating trees growing on the left for pattern-avoiding inversion sequences

Benjamin Testart.

This work concerns a construction of pattern-avoiding inversion sequences from right to left we call the generating tree growing on the left. We first apply this construction to inversion sequences avoiding 201 and 210, resulting in a new way of computing their generating function. We then use a slightly modified construction to compute the generating function of inversion sequences avoiding 010 and 102, which was only conjectured before. These generating functions are algebraic in both instances. We end by discussing how the generating tree growing on the left can be applied in a more general setting.

---

9. Pattern avoidance in nonnesting permutations

Sergi Elizalde ; Amya Luo.

Nonnesting permutations are permutations of the multiset $\{1,1,2,2,\dots,n,n\}$ that avoid subsequences of the form $abba$ for any $a\neq b$. These permutations have recently been studied in connection to noncrossing (also called quasi-Stirling) permutations, which are those that avoid subsequences of the form $abab$, and in turn generalize the well-known Stirling permutations. Inspired by the work by Archer et al. on pattern avoidance in noncrossing permutations, we consider the analogous problem in the nonnesting case. We enumerate nonnesting permutations that avoid each set of two or more patterns of length 3, as well as those that avoid some sets of patterns of length 4. We obtain closed formulas and generating functions, some of which involve unexpected appearances of the Catalan and Fibonacci numbers. Our proofs rely on decompositions, recurrences, and bijections.

---

10. Hertzsprung patterns on involutions

Marilena Barnabei ; Niccolò Castronuovo ; Matteo Silimbani.

Hertzsprung patterns, recently introduced by Anders Claesson, are subsequences of a permutation contiguous in both positions and values, and can be seen as a subclass of bivincular patterns. This paper investigates Hertzsprung patterns within involutions, where additional structural constraints introduce new challenges. We present a general formula for enumerating occurrences of these patterns in involutions. We also analyze specific cases to derive the distribution of all Hertzsprung patterns of lengths two and three.

---

11. Patterns in rectangulations. Part I: $\top$-like patterns, inversion sequence classes $I(010, 101, 120, 201)$ and $I(011, 201)$, and rushed Dyck paths

Andrei Asinowski ; Michaela A. Polley.

We initiate a systematic study of pattern avoidance in rectangulations. We give a formal definition of such patterns and investigate rectangulations that avoid $\top$-like patterns - the pattern $\top$ and its rotations. For every $L \subseteq \{\top, \, \vdash, \, \bot, \, \dashv \}$ we enumerate $L$-avoiding rectangulations, both weak and strong. In particular, we show $\top$-avoiding weak rectangulations are enumerated by Catalan numbers and construct bijections to several Catalan structures. Then, we prove that $\top$-avoiding strong rectangulations are in bijection with several classes of inversion sequences, among them $I(010,101,120,201)$ and $I(011,201)$ - which leads to a solution of the conjecture that these classes are Wilf-equivalent. Finally, we show that $\{\top, \bot\}$-avoiding strong rectangulations are in bijection with recently introduced rushed Dyck paths.

---