Vol. 18 no. 2, Permutation Patterns 2015


1. $2\times 2$ monotone grid classes are finitely based

Albert, Michael ; Brignall, Robert.
In this note, we prove that all $2 \times 2$ monotone grid classes are finitely based, i.e., defined by a finite collection of minimal forbidden permutations. This follows from a slightly more general result about certain $2 \times 2$ (generalized) grid classes having two monotone cells in the same […]
Section: Permutation Patterns

2. Patterns in Inversion Sequences I

Corteel, Sylvie ; Martinez, Megan A. ; Savage, Carla D. ; Weselcouch, Michael.
Permutations that avoid given patterns have been studied in great depth for their connections to other fields of mathematics, computer science, and biology. From a combinatorial perspective, permutation patterns have served as a unifying interpretation that relates a vast array of […]
Section: Permutation Patterns

3. Pattern Avoidance in Task-Precedence Posets

Paukner, Mitchell ; Pepin, Lucy ; Riehl, Manda ; Wieser, Jarred.
We have extended classical pattern avoidance to a new structure: multiple task-precedence posets whose Hasse diagrams have three levels, which we will call diamonds. The vertices of each diamond are assigned labels which are compatible with the poset. A corresponding permutation is formed by […]
Section: Permutation Patterns

4. An Erdős--Hajnal analogue for permutation classes

Vatter, Vincent.
Let $\mathcal{C}$ be a permutation class that does not contain all layered permutations or all colayered permutations. We prove that there is a constant $c$ such that every permutation in $\mathcal{C}$ of length $n$ contains a monotone subsequence of length $cn$.
Section: Permutation Patterns

5. Snow Leopard Permutations and Their Even and Odd Threads

Egge, Eric S. ; Rubin, Kailee.
Caffrey, Egge, Michel, Rubin and Ver Steegh recently introduced snow leopard permutations, which are the anti-Baxter permutations that are compatible with the doubly alternating Baxter permutations. Among other things, they showed that these permutations preserve parity, and that the number of snow […]
Section: Permutation Patterns

6. Asymptotics for minimal overlapping patterns for generalized Euler permutations, standard tableaux of rectangular shape, and column strict arrays

Pan, Ran ; Remmel, Jeffrey B..
A permutation $\tau$ in the symmetric group $S_j$ is minimally overlapping if any two consecutive occurrences of $\tau$ in a permutation $\sigma$ can share at most one element. B\'ona \cite{B} showed that the proportion of minimal overlapping patterns in $S_j$ is at least $3 -e$. Given a permutation […]
Section: Permutation Patterns

7. Packing densities of layered permutations and the minimum number of monotone sequences in layered permutations

Bastos, Josefran de Oliveira ; Coregliano, Leonardo Nagami.
In this paper, we present two new results of layered permutation densities. The first one generalizes theorems from H\"{a}stö (2003) and Warren (2004) to compute the permutation packing of permutations whose layer sequence is~$(1^a,\ell_1,\ell_2,\ldots,\ell_k)$ with~$2^a-a-1\geq k$ (and […]
Section: Permutation Patterns

8. Pattern avoidance in forests of binary shrubs

Bevan, David ; Levin, Derek ; Nugent, Peter ; Pantone, Jay ; Pudwell, Lara ; Riehl, Manda ; Tlachac, ML.
We investigate pattern avoidance in permutations satisfying some additional restrictions. These are naturally considered in terms of avoiding patterns in linear extensions of certain forest-like partially ordered sets, which we call binary shrub forests. In this context, we enumerate forests […]
Section: Permutation Patterns

9. Pattern avoidance for set partitions à la Klazar

Bloom, Jonathan ; Saracino, Dan.
In 2000 Klazar introduced a new notion of pattern avoidance in the context of set partitions of $[n]=\{1,\ldots, n\}$. The purpose of the present paper is to undertake a study of the concept of Wilf-equivalence based on Klazar's notion. We determine all Wilf-equivalences for partitions with exactly […]
Section: Permutation Patterns

10. The permutation class Av(4213,2143)

Bevan, David.
We determine the structure of permutations avoiding the patterns 4213 and 2143. Each such permutation consists of the skew sum of a sequence of plane trees, together with an increasing sequence of points above and an increasing sequence of points to its left. We use this characterisation to […]
Section: Permutation Patterns

11. The Complexity of Pattern Matching for $321$-Avoiding and Skew-Merged Permutations

Albert, Michael H. ; Lackner, Marie-Louise ; Lackner, Martin ; Vatter, Vincent.
The Permutation Pattern Matching problem, asking whether a pattern permutation $\pi$ is contained in a permutation $\tau$, is known to be NP-complete. In this paper we present two polynomial time algorithms for special cases. The first algorithm is applicable if both $\pi$ and $\tau$ […]
Section: Permutation Patterns

12. Right-jumps and pattern avoiding permutations

Banderier, Cyril ; Baril, Jean-Luc ; Santos, Céline Moreira Dos.
We study the iteration of the process "a particle jumps to the right" in permutations. We prove that the set of permutations obtained in this model after a given number of iterations from the identity is a class of pattern avoiding permutations. We characterize the elements of the basis of […]
Section: Permutation Patterns

13. Descent c-Wilf Equivalence

Bach, Quang T. ; Remmel, Jeffrey B..
Let $S_n$ denote the symmetric group. For any $\sigma \in S_n$, we let $\mathrm{des}(\sigma)$ denote the number of descents of $\sigma$, $\mathrm{inv}(\sigma)$ denote the number of inversions of $\sigma$, and $\mathrm{LRmin}(\sigma)$ denote the number of left-to-right minima of $\sigma$. For any […]
Section: Permutation Patterns

14. Permutation Pattern matching in (213, 231)-avoiding permutations

Neou, Both,  ; Rizzi, Romeo ; Vialette, Stéphane.
Given permutations σ of size k and π of size n with k < n, the permutation pattern matching problem is to decide whether σ occurs in π as an order-isomorphic subsequence. We give a linear-time algorithm in case both π and σ avoid the two size-3 permutations 213 and 231. For the special case where […]
Section: Permutation Patterns

15. A Bijection on Classes Enumerated by the Schr\"oder Numbers

Schroeder, Michael W. ; Smith, Rebecca.
We consider a sorting machine consisting of two stacks in series where the first stack has the added restriction that entries in the stack must be in decreasing order from top to bottom. The class of permutations sortable by this machine are known to be enumerated by the Schr\"oder numbers. In […]
Section: Permutation Patterns