Permutation Patterns

This section handles the special issue of DMTCS for 13th International Permutation Patterns conference that has been held in London, UK, 15-19 June.

https://sites.google.com/site/pp2015london/

Special guest editors are 

Jonathan Bloom

Mathilde Bouvel

Robert Brignall

 

 


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 […]

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 […]

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 […]

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 this […]

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$ […]

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 […]

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 […]

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 […]

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 […]

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 […]

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 […]

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 […]

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$.

$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 […]