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

 

 


Quadrant marked mesh patterns in 123-avoiding permutations

Qiu, Dun ; Remmel, Jeffrey B..
Given a permutation $\sigma = \sigma_1 \ldots \sigma_n$ in the symmetric group $\mathcal{S}_{n}$, we say that $\sigma_i$ matches the quadrant marked mesh pattern $\mathrm{MMP}(a,b,c,d)$ in $\sigma$ if there are at least $a$ points to the right of $\sigma_i$ in $\sigma$ which are greater than $\sigma_i$, at least $b$ points to the left of $\sigma_i$ in $\sigma$ which are greater than $\sigma_i$, at least $c$ points to the left of $\sigma_i$ in $\sigma$ which are smaller than $\sigma_i$, and at least $d$ points to the right of $\sigma_i$ in $\sigma$ which are smaller than $\sigma_i$. Kitaev, Remmel, and Tiefenbruck systematically studied the distribution of the number of matches of $\mathrm{MMP}(a,b,c,d)$ in 132-avoiding permutations. The operation of reverse and complement on permutations allow one to translate their results to find the distribution of the number of $\mathrm{MMP}(a,b,c,d)$ matches in 231-avoiding, 213-avoiding, and 312-avoiding permutations. In this paper, we study the […]

Expected Number of Distinct Subsequences in Randomly Generated Binary Strings

Biers-Ariel, Yonah ; Godbole, Anant ; Kelley, Elizabeth.
When considering binary strings, it's natural to wonder how many distinct subsequences might exist in a given string. Given that there is an existing algorithm which provides a straightforward way to compute the number of distinct subsequences in a fixed string, we might next be interested in the expected number of distinct subsequences in random strings. This expected value is already known for random binary strings where each letter in the string is, independently, equally likely to be a 1 or a 0. We generalize this result to random strings where the letter 1 appears independently with probability $\alpha \in [0,1]$. Also, we make some progress in the case of random strings from an arbitrary alphabet as well as when the string is generated by a two-state Markov chain.

Continued fractions for permutation statistics

Elizalde, Sergi.
We explore a bijection between permutations and colored Motzkin paths that has been used in different forms by Foata and Zeilberger, Biane, and Corteel. By giving a visual representation of this bijection in terms of so-called cycle diagrams, we find simple translations of some statistics on permutations (and subsets of permutations) into statistics on colored Motzkin paths, which are amenable to the use of continued fractions. We obtain new enumeration formulas for subsets of permutations with respect to fixed points, excedances, double excedances, cycles, and inversions. In particular, we prove that cyclic permutations whose excedances are increasing are counted by the Bell numbers.

A Central Limit Theorem for Vincular Permutation Patterns

Hofer, Lisa.
We study the number of occurrences of any fixed vincular permutation pattern. We show that this statistics on uniform random permutations is asymptotically normal and describe the speed of convergence. To prove this central limit theorem, we use the method of dependency graphs. The main difficulty is then to estimate the variance of our statistics. We need a lower bound on the variance, for which we introduce a recursive technique based on the law of total variance.

Asymptotic results on Klazar set partition avoidance

Alweiss, Ryan.
We establish asymptotic bounds for the number of partitions of $[n]$ avoiding a given partition in Klazar's sense, obtaining the correct answer to within an exponential for the block case. This technique also enables us to establish a general lower bound. Additionally, we consider a graph theoretic restatement of partition avoidance problems, and propose several conjectures.

On consecutive pattern-avoiding permutations of length 4, 5 and beyond

Beaton, Nicholas R ; Conway, Andrew R ; Guttmann, Anthony J.
We review and extend what is known about the generating functions for consecutive pattern-avoiding permutations of length 4, 5 and beyond, and their asymptotic behaviour. There are respectively, seven length-4 and twenty-five length-5 consecutive-Wilf classes. D-finite differential equations are known for the reciprocal of the exponential generating functions for four of the length-4 and eight of the length-5 classes. We give the solutions of some of these ODEs. An unsolved functional equation is known for one more class of length-4, length-5 and beyond. We give the solution of this functional equation, and use it to show that the solution is not D-finite. For three further length-5 c-Wilf classes we give recurrences for two and a differential-functional equation for a third. For a fourth class we find a new algebraic solution. We give a polynomial-time algorithm to generate the coefficients of the generating functions which is faster than existing algorithms, and use this to (a) […]

Equivalence classes of mesh patterns with a dominating pattern

Tannock, Murray ; Ulfarsson, Henning.
Two mesh patterns are coincident if they are avoided by the same set of permutations, and are Wilf-equivalent if they have the same number of avoiders of each length. We provide sufficient conditions for coincidence of mesh patterns, when only permutations also avoiding a longer classical pattern are considered. Using these conditions we completely classify coincidences between families containing a mesh pattern of length 2 and a classical pattern of length 3. Furthermore, we completely Wilf-classify mesh patterns of length 2 inside the class of 231-avoiding permutations.

Improving bounds on packing densities of 4-point permutations

Sliacan, Jakub ; Stromquist, Walter.
We consolidate what is currently known about packing densities of 4-point permutations and in the process improve the lower bounds for the packing densities of 1324 and 1342. We also provide rigorous upper bounds for the packing densities of 1324, 1342, and 2413. All our bounds are within $10^{-4}$ of the true packing densities. Together with the known bounds, this gives us a fairly complete picture of all 4-point packing densities. We also provide new upper bounds for several small permutations of length at least five. Our main tool for the upper bounds is the framework of flag algebras introduced by Razborov in 2007.

A bijection between the set of nesting-similarity classes and L & P matchings

Martinez, Megan A. ; Riehl, Manda.
Matchings are frequently used to model RNA secondary structures; however, not all matchings can be realized as RNA motifs. One class of matchings, called the L $\&$ P matchings, is the most restrictive model for RNA secondary structures in the Largest Hairpin Family (LHF). The L $\&$ P matchings were enumerated in $2015$ by Jefferson, and they are equinumerous with the set of nesting-similarity classes of matchings, enumerated by Klazar. We provide a bijection between these two sets. This bijection preserves noncrossing matchings, and preserves the sequence obtained reading left to right of whether an edge begins or ends at that vertex.

Best and worst case permutations for random online domination of the path

Coscia, Christopher ; DeWitt, Jonathan ; Yang, Fan ; Zhang, Yiguang.
We study a randomized algorithm for graph domination, by which, according to a uniformly chosen permutation, vertices are revealed and added to the dominating set if not already dominated. We determine the expected size of the dominating set produced by the algorithm for the path graph $P_n$ and use this to derive the expected size for some related families of graphs. We then provide a much-refined analysis of the worst and best cases of this algorithm on $P_n$ and enumerate the permutations for which the algorithm has the worst-possible performance and best-possible performance. The case of dominating the path graph has connections to previous work of Bouwer and Star, and of Gessel on greedily coloring the path.

Asymptotic distribution of fixed points of pattern-avoiding involutions

Miner, Samuel ; Rizzolo, Douglas ; Slivken, Erik.
For a variety of pattern-avoiding classes, we describe the limiting distribution for the number of fixed points for involutions chosen uniformly at random from that class. In particular we consider monotone patterns of arbitrary length as well as all patterns of length 3. For monotone patterns we utilize the connection with standard Young tableaux with at most $k$ rows and involutions avoiding a monotone pattern of length $k$. For every pattern of length 3 we give the bivariate generating function with respect to fixed points for the involutions that avoid that pattern, and where applicable apply tools from analytic combinatorics to extract information about the limiting distribution from the generating function. Many well-known distributions appear.

Splittability and 1-amalgamability of permutation classes

Jelínek, Vít ; Opler, Michal.
A permutation class $C$ is splittable if it is contained in a merge of two of its proper subclasses, and it is 1-amalgamable if given two permutations $\sigma$ and $\tau$ in $C$, each with a marked element, we can find a permutation $\pi$ in $C$ containing both $\sigma$ and $\tau$ such that the two marked elements coincide. It was previously shown that unsplittability implies 1-amalgamability. We prove that unsplittability and 1-amalgamability are not equivalent properties of permutation classes by showing that the class $Av(1423, 1342)$ is both splittable and 1-amalgamable. Our construction is based on the concept of LR-inflations, which we introduce here and which may be of independent interest.

A Bijection on Classes Enumerated by the Schröder 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öder numbers. In this paper, we give a bijection between these sortable permutations of length $n$ and Schröder paths -- the lattice paths from $(0,0)$ to $(n-1,n-1)$ composed of East steps $(1,0)$, North steps $(0,1)$, and Diagonal steps $(1,1)$ that travel weakly below the line $y=x$.

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 establish the generating function enumerating these permutations. We also investigate the properties of a typical large permutation in the class and prove that if a large permutation that avoids 4213 and 2143 is chosen uniformly at random, then it is more likely than not to avoid 2413 as well.

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 only σ avoids 213 and 231, we present a O(max(kn 2 , n 2 log log n)-time algorithm. We extend our research to bivincular patterns that avoid 213 and 231 and present a O(kn 4)-time algorithm. Finally we look at the related problem of the longest subsequence which avoids 213 and 231.

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 sequence of statistics $\mathrm{stat}_1, \ldots \mathrm{stat}_k$ on permutations, we say two permutations $\alpha$ and $\beta$ in $S_j$ are $(\mathrm{stat}_1, \ldots \mathrm{stat}_k)$-c-Wilf equivalent if the generating function of $\prod_{i=1}^k x_i^{\mathrm{stat}_i}$ over all permutations which have no consecutive occurrences of $\alpha$ equals the generating function of $\prod_{i=1}^k x_i^{\mathrm{stat}_i}$ over all permutations which have no consecutive occurrences of $\beta$. We give many examples of pairs of permutations $\alpha$ and $\beta$ in $S_j$ which are $\mathrm{des}$-c-Wilf equivalent, $(\mathrm{des},\mathrm{inv})$-c-Wilf equivalent, […]

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 class and we enumerate these "forbidden minimal patterns" by giving their bivariate exponential generating function: we achieve this via a catalytic variable, the number of left-to-right maxima. We show that this generating function is a D-finite function satisfying a nice differential equation of order~2. We give some congruence properties for the coefficients of this generating function, and we show that their asymptotics involves a rather unusual algebraic exponent (the golden ratio $(1+\sqrt 5)/2$) and some unusual closed-form constants. We end by proving a limit law: a forbidden pattern of length $n$ has typically $(\ln n) /\sqrt{5}$ left-to-right maxima, with Gaussian fluctuations.

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$ are $321$-avoiding; the second is applicable if $\pi$ and $\tau$ are skew-merged. Both algorithms have a runtime of $O(kn)$, where $k$ is the length of $\pi$ and $n$ the length of $\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 two blocks, one of which is a singleton block, and we conjecture that, for $n\geq 4$, these are all the Wilf-equivalences except for those arising from complementation. If $\tau$ is a partition of $[k]$ and $\Pi_n(\tau)$ denotes the set of all partitions of $[n]$ that avoid $\tau$, we establish inequalities between $|\Pi_n(\tau_1)|$ and $|\Pi_n(\tau_2)|$ for several choices of $\tau_1$ and $\tau_2$, and we prove that if $\tau_2$ is the partition of $[k]$ with only one block, then $|\Pi_n(\tau_1)| <|\Pi_n(\tau_2)|$ for all $n>k$ and all partitions $\tau_1$ of $[k]$ with exactly two blocks. We conjecture that this result holds for all partitions $\tau_1$ of $[k]$. Finally, we enumerate […]

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 avoiding patterns of length three. In four of the five non-equivalent cases, we present explicit enumerations by exhibiting bijections with certain lattice paths bounded above by the line $y=\ell x$, for some $\ell\in\mathbb{Q}^+$, one of these being the celebrated Duchon's club paths with $\ell=2/3$. In the remaining case, we use the machinery of analytic combinatorics to determine the minimal polynomial of its generating function, and deduce its growth rate.

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 reading these labels by increasing levels, and then from left to right. We used Sage to form enumerative conjectures for the associated permutations avoiding collections of patterns of length three, which we then proved. We have discovered a bijection between diamonds avoiding 132 and certain generalized Dyck paths. We have also found the generating function for descents, and therefore the number of avoiders, in these permutations for the majority of collections of patterns of length three. An interesting application of this work (and the motivating example) can be found when task-precedence posets represent warehouse package fulfillment by robots, in which case avoidance of both 231 and 321 […]

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 similar permutations). As a second result, we prove that the minimum density of monotone sequences of length~$k+1$ in an arbitrarily large layered permutation is asymptotically~$1/k^k$. This value is compatible with a conjecture from Myers (2003) for the problem without the layered restriction (the same problem where the monotone sequences have different lengths is also studied).

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 leopard permutations of length $2n-1$ is the Catalan number $C_n$. In this paper we investigate the permutations that the snow leopard permutations induce on their even and odd entries; we call these the even threads and the odd threads, respectively. We give recursive bijections between these permutations and certain families of Catalan paths. We characterize the odd (resp. even) threads which form the other half of a snow leopard permutation whose even (resp. odd) thread is layered in terms of pattern avoidance, and we give a constructive bijection between the set of permutations of length $n$ which are both even threads and odd threads and the set of peakless Motzkin paths of length […]

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 $\sigma$, we let $\text{Des}(\sigma)$ denote the set of descents of $\sigma$. We study the class of permutations $\sigma \in S_{kn}$ whose descent set is contained in the set $\{k,2k, \ldots (n-1)k\}$. For example, up-down permutations in $S_{2n}$ are the set of permutations whose descent equal $\sigma$ such that $\text{Des}(\sigma) = \{2,4, \ldots, 2n-2\}$. There are natural analogues of the minimal overlapping permutations for such classes of permutations and we study the proportion of minimal overlapping patterns for each such class. We show that the proportion of minimal overlapping permutations in such classes approaches $1$ as $k$ goes to infinity. We also study the proportion of […]

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 combinatorial structures. In this paper, we introduce the notion of patterns in inversion sequences. A sequence $(e_1,e_2,\ldots,e_n)$ is an inversion sequence if $0 \leq e_i \pi_i \}|$. This correspondence makes it a natural extension to study patterns in inversion sequences much in the same way that patterns have been studied in permutations. This paper, the first of two on patterns in inversion sequences, focuses on the enumeration of inversion sequences […]

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