DMTCS vol. 19:2, 2018, #3

arXiv:1704.02959v3 [math.CO] 4 Feb 2018

Discrete Mathematics and Theoretical Computer Science

Improving bounds on packing densities of
4-point permutations
Jakub Sliačan1
12Walter Stromquist2

Department of Mathematics and Statistics, The Open University, UK
Department of Mathematics, Bryn Mawr College, USA

received 26th Apr. 2017, revised 1st Nov. 2017, accepted 21st Nov. 2017.
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 list a number of upperbounds for 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.
Keywords: permutation density, permutation packing, permuton, subpermutation

1 Introduction
In this paper, we study packing densities of small permutations. A permutation is an ordered tuple utilizing all integers from {1, . . . , n}. We say that S = S[1]S[2] · · · S[m] is a sub-permutation of P =P [1]P [2] · · · P [n] if there exists an m-subset {k1 , . . . , km } of {1, . . . , n} such that for all 1 ≤ i, j ≤ m,
S[i] < S[j] whenever P [ki ] < P [kj ]. We denote by #(S, P ) the number of occurrences of S as a subpermutation of P . Let Pn be the set of all permutations of length n. If #(S, n) = maxP ∈Pn #(S, P ),nthen the packing density of S is defined to be p(S) = limn→∞ #(S, n)/ m.
The study of permutation packing densities began with Wilf’s 1992 SIAM address. Galvin (unpublished) soon rediscovered the averaging argument of Katona et al. (1964), thus proving that p(S) exists
for all permutations S. The original argument was in the setting of graph theory. In 1993, Stromquist,and independently Galvin and Kleitman (both unpublished), found the packing density of 132. Up tosymmetry, 132 is the only permutation of length 3 with a non-trivial packing density.
For 4-point permutations and their packing densities, it is useful to consult Table 1. First results for 4point permutations, including 1324, 1432, and 2143, came as part of the investigation of various layered
patterns by Price (1997). Later, Albert et al. (2002) proved a tight upper bound for 1243, and upperbounds of 2/9 for both 2413 and 1342. The current lower bound for the packing density of 2413 wasgiven by Presutti and Stromquist (2010). The upper bounds of 0.1047805 and 0.1988373 for 2413 and1342, respectively, are mentioned in passing in Balogh et al. (2015). They do not discuss them any further.
It is worthwhile to point out that Balogh et al. (2015) used flag algebras to attack the packing density
problem for monotone sequences of length 4. To the best of our knowledge, the only other application
ISSN 1365–8050

c 2018 by the author(s)Distributed under a Creative Commons Attribution 4.0 International License

2

Jakub Sliačan, Walter Stromquist
S
1234
1432
2143
1243
1324
1342
2413

lower bound
1
β
3/8
3/8
0.244∗
γ∗≈ 0.104724

ref LB
trivialPrice (1997)
trivialtrivialPrice (1997)
Batkeyev
Presutti and Stromquist (2010)

upper bound
1
β
3/8
3/8
−∗
0.1988373∗
0.1047805∗

ref UB
trivialPrice (1997)
Price (1997)
Albert et al. (2002)
Price (1997)
Balogh et al. (2015)
Balogh et al. (2015)

Tab.
p of packing densities for 4-point permutations. Values β and γ are known exactly: β =p 1: Overview

√
3 √
3 √
2 − 1 − 6/
2 − 1 + 4 ∼ 0.423570, γ = (2 3 − 3)β ∼ 0.19657960. We know that the packing density
6
of 1324 is close to 0.244 but there is no non-trivial upper bound. The items with an (∗ ) asterisk will be updated by thecurrent work.

of flag algebras to permutation packing, although indirect, is by Falgas-Ravry and Vaughan (2013). They.
obtained the inducibility (as packing density is refered to in graph theory) of a 2-star directed graph
Their result implies the known upper bound for the packing density of 132. Later, Huang (2014) used anargument exploiting equivalence classes of vertices to extend the result to all directed k-stars. This argument was known in the permutations setting since Price (1997) used it to establish the packing densities
p(1k . . . 2) for all k. Similarly, although flag algebra software package Flagmatic, written by Vaughan(2013), has been available since 2013, it has not previously been used to obtain an upper bound on thepacking density of 1324.
Therefore, we decided to use the flag algebras method to collect, enhance, and improve results inpermutation packing densities. In addition to the mathematical content, we make available a flag algebras
package for permutations, Permpack, written as a Sage script. For more information about the software,
follow Developers (2017). It does all our computations and can be used for further research. Permpack
uses syntax similar to Flagmatic, but requires no installation. We hope this makes it more user friendly.
The rest of this paper is structured as follows. The aim of Section 2 is to introduce notation and concepts, including the part of flag algebras that we need. While Razborov (2007) presented flag algebras in
the general setting of a universal model theory without constants and function symbols, we choose permutations to be the structures on which we base our exposition. Section 3 presents the main results of thischapter. We use flag algebras to provide upper bounds for the packing densities of 4-point permutations
1324, 1342, and 2413. We learnt belatedly about the existence of the latter two bounds from Balogh et al.
(2015). Regarding lower bounds, we give a new lower bound construction for the packing density of 1342
that meets our upper bound to within 10−5 . In case of 1324, we provide a lower bound that agrees withthe upper bound on the first five decimal places. Section 4 gives a list of selected upper bounds to illustrate
the potential of the flag algebras method in the area of permutation packing. These results are not best
possible, but can be obtained effortlessly by using our flag algebras package Permpack.

2 Definitions and concepts
A pattern of length k, where k ≤ n, is a k-tuple of distinct integers from [n] := {1, . . . , n}. Pattern oflength n is called a permutation. We write tuples as strings: 1324 stands for (1, 3, 2, 4). Two patterns P
and S of length k are identical, if P [i] = S[i] for all i ∈ [k]. They are order-isomorphic if for all pairsImproving bounds on packing densities of 4-point permutations

3of indices i, j, it holds that P [i] < P [j] implies S[i] < S[j]. For a set I = {i1 , . . . , im } of m indicesfrom [n], the sub-pattern P [I] is the m-tuple P [i1 ]P [i2 ] · · · P [im ]. By overloading the notation slightly,
we also use P [I] to refer to the subpermutation of length m which is order-isomorphic to the sub-pattern
P [I].
A decreasing (increasing) permutation of length k is the k-tuple k . . . 321 (123 . . . k). A permutation P
is layered, if it is an increasing sequence of decreasing permutations. To be exact, a layered permutation P
is a concatenation of smaller permutations P = P1 P2 . . . Pℓ such that for all 1 ≤ i ≤ ℓ, Pi is a decreasing
sequence of consecutive integers satisfying the following: if x ∈ Pi and y ∈ Pj with i < j, then x < y.
For instance, 321465987 can be partitioned as 321|4|65|987, so it is layered. On the other hand, 2413 is
not layered.
Given S and P of lengths m and n, respectively, we let #(S, P ) denote the number of times that S
occurs as a subpermutation of P . The density of S in P isp(S, P ) =#(S, P ) .
nm

If n < m, we set p(S, P ) = 0. Intuitively, p(S, P ) is the probability that a random m-set of positions
from [n] induces a pattern in P that is order-isomorphic to S. For example, p(12, 132) = 2/3 as both 13
and 12 are order-isomorphic to 12 while 32 is not.
Let F be a set of forbidden permutations. We say that permutation P is F -free if #(F, P ) = 0
for all F ∈ F . Such P is also said to avoid F or be admissible. We denote by Pn the set of alladmissible permutations of length n. It will always be clear from context what F is. If F = ∅, then theadmissible set Pn is the set of all permutations of length n. Notice that if P is admissible, then so are allits subpermutations. Most of the work in this paper concerns the case when F = ∅. However, the setting
remains the same whenever F is non-empty, and we provide a few examples to this effect.

Fig. 1: Permutations in P3 , with F = ∅. From left to right: 123, 132, 213, 312, 231, 321.
Let P ∈ Pn and S ∈ Pm be admissible permutations, and assume m ≤ n. The maximum value ofp(S, P ) over P ∈ Pn is denoted by p(S, n). Conversely, a permutation P such that p(S, P ) = p(S, n) is
an S-maximiser of length n. It is well-known that for every S, the sequence (p(S, n))n≥0 converges to avalue in [0, 1] because it is non-increasing and stays between 0 and 1. See Katona et al. (1964). We are
now ready to define the quantity that we study, packing density.
Definition 1. Let S be a fixed permutation and P = ∪n≥1 Pn the set of admissible permutations. The
packing density of S isp(S) = lim p(S, n).
n→∞

For example, the packing density of 12 in 123-free permutations is 1/2. Notice that every maximiserof size n has at most two layers. It is then easy to see that they should be of balanced sizes for the packing
density to be maximised, i.e. ⌊n/2⌋ and ⌈n/2⌉. Let Pn be such balanced 2-layered maximizer of lengthn. Clearly, p(12, Pn ) → 1/2 as n → ∞.

4Jakub Sliačan, Walter Stromquist

We now formalise the ideas about asymptotic quantities and objects that the discussion is leading to.
Let (Pn )n = P1 , P2 , P3 , . . . be a sequence of permutations of increasing lengths. We say that (Pn )n isconvergent if for every permutation S, (p(S, Pn ))∞n=1 converges. A permuton µ is a probability measurewith uniform marginals on the Borel σ-algebra B([0, 1]2), i.e. for every a, b ∈ [0, 1] with a < b, it holds
that µ([a, b] × [0, 1]) = b − a = µ([0, 1] × [a, b]). See examples of permutons in Figure 2.

(a) Increasing(b) Lebesgue(c) 1243-maximiser

Fig. 2: Examples of permutons. In (a) we have the limit of (1 . . . n)∞n=1 , in (b) it is, with probability one,the limit of a sequence of randomly chosen permutations of each length, and in (c) we have the limit of(1 . . . ⌊n/2⌋n . . . ⌈n/2⌉)∞n=1 .
Let µ be a permuton and S a permutation on [m]. One can sample m points from [0, 1]2 according
to µ and with probability one they will be in general position (no two aligned vertically or horizontally).
We define p(S, µ) as the probability that a randomly sampled m points from [0, 1]2 according to µ areorder-isomorphic to S. It turns out that every convergent sequence of permutations has its permutonand vice versa. In particular, Hoppen et al. (2013) proved that for every (Pn )n≥0 there exists a uniquepermuton µ such that for every S, p(S, µ) = limn→∞ p(S, Pn ). In this sense, µ is the limit of thesequence (Pn )n . In the other direction, they proved that if µ is a permuton and Pn is a permutation oflength n sampled at random according to µ from [0, 1]2 , then with probability one the sequence (Pn )nis convergent (with µ as its limit). The concept of permutation limits was known as “packing measures”
since Presutti and Stromquist (2010) used them for constructing the 2413 lower bound. In the current
work, we use permutons mainly to describe extremal constructions that yield our lower bounds.

2.1 Flag Algebras
The term flag algebras refers to a framework first introduced by Razborov (2007). It proved to be avery useful tool for researchers in extremal graph theory, but found use in other fields as well. For
an overview of results aided by flag algebras, see Razborov’s own survey Razborov (2013). For more
extensive expositions, see the PhD theses of Sperfeld (2012) and Volec (2014). By now, there are also
many papers with explanations and examples such as Baber and Talbot (2011), Falgas-Ravry et al. (2015),
Falgas-Ravry and Vaughan (2012), Falgas-Ravry and Vaughan (2013). For a long list of important results
across disciplines of discrete mathematics that were aided by flag algebras, see the abovementioned theses,
especially Chapter 1 of Volec (2014). The main flag algebra result in permutations is Balogh et al. (2015).
In their work on quasirnadom permutations, Král’ and Pikhurko (2013) mention flag algebras as anotherway to think about the subject. It is important to note that the method of flag algebras has evolved fromother combinatorial and analytic methods in combinatorics which had been used by researchers for a longtime. The Cauchy-Schwarz type arguments can be found in e.g. work by Bondy (1997) as early as 1990s.
The ideas pertinent to quasirandomness have been around since Chung et al. (1988). And while there
are other analytic methods that were used successfully to attack extremal problems in combinatorics, theImproving bounds on packing densities of 4-point permutations

5

method of flag algebras is syntactical and lends itself to automation. The syntax-based nature of flag
algebras is the main feature that distinguishes the theory of flag algebras from the theory of dense graphlimits (see e.g. Lovász (2012)). The crux of the method is a systematic conversion of the combinatorial
problem into a semidefinite programming problem. The latter can be solved (efficiently) by current SDP
solvers. The numerical values returned by the SDP solvers then need to be transformed to exact values(rational or algebraic) to provide valid upper bounds on packing densities.
Before we delve into the method itself, let us consider an example from before. For the remainder ofthis section, assume that all objects (permutations, flags, types) are admissible unless stated otherwise.
Now, assume that we are looking for 123-free permutations P that are as 12-dense as possible. We get thefollowing bound without much effort.
p(12, P ) = p(12, 123)p(123, P ) + p(12, 132)p(132, P ) + p(12, 213)p(213, P )
{z
}
|
=0

+ p(12, 231)p(231, P ) + p(12, 312)p(312, P ) + p(12, 321)p(321, P )2
2 2 1 1
, , , ,0 =≤ max
3 3 3 3
3

(1)This is strictly better than a trivial bound of 1. However, observe that there is no P of length greater than 4such that p(132, P ) + p(213, P ) = 1. This follows from Erdős-Szekeres theorem (adapted) which statesthat a permutation of length (r − 1)(s − 1) + 1 contains either an increasing subpermutation of length r
or a decreasing subpermutation of length s. Hence, a permutation of length 5 contains 123 or 321 as asubpermutation. So there are always subsets of size 3 in P which do not induce 132 or 213. Therefore,
the bound of 2/3 is unachievable in practice. Knowing this, it would be useful to be able to control how
copies of small permutations, such as 132 and 213, interact inside larger permutations. The method of flag
algebras helps us systematically take into account the ways in which small patterns overlap inside larger
structures. This takes the form of extra coefficients in front of p(12, P ) terms in (1). If chosen well, theyshift weight away from the large values like p(12, 231) and p(12, 312) and thereby reduce the maximum
over all of them.
In general, the process is analogous to the example above. If S is a small permutation whose packing
density we seek to determine, we pick a reasonably small value N ≥ |S|. The crude bound then looks asfollows.
X
p(S, P ′ )p(P ′ , P )p(S, P ) =P ′ ∈PN≤ maxp(S, P ′ )
′
P ∈PN

(2)

Before we describe how exactly we leverage overlaps between small patterns, we need to define flags,
types, and operations on them.
Definition 2 (Flag). A permutation τ -flag S τ is a permutation S together with a distinguished subpermutation τ , also called an intersection type.
See Figure 3 for a list of all 1-flags on two vertices. The set of all admissible τ flags of length m is10
τ, respectively. Noticedenoted by Pm. If τ is the permutation of length 0 or 1, we write Pm
and Pm0
τthat Pm = Pm . The support T of τ in S is the set of indices of S that span τ in S τ . We say that

6

Jakub Sliačan, Walter Stromquist
S11

S21

S31

S41

Fig. 3: If τ = 1 (as permutation), then there are four distinct τ -flags of length two. The empty circle marks τ in eachflag.

two permutation flags S1τ1 and S2τ2 are type-isomorphic if S1 = S2 and if the supports of τ1 and τ2 are
identical. For instance, in Figure 3, S11 and S41 are not type-isomorphic, because the support of τ in S11 is
1 and in S41 it is 2. For convenience, we set t := |τ |.

Definition 3. Let S τ be a τ -flag of length m, P τ a τ -flag of length n ≥ m. We define #(S τ , P τ ) to be
the number of m-sets M ⊆ [n] such that P [M ] is type-isomorphic to S τ . Flag density is then defined asfollows#(S τ , P τ ) .
p(S τ , P τ ) =n−t
m−t

In other words, p(S τ , P τ ) is the probability that a uniformly at random chosen subpermutation of lengthm from P τ , subject to it containing τ , induces a a flag type-isomorphic to S τ . For instance, consider thefollowing flag densities. The empty circle denotes τ = 1.
p( ,) = 1,p( ,) = 0,p( ,) = 1/2

Finally, we define joint density of two flags, p(S1τ , S2τ ; P τ ), as the probability that choosing an m1 -set
M1 ⊆ [n] such that P [M1 ] contains τ and choosing an m2 -set M2 ⊆ [n] such that P [M2 ] contains τand M1 ∩ M2 = τ induces τ -flags P [M1 ]τ and P [M2 ]τ in P τ which are type-isomorphic to S1τ and S2τ ,respectively. The following proposition turns out to be useful (Lemma 2.3 in Razborov (2007)). It saysthat choosing subflags with or without replacement makes no difference asymptotically.
Proposition 1. Let S1τ and S2τ be flags on m1 and m2 vertices. Let n ≥ m1 + m2 − t and P τ be a flagon n vertices. Thenp(S1τ , P τ )p(S2τ , P τ ) = p(S1τ , S2τ ; P τ ) + o(1),where o(1) → 0 as n → ∞.

τττLet ℓ = |Pm| and fix an order on elements of Pm. Let Siτ , Sjτ be τ -flags from Pmand P a τ -flagττττfrom Pn . Furthermore, let x be a vector with i-th entry p(Si , P ), and let Q be a positive semi-definite
matrix with dimensions ℓ × ℓ. Then by Proposition 1 and since Qτ  0, we have0 ≤ xQτ xT =X

Qτij p(Siτ , Sjτ , P τ ) + o(1).

i,j≤ℓMoreover, if we let σ be a uniformly at random chosen type in P of length t, the inequality above remains
true. Moreover, an “average” σ preserves the non-negativity as well.
X
1 X
p(Siτ , Sjτ ; P σ ) + o(1).
0 ≤ Eσ xQτ xT =Qτij nt σ∈ [n]
i,j≤ℓ
(t)

(3)

7

Improving bounds on packing densities of 4-point permutations

Next, we write the above expression in terms of permutations on N vertices. Having all information interms of the same objects allows us to combine it together.
X

1 X X
p(Siτ , Sjτ ; (P ′ , σ))p(P ′ , P ) + o(1)Eσ xQτ xT =Qτij nt σ∈ [n] P ′ ∈PN
i,j≤ℓ
(t)


X X
X
1

Qτij n=p(Siτ , Sjτ ; (P ′ , σ)) p(P ′ , P ) + o(1)t σ∈ [n]P ′ ∈PN
i,j≤ℓ
(t)
{z
}
|
α(P ′ ,m,τ )P
Notice that the last expression is of the form P ′ ∈PN α(P ′ , m, τ )p(P ′ , P ). There is one of those foreach type τ and value m. Every such choice will require another matrix Qτ . In practice, we first choose
N , then take all possible pairs of t and m such
Pthat N = 2m − t. Thus once N is fixed, the choice oft determines the rest. Therefore, let α(P ′ ) = τ α(P ′ , m, τ ) and recall that the expression that we aretrying to minimise, subject to Qτ  0 for all τ , comes from (2). By adding inequalities of the form of (3)to (2), we obtainp(S, P ) =X

p(S, P ′ )p(P ′ , P )P ′ ∈PN≤XP ′ ∈PN

p(S, P ′ )p(P ′ , P ) +α(P ′ )p(P ′ , P )P ′ ∈PN≤ max{p(S, P ′ ) + α(P ′ )}.
′
P ∈PN

X

(4)

This problem (4) has the form of a semidefinite programming problem subject to the condition that Qτ  0
for every type τ . There exist numerical solvers, such as CSDP or SDPA, that we can use. However, thesolution is in the form of numerical PSD matrices. These need to be converted to exact matrices without
floating-point entries in a way that preserves their PSD property and still yields a bound that we aresatisfied with. Since none of our bounds is tight, we will take a shortcut in rounding. Let Q′ be a numericalmatrix returned by the solver. Since it is positive semi-definite, it admits a Cholesky decomposition intoa lower and upper triangular matrices: Q′ = L′ L′T . We compute this decomposition and then roundthe L′ matrices into L matrices in such a way that they do not have negative entries on the diagonals.
In certificates, we provide these L matrices instead of Q matrices. This way, one can readily check that
Q = LLT  0 by inspecting the diagonal entries of the L matrices.

2.2 Example
The following example is a done-by-hand flag algebras√ method on a small problem of determining thepacking density of 132. We have a lower bound of 2 3 − 3 ≈ 0.464101615 . . . given by the standard
construction. Assume we want to obtain an upper bound for the packing density of 132. Let P be a (large)

8

Jakub Sliačan, Walter Stromquist

132-maximiser of length n and let 3 ≤ ℓ ≤ n. By (2) we getp(132) ≤ p(132, P )X
p(132, P ′ )p(P ′ , P )=P ′ ∈Pℓ≤ maxp(132, P ′ ).
′
P ∈Pℓ

√
We choose ℓ = 3 and set λ = 2 3 − 3. Now consider∆ = λp(123, P ) + (λ − 1)p(132, P ) + λp(213, P ) ++5λ − 3p(231, P )65λ − 3p(312, P ) + λp(321, P ).
6

Adding the linear combination ∆ of P ′ densities to the previous crude upper bound improves it to λ.
Xp(132, P ) ≤p(132, P ′)p(P ′ , P ) + ∆P ′ ∈Pℓ≤ max{λ, λ, λ,′P ∈Pℓ5λ − 3 5λ − 3
,
, λ}
6
6

=λ
The key property of ∆ is that it is non-negative for all P , including all P ′ ∈ P3 . Let σ be a randomly
chosen vertex out of the three available. The matrix Q below is positive semi-definite and xP ′ is a vectorof flag densities for flags in Figure 3:
xP ′ = p( , (P ′ , σ)) p( , (P ′ , σ)) p( , (P ′ , σ)) p( , (P ′ , σ)) .

0
0
0
0
0
λ
λ
3(λ − 1)/2

Q=
0
λ
λ
3(λ − 1)/2
0 3(λ − 1)/2 3(λ − 1)/2
3λ
Averaging over σ gives the expression (6) that makes the non-negativity of ∆ apparent.
!
X
T
xP ′ QxP ′ ≥ 0∆ = Eσ√Therefore, we proved that p(132) ≤ 2 3 − 3.

(5)

(6)

P ′ ∈P3

2.3 Implementation
Flagmatic 2.0 was written by Emil R. Vaughan and is currently the only general implementation ofRazborov’s flag algebra framework which is freely available to use and modify. See Vaughan (2013) forImproving bounds on packing densities of 4-point permutations

9

more information. The project is hosted at http://github.com/jsliacan/flagmatic. Unfortunatelly, Flagmatic does not support permutations. For this reason, we wrote Permpack, a lightweight
implementation of flag algebras on top of SageMath’s Sage 7.4 (see Developers (2017)). It does not have
all the functionality of Flagmatic but it is sufficient for basic tasks. For more information, code, andinstallation instructions, see https://github.com/jsliacan/permpack.
Let us consider an example of how Permpack can be used on the above example of 132-packing. It
will be clear from Permpack’s output where the Q matrix above comes from. In Permpack, one needs tospecify the complexity in terms of N , the length of the admissible permutations which all computations
are expressed in terms of. The density pattern argument specifies the permutation whose packing
density we want to determine. Once permutations, types, flags, and flag products are computed, we
can delegate the rest of the tasks to the solver of our choice (currently supported solvers are csdp andsdpa dd). The answer is a numerical upper bound on p(132). It can be rounded automatically toa rational bound by the exactify() method of the PermProblem class. The certificate contains
admissible permutations, flags, types, matrices Q (as L matrices in the Cholesky decomposition of Q)
and the actual bound as a rational number (fraction). These are suficient to verify the bound. Below is the
script used to obtain the numerical Q′ matrix for the packing density of 132 with Permpack.
Listing 1: Packing 132 with Permpack.
p = PermProblem(3, density_pattern="132")
p.solve_sdp()

Listing 2: Output.
...
Success: SDP solved
Primal objective value: -4.6410162e-01
Dual objective value: -4.6410162e-01
Relative primal infeasibility: 5.90e-14
Relative dual infeasibility: 1.67e-10
Real Relative Gap: 3.68e-10
XZ Relative Gap: 6.14e-10

It is not difficult to guess the entries of Q from the numerical matrix below, which is part of the outputof the SDP solver. The resulting exact matrix Q is shown in (5).
Listing 3: Floating point Q′ matrix.
[ 4.55854035127455e-10 6.806084489120e-12 6.8060845047452e-12 -1.032045390820e-10][ 6.80608448912001e-12 0.4641016162301893 0.464101613919741-0.8038475767936814][ 6.80608450474521e-12 0.464101613919741
0.4641016162301782 -0.8038475767936717][-1.03204539082084e-10 -0.803847576793681 -0.8038475767936717
1.3923048450288649]

3 Results
The following theorem will be needed later. There exist further variations of it, e.g. Proposition 2.1 andTheorem 2.2 in Albert et al. (2002). However, we only need the original version.

10

Jakub Sliačan, Walter Stromquist

Theorem 1 (Stromquist (1993)). Let S be a layered permutation. Then for every n, extremal value ofp(S, n) is achieved by a layered permutation. Moreover, if S has no layer of size 1, every maximiser ofp(S, n) is layered.
The scripts used to obtain results in this section can be found athttps://github.com/jsliacan/permpack/tree/master/scripts.
The certificates in support of the upper bounds in this section can be found at the address below. With
each result, we provide the name of the certificate file that witnesses it, e.g. cert1324.js witnesses
the upper bound for p(1324).
https://github.com/jsliacan/permpack/tree/master/certificates.

3.1 Packing 1324
Layered permutations have been studied in depth by Price (1997). He came up with an approximation
algorithm that, at m-th iteration assumes that the extremal construction has m layers (see Theorem 1) and
optimises over their sizes. The algorithm then proceeds to increase m and halts when increasing m does
not improve the estimate. In that case, an optimal construction has been found (up to numerical noisefrom the optimization, if any). In reality, the procedure is stopped manually when approximation is fineenough or the problem becomes too large. Therefore, for every m, the value that Price’s algorithm gives
is a lower-bound for the packing density in question.
It is known that the extremal construction for the packing density of 1324 is layered with infinite numberof layers. See, for instance, Albert et al. (2002) and Price (1997). The main theorem of this section is thefollowing.
Theorem 2.
0.244054321 < p(1324) < 0.244054549
Proof: Consider the construction Γ from Figure 4, where Γ is a permuton. Let C denote the middle layerof Γ (the largest layer), B denote the layer above (and B ′ the layer below) C, and A denotes the group of
the remaining layers above B (and A′ denotes the groupp of layers below B ′ ). So Γ = A′ ⊕B ′ ⊕C⊕B⊕A,
where A ⊕ B means that the layer A is entirely below and to the left of the layer B. Let c = |C|,b = |B| = |B ′ |, and a = |A| = |A′ |. We assume that A (and A′ ) is isomorphic to a maximiser for thepacking of 132-pattern (213-pattern). The aim is to optimise over a and b. Ideally, the tails of Γ would
also be optimised over, but that is infeasible. So we assume the tails are 132 (213) maximisers. It turns
out that the first two steps give a good lower bound. We now compute the density of 1324 patterns in Γ.
There are four distinct (i.e. up to symmetry) positions that a copy of 1324 can assume in Γ. Let xyzw be
the four points in Γ that form a copy of 1324 in that order.
1. y, z ∈ C, x ∈ A′ ∪ B ′ , w ∈ A ∪ B, there are N1 such copies
2. y, z ∈ B, x ∈ A′ ∪ B ′ ∪ C, w ∈ A, there are N2 such copies

11

Improving bounds on packing densities of 4-point permutations
3. y, z, w ∈ A, x ∈ A′ ∪ B ′ ∪ C ∪ B, there are N3 such copies
4. x, y, z, w ∈ A, , there are N4 such copies
Let us now determine quantities N1 , . . . , N4 .
1. N1 = c2 /2 + (a + b)2
2. N2 = b2 /2 + a(a + b + c)√3
3. N3 = (2 3 − 3) a6 · (a + 2b + c)
4. N4 =√√
3·(2 3−3)4√
k=0 6·( 3+1)4k+4 · a .

P∞Finally, we get the density of 1324 pattern in Γ. Let b = 1 − c − 2a. Thenp(1324, Γ) =max

0<c≤1/20<a<≤1/4

24 · (N1 + 2N2 + 2N3 + 2N4 )> 0.244054321.
This proves the lower bound in Theorem 2, because 0.244054321 < p(1324, Γ) ≤ p(1324).

0 a

b

c

b

a 1

Fig. 4: Permuton Γ provides a lower bound for p(1324). The triangles at the ends represent permutons that are
maximisers for the packing of 132 and 213 (L to R).
We use Flagmatic to prove the upper bound. Since 1324 is layered, there is a 1324-maximiser that islayered as well. Therefore, we can limit the search space to the layered permutations. Since Flagmatic
does not work with permutations, we transformed the problem to an equivalent problem in directed graphs– which Flagmatic can handle.

12

Jakub Sliačan, Walter Stromquist,} be the set of forbidden digraphs. The packing density of 1324 equals
Lemma 1. Let F = { ,-density of F . In other words,
the Turánp(1324) = p(

, F ).

Proof 1: There is a unique way to encode a layered permutation P as a directed graph D. If and only,, and
if two points x, y ∈ P form a 12 pattern, then xy is an arc x → y in D. Forbiddingin D forces it to be a union of independent sets with arcs between them so that if x, y are vertices in one
independent set and u, v are vertices in another independent set of D, then if xu is an arc in D, so are
xv, yu, and yv. In other words, all arcs between two independent sets are present, and all go in the same
direction. Moreover, the direction is transitive (is forbidden). Together with the first rule about thedirection of arcs between independent sets, this fully characterizes the digraph D from the permutation
P . Clearly, the process is reversible.
Given Lemma 1, we use flag algebra method on directed graphs to compute an upper bound for thepacking density of(an equivalent of 1324 in digraphs) over { ,,}-free digraphs. The
resulting bound is the one in Theorem 2. The certificate is called cert1324flagmatic.js. Notethat this is a Flagmatic certificate and can be verified using the inspect certificate.py script thatcomes with Flagmatic. The script is pack1324flagmatic.sage.
A similar bound can be achieved by Permpack. In particular, we can show that p(1324) < 0.244054540.
Certificate: cert1324permpack.js. Script: pack1324permpack.sage. Despite Permpack being able to prove a good bound, we used Flagmatic in the proof above to emphasise that this result had
been available before Permpack was written.

3.2 Packing 1342
The previous lower bound for the packing density of 1342 was approximatelly 0.1965796. The resultof Batkeyev can be found in Albert et al. (2002).

Fig. 5: On the left is Batkeyev’s construction for the lower bound on p(1342) as product of packing densities of 132
and 1432. On the right is the schematic drawing of it. The triangle stands for a 231-maximiser and the square stands
for the part inside which the entire construction is iterated.
√
Let λ = 2 3 − 3 be the packing density of 231 and κ the ratio between the top layer and the rest of
the 1432-maximiser, see Price (1997) (κ is the root of 3x4 − 4x + 1). Batkeyev suggested to replace eachImproving bounds on packing densities of 4-point permutations

13

layer in the maximiser of 1432 by a 231-maximiser while preserving the size ratio κ. The density of 1342
in Batkeyev’s construction (see Figure 5) is∞X√(1 − κ)3 κ4n+1
p(1342, B) = (8 3 − 12) ·n=0= p(132)p(1432)
!
q
 √

3
3 √
=2 2 3−33
2−1− p+2√32−1≈ 0.1965796 . . .

This lower bound was widely regarded as possibly optimal. Our contribution to this problem is findinga vastly better lower bound construction. However, if we restrict the space of admissible permutations tothose that avoid 2431, then Batkeyev’s construction is likely optimal. We are able to prove the following
theorem on N = 6 admissible graphs to keep the SDP small (if N = 7 was chosen, the bound would
likely be slightly better).
Theorem 3.
p(1342, {2431}) < 0.19658177.
Proof: Certificate: cert1342 forb2431.js. Script: pack1342 forb2431.sage.
The following result addresses the actual packing density of 1342 without any forbidden patterns.
Theorem 4.
0.198836597 < p(1342) < 0.198837287.
Proof: The new lower bound is given by the construction Π in Figure 6. The weights we used for theparts are given in cert1342lb.txt, located with other certificates.
a1 = 0.2174127723536347308692444843
a2 = 0.0170598057899242722740620549
a3 = 0.0516101402487892270230230972
a4 = 0.4340722809873864994312953007(7)a5 = 0.1479895625950390496250611829
a6 = 0.0764457255805656971383351365
a7 = 0.0554097124446605236389787433
Label the 7 parts of Π from left to right as a1 , . . . , a7 . We assign the weights to them roughly as in (7).
Then a straightforward calculation of the 1342 density in Π implies the desired lower bound. The sage
script that does this is called lb1342.sage, located with other scripts. The upper bound certificate iscalled cert1342.js. Script is pack1342.sage.
The upper bound obtained without flag algebras stands at 2/9, see Albert et al. (2002). The upperbound above was obtained via the flag algebras method and confirms the claimed bound from Balogh

14

Jakub Sliačan, Walter Stromquist

Fig. 6: New lower bound construction Π for the packing density of 1342. The part sizes, left to right, are approximatelly 0.2174, 0.0170, 0.0516, 0.4341, 0.1480, 0.0764, 0.0554. The square part represents the part inside which thewhole construction is iterated. The triangle part is the extremal construction for 231-packing.
et al. (2015). We used N = 7 for our computations. While it is possible that N = 8 would yield a slightly
better bound, the computations would be much more expensive. Without a candidate for an exact lower
bound, we were satisfied with the bound we obtained with N = 7.

3.3 Packing 2413
The case packing 2413 patterns is fairly complicated as can be seen from the lower bound construction
by Presutti and Stromquist (2010). The previous upper bound obtained without flag algebras was 2/9
by Albert et al. (2002). The bound below was obtained via flag algebras and is in the same range as thebound in Balogh et al. (2015).
Theorem 5.
p(2413) < 0.10478046354353523761779.
Proof: Certificate: cert2413.js. Script: pack2413.sage.
We used admissible permutations of length N = 7. Again, larger N could yield a slightly better upperbound, but without an exact lower bound, this effort would not be justified.

4 Packing other small permutations
The flag algebras method will yield upper bounds for many problems. In some cases these bounds are
particularly interesting because they are close to their corresponding lower bounds. In this section we lista selection of upper and lower bounds that are potentially sharp since their values appear to be close toeach other.
In the list below we choose to represent the permutations by their drawings in the grid. This is moretransparent as the permutations became larger. The extremal constructions (permutons) on the left-handside of the Table 2 are represented by their drawings as well. The lower bounds are given on the left-hand15

Improving bounds on packing densities of 4-point permutations
Permutation
23154
14523
21354
231654231564231645215634Lower bounds !
p

,



p
p
p

√
(3/5)
= 5! (2/5)
2!
3! (2 3 − 3)2

 ∼ 0.153649 . . .

,

!

,
,

!

∼ 0.16515 . . .

≤ 0.153649 . . .

p





≤ 0.16515 . . .

p
p

,

p

,



p

,





p



p


Upper bounds ≤ 0.16039 . . .
p√
6= 6! (1/2)
3!2 (2 3 − 3)





3

√
 = (2 3 − 3)2 6!248√
 = (2 3 − 3)2 6!2
48
=

6!
93 23



≤ 0.145031 . . .

≤ 0.0673094

p





≤ 0.0673094

p





≤ 0.123456 . . .

Tab. 2: Exact values are known for all densities on the left-hand side. They are described in the text as they are noteasy to write down.
side of the table and upper bounds on the right-hand side of the table. This is a sample of the results
obtained with Permpack via flag algebras.
We now give the descriptions of the lower bound constructions. For 23154 =, the construction is asum of two parts in ratio 2 : 3 top to bottom. The bottom part is a 231-maximiser while the top part is a
simple decreasing segment. Certificate: cert23154.js. Script: pack23154.sage.
The construction for 14523 =is designed as follows. Let α be the maximiser of 5(1−x)4 /(1−x5 )such that α ∈ [0, 1]. The topmost sum-indecomposable part of the-maximiser has length α and theremainder of the maximiser has length (1 − α). The construction is iterated inside the part of length(1 − α). The part of length α is a skew-sum of two balanced increasing segments. The exact value of thedensity on the left-hand side of Table 2 is too complicated to fit in. Certificate: cert14523.js. Script:
pack14523.sage.
is a 4-layered permuton with layers of lengths β, 1/2−β, 1/2−β, β,The construction for 21354 =top to bottom. Here, β is the real root of 40x3 − 32x2 + 9x − 1 = 0. Again, we only write theapproximate value on the left-hand side in Table 2 for space reasons. Certificate: cert21354.js.
Script: pack21354.sage.
The construction for 231654 =is identical in structure to the construction for, except the ratiosof the two parts in the sum are 1 : 1. Certificate: cert231654.js. Script: pack231654.sage.

16

Jakub Sliačan, Walter Stromquist

The construction for 231564 =is the sum of two 231-maximisers of equal size. In case of, the top 231-maximiser is flipped accordingly. Certificates: cert231564.js and231645 =cert231645.js. Scripts: pack231564.js and pack231645.js.
The construction for 215634 =has three segments of equal length arranged as portrayed in Table 2. Certificate: cert215634.js. Script: pack215634.sage.

5 Conclusion
While we now know the packing densities of all 4-point permutations with accuracy of 0.01%, finding
candidates for optimal constructions for the cases of 1324 and 1342 remains a challenge. In the case of1324, a new idea for the part ratios will be needed to come up with a possible extremal construction. As
for the 1342 pattern, the extremal construction might use a different layer formation than our Π. Even ifΠ has the right structure, the part ratios remain to be determined precisely. The latest status of 4-point
packing densities is depicted in Table 3.
S
1234
1432
2143
1243
1324
1342
2413

lower bound
1
β
3/8
3/8
0.244054321∗
0.198836597∗≈ 0.104724

ref LB
trivialPrice (1997)
trivialtrivial––Presutti and Stromquist (2010)

upper bound
1
β
3/8
3/8
0.244054549∗
0.198837286342∗
0.104780463544∗

ref UB
trivialPrice (1997)
Price (1997)
Albert et al. (2002)–––

Tab. 3: Overview of packing densities for 4-point permutations given the information in this paper. The values withasterisk have been updated.
After 4-point permutations, there are many packing densities of small permutations of length 5, 6, . . ..
The values of lower bounds and upper bounds in Table 2 should be made to match. In some cases this will
be easier than in others. In particular, the packing density of 21354 has been mentioned in both Albert
et al. (2002) and Hästö (2002).
There are analogous questions to be asked about packing densities when certain patterns are forbidden.
As an example, we mentioned p(1342, {2431}) in relation to p(1342).
Next, an interesting line of enquiry was made precise as Conjecture 9 in Albert et al. (2002). For apacking of pattern S, is there an extremal construction with infinite number of layers? Are all extremal
constructions of that form? More precisely, let an S-maximiser be an n-permutation P such that p(S, n) =p(S, P ). If Ln is the number of layers in a layered maximiser of length n, what can we say about Ln
as n → ∞? For example, we know that the number of layers in every 1324-maximiser is unbounded as
n → ∞. We also know that a 2143-maximiser has only two layers, regardless of n.

Acknowledgements
We would like to thank Robert Brignall for heaps of useful discussions.

Improving bounds on packing densities of 4-point permutations

17

References
M. H. Albert, M. D. Atkinson, C. C. Handley, D. A. Holton, and W. Stromquist. On packing densities of
permutations. Electron. J. Combin, 9(1), 2002.
R. Baber and J. Talbot. Hypergraphs do jump. Combinatorics, Probability and Computing, 20(2):161–
171, 2011. ISSN 0963-5483. doi: 10.1017/S0963548310000222. URL http://dx.doi.org/
10.1017/S0963548310000222.
J. Balogh, P. Hu, B. Lidický, O. Pikhurko, B. Udvari, and J. Volec. Minimum number of monotone
subsequences of length 4 in permutations. Combinatorics, Probability and Computing, 24(04):658–
679, 2015.
B. Batkeyev. Extremal construction for 1342-packing. unpublished.
J. A. Bondy. Counting subgraphs a new approach to the Caccetta-Häggkvist conjecture. Discrete Mathematics, 165:71–80, 1997.
F. R. K. Chung, R. L. Graham, and R. M. Wilson. Quasirandom graphs. Proc. Nat. Acad. Sci. U.S.A., 85(4):969–970, 1988.
T. S. Developers. SageMath, the Sage Mathematics Software System (Version 7.4), 2017. http://www.
sagemath.org.
V. Falgas-Ravry and E. R. Vaughan. Turán H-densities for 3-graphs. The Electronic Journal of Combinatorics, 19(3):P40–, 2012.
V. Falgas-Ravry and E. R. Vaughan. Applications of the semi-definite method to the Turán density problem for 3-graphs. Combinatorics, Probability and Computing, 22(01):21–54, 2013.
V. Falgas-Ravry, E. Marchant, O. Pikhurko, and E. R. Vaughan. The codegree threshold for 3-graphs withindependent neighborhoods. SIAM Journal on Discrete Mathematics, 29(3):1504–1539, 2015.
P. A. Hästö. The packing density of other layered permutations. Electronic Journal of Combinatorics, 9(2), 2002.
C. Hoppen, Y. Kohayakawa, C. G. Moreira, B. Ráth, and S. M. R. Limits of permutation sequences.
Journal of Combinatorial Theory, Series B, 103(1):93–113, 2013.
H. Huang. On the maximum induced density of directed stars and related problems. SIAM Journal on
Discrete Mathematics, 28(1):92–98, 2014.
G. Katona, T. Nemetz, and M. Simonovits. On a problem of turán in the theory of graphs. Matematikai
Lapok, 15:228–238, 1964.
D. Král’ and O. Pikhurko. Quasirandom permutations are characterized by 4-point densities. Geometricand Functional Analysis, 23(2):570–579, 2013. ISSN 1420-8970. doi: 10.1007/s00039-013-0216-9.
URL http://dx.doi.org/10.1007/s00039-013-0216-9.
L. Lovász. Large networks and graph limits, volume 60. American Mathematical Soc., 2012.

18

Jakub Sliačan, Walter Stromquist

C. B. Presutti and W. Stromquist. Packing rates of measures and a conjecture for the packing density of2413. Permutation patterns, 376:287–316, 2010.
A. L. Price. Packing densities of layered* patterns. PhD thesis, University of Pennsylvania, 1997.
A. A. Razborov. Flag algebras. The Journal of Symbolic Logic, 72(04):1239–1282, 2007.
A. A. Razborov. Flag algebras: an interim report. In The Mathematics of Paul Erdős II, pages 207–232.
Springer, 2013.
K. Sperfeld. Semidefinite programming in extremal graph theory. PhD thesis, Universität Rostock, 2012.
W. Stromquist. Packing layered posets into posets. unpublished, http://walterstromquist.
com/POSETS.DOC, 1993.
E. R. Vaughan. Flagmatic 2.0. http://sliacan.info/flagmatic, 2013.
J. Volec. Analytic methods in combinatorics. PhD thesis, University of Warwick, Université Paris-Diderot,
2014.