. S
nt.
. S
P
ERMUTATION
C
LASSES OF
E
VERY
G
ROWTH
R
ATE
(
A
.
K
.
A
. S
TANLEY
-W
ILF
L
IMIT
) A
BOVE
2.48187 . . .
V
INCENT
V
ATTER
Department of Mathematics
Dartmouth College
Hanover, NH 03755
We prove that there are permutation classes (hereditary properties
of permutations) of every growth rate (Stanley-Wilf limit) at least
2.48187
, the unique real root of x
5
2x
4
2x
2
2x
1
, thereby
establishing a conjecture of Albert and Linton.
1.
I
NTRODUCTION
A permutation of length n contains the permutation of length k, written
, if
has a subsequence of length k in the same relative order as . For example,
391867452
(written in list, or one-line notation) contains
51342
, as can be seen by considering the
subsequence 91672 (
2
,
3
,
5
,
6
,
9
). We further say that properly contains
if
and
. A permutation class is a downset (or hereditary property) of
permutations under this order; thus if C is a permutation class,
C
, and
then
C
.
For any permutation class C there is a unique (but possibly innite) antichain (i.e., set of
pairwise incomparable permutations) B such that C
Av
B
:
for all
B
.
This antichain B is called the basis of C. (While specifying classes via their basis is the
traditional approach, herein we will instead describe classes by the permutations they do
contain, rather than those they do not.)
We denote by C
n
the set of permutations in C of length n. The Marcus-Tardos Theo-
rem [
11
] (formerly the Stanley-Wilf Conjecture) states that all permutation classes other
than the class of all permutations grow at at most exponential speed, i.e., that these classes
have nite upper growth rates,
gr
C
lim sup
n
n
C
n
.
Date: July 17, 2008
Key words and phrases. growth rate, permutation class, Stanley-Wilf limit
AMS 2000 Subject Classication. 05A05, 05A15, 06A06
1
P
ERMUTATION
C
LASSES OF
E
VERY
G
ROWTH
R
ATE
A
BOVE
2.48187 . . .
2
When lim
n
n
C
n
exists, as will always be the case for classes in this paper, we call it
the growth rate of C and denote it by gr
C
.
Although vast amounts of research had considered the growth rates of principally based
permutation classes, i.e., those of the form Av
, Kaiser and Klazar [
9
] were the rst to
conduct an extensive investigation of growth rates of permutation classes in full gener-
ality. They showed that permutation classes of growth rate less than 2 satisfy one of the
following:
C
n
is polynomial for large n, or
F
n,k
C
n
n
c
F
n,k
holds for integers c
0
and k
2
, where F
n,k
denotes the
k
-generalized Fibonacci numbers dened by F
n,k
F
n
1,k
F
n
2,k
F
n
k,k
.
It follows that all growth rates of permutation classes less than 2 are positive roots of x
k
1
x
k
x
2
1
for some k.
Vatter [
12
] then showed that there are only countably many permutation classes of
growth rate less than , the unique real root of x
3
2x
2
1
, approximately 2.20557, while
there are uncountably many permutation classes of growth rate . That work also charac-
terizes the possible growth rates between 2 and , which are roots of one of the following
four families of polynomials
x
3
2x
2
1
x
k
1
x
3
,
x
3
2x
2
1
x
k
2
x
2
2x
1
,
x
3
2x
2
1
x
k
x
1
, and
x
3
2x
2
1
x
k
1
,
for integers k,
0
. Note that the set of these growth rates contains no accumulation
points from above, but does contain countably many accumulation points from below,
and these accumulation points accumulate at .
Results such as these have also been proved for a variety of combinatorial structures,
for surveys of which we refer to Bollobas [
5
] and Klazar [
10
]. In particular, Balogh, Bol-
lobas, and Morris [
4
] extended Kaiser and Klazars work to the more general setting of
ordered graphs
1
and conjectured both that the set of growth rates of ordered graphs con-
tains no accumulation points from above, and that all such growth rates are either integral
1
Let G and H be graphs on
1
, . . . , n
and
1
, . . . , k
, respectively. We say that H is an ordered subgraph of
G
if there is an increasing injection f :
1
, . . . , k
1
, . . . , n
such that i
H
j
if and only if f
i
G
f
j
.
For any permutation of length n we can construct the ordered graph G
on the vertex set
1
, . . . , n
by
taking i
G
j
for i
j
if and only if
i
j
. It follows that G
contains G
as an ordered subgraph
if and only if
, so every permutation class can be viewed as a hereditary property of ordered graphs.
Thus in particular, the set of growth rates of permutation classes is contained in the set of growth rates of
hereditary properties of ordered graphs. The converse, however, is not true. For example, Balogh, Bollobas,
and Morris [
4
] show that the largest real root of x
5
x
4
x
3
x
2
2
x
1
, approximately 2.03166, is the
growth rate of a hereditary property of ordered graphs (they conjecture that it is the smallest such growth rate
above 2), but the results of Vatter [
12
] show that this number is not the growth rate of a permutation class.
P
ERMUTATION
C
LASSES OF
E
VERY
G
ROWTH
R
ATE
A
BOVE
2.48187 . . .
3
or algebraic irrationals. These conjectures were disproved by Albert and Linton [
3
], who
showed that the set of growth rates of permutation classes contains a perfect set (a set
which is equal to its accumulation points, e.g., the middle thirds Cantor set). Albert and
Linton also conjectured that there is some such that every real number at least is the
growth rate of a permutation class. Our main theorem, below, resolves this conjecture.
Theorem 1.1.
Let denote the unique real root of x
5
2x
4
2x
2
2x
1
, approximately 2.48187.
Every real number greater than is the growth rate of a permutation class.
In the next section we establish the terminology and basic analytic facts needed for the
proof of Theorem
1.1
, which is carried out in Section
3
. We conclude with comments and
conjectures.
2.
S
UMS OF
P
ERMUTATIONS AND
S
ERIES OF THE
F
ORM
1
1
s
n
x
n
Given two permutations and of respective lengths n and k, their direct sum,
, is
the permutation of length n
k
which consists of followed by a shifted copy of :
i
i
for i
n
,
i
n
n
for n
1
i
n
k
.
A class C is said to be sum closed if
C
whenever ,
C
. The classes we use to prove
Theorem
1.1
will all be sum closed, and so we begin by recalling a few simple facts about
these classes.
A permutation is said to be sum indecomposable (or connected or simply indecomposable)
if it cannot be written as the direct sum of two shorter permutations. Note that every
permutation has a unique representation as a sum of sum indecomposable permutations.
Proposition 2.1.
For all n
1
, let s
n
denote the number of sum indecomposable permutations in
the sum closed class C. Then the generating function for C is 1
1
s
n
x
n
.
Proof. The permutations in C are in bijection with sequences of nonempty sum indecom-
posable permutations in C. Thus the generating function for C is 1
s
1
x
s
2
x
2
s
1
x
s
2
x
2
2
1
1
s
n
x
n
.
From Proposition
2.1
applied to the (sum closed) class of all permutations, we see that
the number, ip
n
, of sum indecomposable permutations of length n satises
n 1
n!x
n
1
1
n 1
ip
n
x
n
,
so
n 1
ip
n
x
n
1
1
n 1
n!x
n
.
P
ERMUTATION
C
LASSES OF
E
VERY
G
ROWTH
R
ATE
A
BOVE
2.48187 . . .
4
(This is due originally to Comtet [
7
, Exercise VI.14].) The sequence
ip
n
begins
1, 1, 3, 13, 71, 461, 3447, 29093, 273343, 2829325, 31998903, . . . .
For the rest of the section we are concerned only with series of the form 1
1
s
n
x
n
.
We extend the denition of growth rate to generating functions, dening
gr
a
n
x
n
lim sup
n
n
a
n
,
and
gr
a
n
x
n
lim
n
n
a
n
,
when this limit exists (which we will always be the case for the series we consider). First
we recall the following fact.
Pringsheims Theorem
(see Flajolet and Sedgewick [
8
, Section IV.3]). For any sequence
a
n
of nonnegative numbers, the upper growth rate of
a
n
x
n
is equal to the reciprocal of its smallest
positive pole.
Our next two propositions can be found (in slightly different forms) in Albert and Lin-
tons work [
3
].
Proposition 2.2.
For any sequence
s
n
n 1
of bounded positive integers, the growth rate of 1
1
s
n
x
n
exists and is equal to the greatest positive solution of
s
n
x
n
1
.
Proof. First we prove that the limit exists. Consider an alphabet A containing, for each n,
s
n
letters of weight x
n
. Then the generating function counting words over A by weight is
1
1
s
n
x
n
; suppose that this is equal to
a
n
x
n
. The concatenation operation gives
an injection from pairs of words of weight m and n to words of weight m
n
, proving
that a
m
n
a
m
a
n
. Because s
1
1
, we have that a
n
1
for all n, so log a
n
exists for all
n
and is superadditive. Feketes lemma then implies that lim
n
n
a
n
e
lim
n
log a
n
n
e
sup log a
n
n
. Furthermore, this limit is nite because the sequence
s
n
is bounded.
Now let denote the growth rate of 1
1
s
n
x
n
. By Pringsheims Theorem is
the reciprocal of the smallest positive pole of this series, and because
s
n
is bounded, the
radius of convergence of
s
n
x
n
is 1. Thus the smallest pole of 1
1
s
n
x
n
is the least
positive solution of
s
n
x
n
1
, making the greatest positive solution of
s
n
x
n
1
.
Proposition 2.3.
Fix
0
and c a positive integer. There is a constant m
m
, c
such that if
two sequences
r
n
n 1
and
s
n
n 1
of positive integers eac