
182 Combinatorics of Permutations, Second Edition.
the best possible result. Josef Cibulka [90] has recently improved the upper
bound of Corollary 4.66 as follows. Let c
k
be the smallest constant satisfying
S
n
(q) <c
n
k
for all patterns q of length k, and all positive integers n.Then
there is a constant C so that the inequality
c
k
≤ 2
Ck log k
holds. Though this is a significant improvement, the upper bound obtained
for c
k
is still an exponential function of k.
The following definition enables us to discuss a conjecture that suggests a
much more realistic value for c
k
.
DEFINITION 4.67 A pattern q is called layered if q can be written as
the concatenation q
1
q
2