Megan A. Martinez ; Manda Riehl.
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.
Section:
Permutation Patterns
Christopher Coscia ; Jonathan DeWitt ; Fan Yang ; Yiguang Zhang.
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.
Section:
Permutation Patterns
Jakub Sliacan ; Walter Stromquist.
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.
Section:
Permutation Patterns
Vít Jelínek ; Michal Opler.
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.
Section:
Permutation Patterns
Samuel Miner ; Douglas Rizzolo ; Erik Slivken.
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.
Section:
Permutation Patterns
Murray Tannock ; Henning Ulfarsson.
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.
Section:
Permutation Patterns
Ryan Alweiss.
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.
Section:
Permutation Patterns
Nicholas R Beaton ; Andrew R Conway ; Anthony J Guttmann.
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) calculate the asymptotics for all classes of
length 4 and length 5 to significantly greater precision than previously, and
(b) use these extended series to search, unsuccessfully, for D-finite solutions
for the unsolved classes, leading us to conjecture that the solutions are not
D-finite. We have also searched, unsuccessfully, for differentially algebraic
solutions.
Section:
Permutation Patterns
Lisa Hofer.
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.
Section:
Permutation Patterns
Yonah Biers-Ariel ; Anant Godbole ; Elizabeth Kelley.
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.
Section:
Permutation Patterns
Sergi Elizalde.
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.
Section:
Permutation Patterns
Dun Qiu ; Jeffrey B. Remmel.
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 distribution of the number of matches of
$\mathrm{MMP}(a,b,c,d)$ in 123-avoiding permutations. We provide explicit
recurrence relations to enumerate our objects which can be used to give closed
forms for the generating functions associated with such distributions. In many
cases, we provide combinatorial explanations of the coefficients that appear in
our generating functions.
Section:
Permutation Patterns
Harry Crane ; Stephen DeSalvo.
Using techniques from Poisson approximation, we prove explicit error bounds
on the number of permutations that avoid any pattern. Most generally, we bound
the total variation distance between the joint distribution of pattern
occurrences and a corresponding joint distribution of independent Bernoulli
random variables, which as a corollary yields a Poisson approximation for the
distribution of the number of occurrences of any pattern. We also investigate
occurrences of consecutive patterns in random Mallows permutations, of which
uniform random permutations are a special case. These bounds allow us to
estimate the probability that a pattern occurs any number of times and, in
particular, the probability that a random permutation avoids a given pattern.
Section:
Permutation Patterns
Monica Anderson ; Marika Diepenbroek ; Lara Pudwell ; Alex Stoll.
In this paper, we consider pattern avoidance in a subset of words on
$\{1,1,2,2,\dots,n,n\}$ called reverse double lists. In particular a reverse
double list is a word formed by concatenating a permutation with its reversal.
We enumerate reverse double lists avoiding any permutation pattern of length at
most 4 and completely determine the corresponding Wilf classes. For permutation
patterns $\rho$ of length 5 or more, we characterize when the number of
$\rho$-avoiding reverse double lists on $n$ letters has polynomial growth. We
also determine the number of $1\cdots k$-avoiders of maximum length for any
positive integer $k$.
Section:
Permutation Patterns