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

 

 


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