# An almost complete $t$-intersection theorem for permutations

###### Abstract.

For any $\epsilon>0$ and $n>(1+\epsilon)t$, $n>n_{0}(\epsilon)$ we determine
the size of the largest $t$-intersecting family of permutations, as well as
give a sharp stability result. This resolves a conjecture of Ellis, Friedgut
and Pilpel (2011) and shows the validity of conjectures of Frankl and Deza
(1977) and Cameron (1988) for $n>(1+\epsilon)t$. We note that, for this range
of parameters, the extremal examples are not necessarily trivial, and that our
statement is analogous to the celebrated Ahlswede-Khachatrian theorem. The
proof is based on the refinement of the method of spread approximations,
recently introduced by Kupavskii and Zakharov (2022).

##  1\. Introduction

Let $[n]=\\{1,\ldots,n\\}$ stand for the standard $n$-element set and let
$2^{[n]},{[n]\choose k}$ denote its power set and the set of all $k$-element
subsets. One of the classical results in extremal combinatorics is the
Erdős–Ko–Rado theorem [12]. We say that a family of sets is intersecting if
any two sets from the family have non-empty intersection. The EKR theorem
states that for $n\geqslant 2k$ any intersecting family
$\mathcal{F}\subset{[n]\choose k}$ has size at most ${n-1\choose k-1}$. This
result was highly influential, and by now grew into a subfield of extremal
combinatorics, studying collections of objects with forbidden intersections.

Erdős, Ko and Rado [12] also showed that the largest $t$-intersecting family
of sets in ${[n]\choose k}$ has size ${n-t\choose k-t}$, provided
$n>n_{0}(k)$. A family is $t$-intersecting if any two sets from the family
intersect in at least $t$ elements. Note that the extremal example for this
result, as well as the ‘classical’ EKR theorem, is the family of all sets that
contain a fixed $t$-element set. Later, Frankl [13] and Wilson [38] determined
the exact value of $n_{0}(k)$: the same conclusion holds for
$n\geqslant(t+1)(k-t+1)$. For smaller values of $n$, other $t$-intersecting
families become larger. For $i=0,\ldots,k-t$ define the Frankl families

$\mathcal{B}_{i}=\Big{\\{}F\in{[n]\choose k}:|F\cap[t+2i]|\geqslant
t+i\Big{\\}}.$

For $n<(t+1)(k-t+1)$ $|\mathcal{B}_{1}|>|\mathcal{B}_{0}|$. It turned out,
however, that for any values of $n,k,t$ one of $\mathcal{B}_{i}$ should be
extremal. Frankl [13] introduced the families defined above and conjectured
that for every $n,k,t$ one of them is extremal. This was shown for a wide
range of parameters by Frankl and Füredi [18] and then for all $n,k,t$ by
Ahlswede and Khachatrian [1] in the so-called ‘Complete $t$-intersection
Theorem’. This theorem played an important role in some applications to
computer science, in particular the result of Dinur and Safra [7] from
hardness of approximation.

Another very influential forbidden intersections result is due to Frankl and
Wilson [22]. It addresses the so-called Erdős–Sós problem: determine the
largest family in ${[n]\choose k}$ with intersection exactly $t$ forbidden.
Importantly, it gives an almost sharp result for the case when $k,t$ are
linear in $n$ (under some number-theoretic restrictions). This was extremely
important for applications, and the Frankl–Wilson theorem and a more general
Frankl–Rödl theorem [20] was used for several questions in discrete geometry
and Ramsey theory (for applications in discrete geometry, see [21], [35],
[36]).

Forbidden intersections were studied for structures other than families in
$2^{[n]}$ or ${[n]\choose k}$: graphs [8], partitions [34] [29], simplicial
complexes [4] [30], vector spaces [19], and permutations. Permutations are by
far the most studied object in this respect. Denote by $\Sigma_{n}$ the
collection of permutations $[n]\to[n]$. The study of forbidden intersection
theorems for permutations goes back to the paper of Frankl and Deza [15], in
which they studied the question of how big a family of permutations from
$\Sigma_{n}$ could be, if any two permutations $\sigma_{1},\sigma_{2}$ from
the family agree on at least $t$ points: satisfy $\sigma_{1}(x)=\sigma_{2}(x)$
for at least $t$ different $x\in[n]$. They showed that for $t=1$ the answer is
$(n-1)!$, and showed that for $t=2,3$ and $n$ of certain form the answer is
$(n-2)!$ and $(n-3)!$, respectively.111The reason behind the latter results is
the existence of certain multiply transitive permutation subgroups for certain
values of $n$, over which it is possible to do an averaging argument. It is
one of the reasons why the algebraic combinatorics community got interested in
the problem. They conjectured that the answer is $(n-t)!$ for $n\geqslant
n_{0}(t)$.222Frankl and Deza have also studied the dual question of extremal
families with no two permutation satisfying $\sigma_{1}(x)=\sigma_{2}(x)$ for
at least $t$ distinct $x\in[n]$ and established that the product of the two
extremal functions (permutations with intersection at least $t$ and at most
$t-1$) is at most $n!$. For each $i=0,\ldots,\lfloor\frac{n-t}{2}\rfloor$
consider the following collections of families

(1) $\displaystyle\mathfrak{A}_{k}=$
$\displaystyle\big{\\{}\sigma\mathcal{A}_{k}\tau\ :\
\sigma,\tau\in\Sigma_{n}\big{\\}},\text{ where}$
$\displaystyle\mathcal{A}_{k}:=$
$\displaystyle\big{\\{}\sigma\in\Sigma_{n}:\sigma(i)=i\text{ for at least
}t+k\text{ indices }i\in[t+2k]\big{\\}}.$

Clearly, for each $i$ each family from $\mathfrak{A}_{i}$ is $t$-intersecting.
The families from $\mathfrak{A}_{0}$ all have size $(n-t)!$ and thus provide a
tight example for the Frankl–Deza conjecture.

The question of Frankl and Deza has a long history. First, it was proved by
Cameron and Ku [5] and Larose and Malvenuto [33] that for $t=1$ the only
extremal examples are of the form (1). Generalizing it to arbitrary $t$,
Cameron conjectured that for $n\geqslant n_{0}(t)$ all extremal examples
belong to $\mathfrak{A}_{0}$. In 2011, Ellis, Friedgut and Pilpel [9] showed
that the conjectures of Frankl and Deza and of Cameron hold (with the
assumption $n>n_{0}(t)$). They made a far-reaching conjecture in the spirit of
the Complete $t$-Intersection Theorem for sets.

######  Conjecture 1.

For any $n,t$ the largest $t$-intersecting family of permutations must belong
to one of the collections $\mathfrak{A}_{k}$.

We should mention that a particular case of the conjecture was proved already
by Frankl and Deza [15] for $t$ being very close to $n$, i.e., for $n\geqslant
n_{0}(n-t)$. In that regime, they showed that the family
$\mathcal{A}_{\lfloor\frac{n-t}{2}\rfloor}$ is extremal. In particular,
comparing the sizes of $\mathcal{A}_{i}$ for different $i$, the conjecture
suggests that $\mathcal{A}_{0}$ must be the largest $t$-intersecting family of
permutations iff $n>2t$.333The size of any family in $\mathfrak{A}_{1}$ is
$(t+2)(n-t-1)!-(t+1)(n-t-2)!$. The value $(n-t)!$ is bigger iff
$(n-t-1)(n-2t-2)+(t+1)>0$. It has seen some great progress over the last
several years. First, Ellis and Lifshitz [11] showed that the conjectures of
Deza–Frankl, Cameron, and Ellis–Friedgut–Pilpel are valid for $t<c\frac{\log
n}{\log\log n}$. More recently, Zakharov and the author [32] managed to extend
the validity of to $n>Ct/\log^{2}t$ with some large $C$. Then Keller,
Lifshitz, Minzer and Sheinfield [28] extended it to $n>Ct$ with some large
$C$. In this paper, we prove these conjectures for $n>(1+\eta)t$ with
arbitrary $\eta>0$.

######  Theorem 1.

Let $\eta>0$ be some constant and $n,t$ be integers such that $n>(1+\eta)t$
and $n\geqslant n_{0}(\eta)$. If $\mathcal{F}\subset\Sigma_{n}$ is
$t$-intersecting then
$|\mathcal{F}|\leqslant\max_{k\in\mathbb{N}}|\mathcal{A}_{k}|$. Moreover, if
$\mathcal{F}$ is not fully contained in some $\mathcal{F}\in\mathfrak{A}_{k}$
then
$|\mathcal{F}|\leqslant(1-\frac{1}{e}+o(1))\max_{k\in\mathbb{N}}|\mathcal{A}_{k}|$.

Thus, this can be seen as the first Ahlswede-Khachatrian type result for
permutations, in which families from $\mathfrak{A}_{k}$ for all $k$
appear.444We note without a proof that for constant $k$ and $n\to\infty$ the
families $\mathfrak{A}_{k}$ are extremal in the interval
$t\in[t_{k},t_{k+1}]$, where $t_{k}=(1+o(1))\frac{k}{k+1}n$. Our theorem comes
with a stability version, which is in fact tight, that extends similar results
of [9] and [28]. Many of the forbidden intersection results have stability
versions: if a family has size close to extremal, then it has structure
resembling that of the extremal example. Classical stability results on the
EKR theorem are the Hilton–Milner theorem [24] and Frankl’s degree theorem
[14] (cf. also [31]). Stability results on the Ahlswede-Khachatrian theorem
include [2], [23]. Ellis, Keller and Lifshitz [10] managed to prove a
stability result for the Erdős–Sós problem.

Stability/structural results are often a way to get exact results. Once the
rough structure of all nearly-extremal examples is determined, it often can be
bootstrapped to obtain the extremal result. The classical Delta-system method,
developed by Frankl and Füredi [16, 17] is one example of such approach. More
recently, there was an impressive development of the methods coming from
Boolean Analysis, based on junta approximations and hypercontractivity. Using
juntas for the study of forbidden intersection problems started with the paper
of Dinur and Friedgut [6] and then was greatly developed in the recent works
of Ellis, Keller and Lifshitz [10, 11, 25]. Hypercontractivity and sharp
threshold results for the biased cube, as well as their applications to
different extremal combinatorics questions were studied in the recent paper by
Keevash, Lifshitz, Long and Minzer [26].

Another approach was suggested by Zakharov and the author [32]. It was
developed around the recent breakthrough by Alweiss, Lovett Wu and Zhang [3]
on the Erdős–Rado sunflower conjecture. The approach is purely combinatorial,
and, importantly, works with a large class of sufficiently quasirandom
structures, such as partitions and permutations, which were previously studied
mostly using algebraic techniques (Hoffman bounds combined with representation
theory for permutations). Later, Keller, Lifshitz, Minzer and Sheinfeld [27,
28] made a similar extension of the hypercontractivity approach.

We note that the authors of [28] also gave a two-family version of their
result. It is also possible within our framework, but we decided to write the
proofs for one family for conciseness.

##  2\. Proof of Theorem 1

Recall that $\Sigma_{n}$ is the set of permutations on $n$ elements. It will
be convenient to view $\Sigma_{n}$ as a family of sets. One way is to treat it
as an $n$-uniform subfamily in ${[n]^{2}\choose n}$ by identifying a
permutation $\sigma:[n]\to[n]$ with the set
$\\{(1,\sigma(1)),\ldots,(n,\sigma(n))\\}\in{[n]^{2}\choose n}$. We will
mostly use set terminology for permutations. We say that $S\subset[n]^{2}$ is
a partial permutation if $S\subset\sigma$ for a permutation
$\sigma\in\Sigma_{n}$. For any partial permutation $S$ we have
$|\Sigma_{n}(S)|=(n-|S|)!$. If $S$ is not a partial permutation then
$|\Sigma_{n}(S)|=0$. We denote by $\Sigma_{n}^{\leqslant q}$ the family of
partial permutations with $\leqslant q$ elements. We use the following
notation that is standard when working with families of sets. For sets
$X\subset Y$ and a family $\mathcal{S}$ we put

$\displaystyle\mathcal{F}(X):=$ $\displaystyle\ \\{F\setminus X:X\subset
F,F\in\mathcal{F}\\},$ $\displaystyle\mathcal{F}[X]:=$ $\displaystyle\
\\{F:X\subset F,F\in\mathcal{F}\\},$ $\displaystyle\mathcal{F}(X,Y):=$
$\displaystyle\ \\{F\setminus X:F\cap Y=X\\},$
$\displaystyle\mathcal{F}[\mathcal{S}]:=$ $\displaystyle\
\bigcup_{A\in\mathcal{S}}\mathcal{F}[A].$

###  2.1. Sketch of the proof.

The rough structure of the proof is described below. We introduce and use a
refinement of the spread approximation technique. Given the previous results,
say, from [32], we may for simplicity assume that $t\geqslant
n^{1-\epsilon/2}$ for $\epsilon=0.01\eta$. Let $\mathcal{F}$ be the largest
$t$-intersecting family of permutations.

First, we find a family $\mathcal{S}$ of partial permutations of size somewhat
smaller than $n$ (a concrete dependence is crucial here), such that it covers
most of the extremal family $\mathcal{F}$. At the same time, the family
$\mathcal{S}$ is $t^{\prime}$-intersecting for some $t^{\prime}$ that is a bit
smaller than $t$: $t^{\prime}=t-n^{1-\epsilon/2}$. In this part, we trade $t$
for $t^{\prime}$ in order to guarantee that the sets in $\mathcal{S}$ have a
relatively small uniformity.

Second, we use the ‘‘peeling’’ technique to analyze the structure of
$\mathcal{S}$. In this part, we use the condition on the uniformity of
$\mathcal{S}$ in order to guarantee that the main contribution to the size of
the family comes from partial permutations from $\mathcal{S}$ of size at most
$t+k$, where $k=n^{1-\epsilon}$. This, in turn, allows to get a subset $X$ of
size $t^{\prime}$, such that $\mathcal{F}(X)$ is rather dense in
$\Sigma_{n}(X)$ (much denser than the original family is in $\Sigma_{n}$).

Third, we employ a greedy procedure that at each step uses the set $X$ as
above, and manage to construct a much better spread approximation
$\mathcal{S}^{\prime}$ of the family. In particular, $\mathcal{S}^{\prime}$
only contains sets of size $t+O(n^{1-\epsilon})$ and is $t$-intersecting.

The last step is to apply and analyze the peeling procedure for the refined
approximation $\mathcal{S}^{\prime}$. Within the procedure, we detect the most
‘important’ layer and then show that this layer must be the only layer present
in $\mathcal{S}^{\prime}$ and thus in $\mathcal{F}$, assuming that
$\mathcal{F}$ is extremal. After some analysis, this allows us to discern the
structure isomorphic to $\mathcal{A}_{k}$ for some $k$.

###  2.2. Preliminaries

We say that a family $\mathcal{F}\subset 2^{[n]}$ is $r$-spread, if for any
$X\subset[n]$ we have $|\mathcal{F}(X)|\leqslant r^{-|X|}|\mathcal{F}|$. We
begin with some simple observations concerning the property of being
$r$-spread.

######  Observation 2.

If for some $\alpha>1$ we have a family
$\mathcal{F}\subset{[n]\choose\leqslant k}$ such that
$|\mathcal{F}|\geqslant\alpha^{k}$, then there is a set $X$ such that
$|\mathcal{F}(X)|>1$ and $\mathcal{F}(X)$ is $\alpha$-spread.

###### Proof.

if $\mathcal{F}$ is $\alpha$-spread then we are done. Otherwise, find an
inclusion-maximal set $X$ such that
$|\mathcal{F}(X)|>\alpha^{-|X|}|\mathcal{F}|$. Note that, by $|X|\leqslant k$
and $|\mathcal{F}|\geqslant\alpha^{k}$ we have $|\mathcal{F}(X)|>1$. We claim
that $\mathcal{F}(X)$ is $\alpha$-spread. Indeed, arguing indirectly, assume
that there is a nonempty set $Y$, $Y\cap X=\emptyset$, such that
$|\mathcal{F}(X\cup
Y)|>\alpha^{-|Y|}|\mathcal{F}(X)|>\alpha^{-|X|-|Y|}|\mathcal{F}|$. But then
$Y\cup X$ is a valid choice for $X$, which was supposed to be inclusion-
maximal. ∎

Arguing as in the proof of Observation 2, we get the following observation.

######  Observation 3.

Fix $\alpha>1$ and consider a family $\mathcal{F}$. If $X$ is an inclusion-
maximal set with the property that
$\mathcal{F}(X)\geqslant\alpha^{-|X|}|\mathcal{F}|$, then $\mathcal{F}(X)$ is
$\alpha$-spread.

We say that $W$ is a $p$-random subset of $[n]$ if each element of $[n]$ is
included in $W$ with probability $p$ and independently of others. The spread
approximation technique is based on the following theorem.

######  Theorem 4 ([3], a sharpening due to [37]).

If for some $n,k,r\geqslant 1$ a family
$\mathcal{F}\subset{[n]\choose\leqslant k}$ is $r$-spread and $W$ is an
$(\beta\delta)$-random subset of $[n]$, then

$\Pr[\exists F\in\mathcal{F}\ :\ F\subset W]\geqslant
1-\Big{(}\frac{5}{\log_{2}(r\delta)}\Big{)}^{\beta}k.$

In the remainder of this subsection, we will prove an estimate on the size of
$\mathcal{A}_{k}$. We will need the following inequality, valid for any
positive integers $n,x$.

(2)
$\frac{(n+x)!}{n!}=\prod_{i=n+1}^{n+x}i\geqslant\big{(}(n+x)!\big{)}^{\frac{x}{n+x}}\geqslant\Big{(}\Big{(}\frac{n+x}{e}\Big{)}^{n+x}\Big{)}^{\frac{x}{n+x}}=\Big{(}\frac{n+x}{e}\Big{)}^{x}.$

In what follows, we bound the sizes of $\mathcal{A}_{i}$. For an integer
$\ell\in[n]$, we say that a permutation $\sigma\in\Sigma_{n}$ is an
$\ell$-derangement, if $\sigma(i)\neq i$ for each $i\in[\ell]$.

######  Lemma 5.

For any $n,t,k$ we have $|\mathcal{A}_{k}|\leqslant{t+2k\choose k}(n-t-k)!$.
If $k=o(n-t-k)$ then we have $|\mathcal{A}_{k}|=(1+o(1)){t+2k\choose
k}(n-t-k)!$.

###### Proof.

Every permutation in $\mathcal{A}_{k}$ can be described by first choosing some
$(t+k)$-element subset of $[t+2k]$ that it fixes, and then defining it on the
remainder (that is, choosing a way how to permute the remaining $n-t-k$
elements). Therefore, $|\mathcal{A}_{k}|\leqslant{t+2k\choose k}(n-t-k)!$ for
any values of $n,t,k$.

Let us give a lower bound on $|\mathcal{A}_{k}|$ for $k=o(n-t-k)$. Clearly,
$|\mathcal{A}_{k}|$ is at least the number of permutations that fix exactly
$t+k$ elements on $[t+2k]$. For any fixed subset $S\in{[t+2k]\choose t+k}$,
the number of permutations that fix elements from $S$ and no other element of
$[t+2k]$ is the same as the number of $k$-derangements in $\Sigma_{n-t-k}$.
Using inclusion-exclusion formula, this number is

(3) $\sum_{i=0}^{k}(-1)^{i}{k\choose i}(n-t-k-i)!=(1+o(1))(n-t-k)!,$

where the equality uses the fact that $k=o(n-t-k)$. The collections of
permutations that fix exactly $S_{1}$, $S_{2}$ are disjoint for distinct
$S_{1},S_{2}\in{[t+2k]\choose t+k}$. Thus, we get that
$|\mathcal{A}_{k}|\geqslant(1+o(1)){t+2k\choose k}(n-t-k)!$. ∎

###  2.3. First spread approximation

We begin the proof of the main result by constructing the first, ‘rough’
spread approximation. In the next stage, we shall repeatedly apply this
theorem to $\mathcal{F}$ and some of its ‘dense’ subfamilies.

######  Theorem 6.

Let $n\geqslant 2$, $t\geqslant 1$ be some integers and fix a real number
$\epsilon\in(0,1/2)$, such that $n\geqslant(1+2\epsilon)t$ and $t\geqslant
n^{1-\epsilon/2}$. Suppose that $n\geqslant n_{0}(\epsilon)$. Consider a
family $\mathcal{F}\subset\Sigma_{n}$ that is $t$-intersecting. Put
$t^{\prime}=t-n^{1-\epsilon/2}$. Then there exist a $t^{\prime}$-intersecting
family $\mathcal{S}\subset\Sigma_{n}^{\leqslant(1+\epsilon)t}$ of partial
permutations of size at most $(1+\epsilon)t$ and a family
$\mathcal{F}^{\prime}$ such that the following holds.

  * (i)

$\mathcal{F}\setminus\mathcal{F}^{\prime}\subset\Sigma_{n}[\mathcal{S}]$;

  * (ii)

for any $B\in\mathcal{S}$ there is a family
$\mathcal{F}_{B}\subset\mathcal{F}$ such that $\mathcal{F}_{B}(B)$ is
$n^{\epsilon/2}$-spread;

  * (iii)

$|\mathcal{F}^{\prime}|\leqslant n^{-\frac{1}{5}\epsilon t}(n-t)!$.

###### Proof of Theorem 6.

We construct $\mathcal{S}$ as follows. Put $r:=n^{\epsilon/2}$ and consider
the following procedure for $i=1,\ldots$ with $\mathcal{F}^{1}:=\mathcal{F}$.

  1. (1)

Find a maximal $S_{i}$ that $|\mathcal{F}^{i}(S_{i})|\geqslant
r^{-|S_{i}|}|\mathcal{F}^{i}|$.

  2. (2)

If $|S_{i}|>(1+\epsilon)t$ or $\mathcal{F}^{i}=\emptyset$ then stop.
Otherwise, put
$\mathcal{F}^{i+1}:=\mathcal{F}^{i}\setminus\mathcal{F}^{i}[S_{i}]$.

Note that Observation 3 and maximality of $S_{i}$ imply that
$\mathcal{F}^{i}(S_{i})$ is $r$-spread. Let $N$ be the step of the procedure
for $\mathcal{F}$ at which we stop. The family $\mathcal{S}$ is defined as
follows: $\mathcal{S}:=\\{S_{1},\ldots,S_{N-1}\\}$. Clearly,
$|S_{i}|\leqslant(1+\epsilon)t$ for each $i\in[N-1]$. The family
$\mathcal{F}_{B}$ promised in (ii) is defined to be $\mathcal{F}^{i}[S_{i}]$
for $B=S_{i}$. Next, note that if $\mathcal{F}^{N}$ is non-empty, then

$\displaystyle|\mathcal{F}^{N}|\leqslant$ $\displaystyle\
r^{|S_{N}|}|\mathcal{F}^{N}(S_{N})|\leqslant r^{|S_{N}|}(n-|S_{N}|)!$
$\displaystyle\overset{\eqref{eqfac}}{\leqslant}$ $\displaystyle\
n^{\frac{1}{2}\epsilon|S_{N}|}\Big{(}\frac{n-t}{e}\Big{)}^{-(|S_{N}|-t)}(n-t)!$
$\displaystyle\leqslant$ $\displaystyle\
n^{\frac{1}{2}\epsilon|S_{N}|}\Big{(}\frac{2\epsilon
n}{e}\Big{)}^{-(|S_{N}|-t)}(n-t)!$ $\displaystyle\leqslant$ $\displaystyle\
n^{\frac{1}{2}\epsilon(1+\epsilon)t}\Big{(}\frac{2\epsilon
n}{e}\Big{)}^{-\epsilon t}(n-t)!$ $\displaystyle\leqslant$ $\displaystyle\
(2\epsilon/e)^{-\epsilon t}n^{-\frac{1}{4}\epsilon t}(n-t)!\leqslant
n^{-\frac{1}{5}\epsilon t}(n-t)!$

The inequality in the fourth line uses the fact that the expression in the
third line is a decreasing function of $|S_{N}|$, provided $2\epsilon
n\geqslant en^{\epsilon n/2}$, and that $|S_{N}|\geqslant(1+\epsilon)t$. We
put $\mathcal{F}^{\prime}:=\mathcal{F}^{N}$. Since either
$|S_{N}|>(1+\epsilon)t$ or $\mathcal{F}^{\prime}=\emptyset$, we have
$|\mathcal{F}^{\prime}|\leqslant n^{-\frac{1}{5}\epsilon t}(n-t)!$. We are
only left to verify that $\mathcal{S}$ is $t^{\prime}$-intersecting. We prove
it below.

######  Lemma 7.

The family $\mathcal{S}$ is $t^{\prime}$-intersecting.

###### Proof.

Take two (not necessarily distinct) $A_{1},A_{2}\in\mathcal{S}$ and assume
that $|A_{1}\cap A_{2}|<t^{\prime}$. Recall that the families
$\mathcal{F}_{A_{i}}(A_{i})$, $i=1,2$ are both $r$-spread with
$r=n^{\epsilon/2}$. For $i\in[2]$ put $j:=3-i$ and put

$\mathcal{G}_{i}:=\mathcal{F}_{A_{i}}(A_{i})\setminus\Big{\\{}F\in\mathcal{F}_{A_{i}}(A_{i}):|F\cap
A_{j}\setminus A_{i}|\geqslant\frac{n^{1-\epsilon/2}}{2}\Big{\\}}.$

The size of the latter family is at most

$\displaystyle{|A_{j}\setminus A_{i}|\choose
n^{1-\epsilon/2}/2}\max_{X:|X|=n^{1-\epsilon/2}/2,X\cap
A_{i}=\emptyset}|\mathcal{F}_{A_{i}}(A_{i}\cup X)|\leqslant$
$\displaystyle{n\choose
n^{1-\epsilon/2}/2}n^{-\frac{\epsilon}{2}n^{1-\epsilon/2}}|\mathcal{F}_{A_{i}}(A_{i})|\leqslant$
$\displaystyle(2en^{\epsilon/2})^{\frac{1}{2}n^{1-\epsilon/2}}n^{-\frac{\epsilon}{2}n^{1-\epsilon/2}}|\mathcal{F}_{A_{i}}(A_{i})|\leqslant$
$\displaystyle\ \frac{1}{2}|\mathcal{F}_{A_{i}}(A_{i})|.$

This implies that
$|\mathcal{G}_{i}|\geqslant\frac{1}{2}|\mathcal{F}_{A_{i}}(A_{i})|$. Because
of this and the trivial inclusion
$\mathcal{G}_{i}(Y)\subset\mathcal{F}_{A_{i}}(A_{i}\cup Y)$, valid for any
$Y$, we conclude that $\mathcal{G}_{i}$ is $\frac{r}{2}$-spread for both
$i\in[2]$. Since $n$ is sufficiently large, we have
$\frac{r}{2}>2^{11}\log_{2}(2n)$.

What follows is an application of Theorem 4. Let us put $\beta=\log_{2}(2n)$
and $\delta=(2\log_{2}(2n))^{-1}$. Note that $\beta\delta=\frac{1}{2}$ and
$\frac{r}{2}\delta>2^{10}$ by our choice of $r$. Theorem 4 implies that a
$\frac{1}{2}$-random subset $W_{i}$ of $[n]\setminus A_{i}$ contains a set
from $\mathcal{G}_{i}$ with probability strictly bigger than

$1-\Big{(}\frac{5}{\log_{2}2^{10}}\Big{)}^{\log_{2}(2n)}n=1-2^{-\log_{2}(2n)}n=\frac{1}{2}.$

Consider a random partition of $[n]\setminus(A_{1}\cup A_{2})$ into $2$ parts
$U_{1}^{\prime},U_{2}^{\prime}$, where $\Pr[x\in U_{i}^{\prime}]=1/2$
independently for each $i\in[2]$ and $x\in[n]\setminus(A_{1}\cup A_{2})$.
Next, for $i\in[2]$ and $j=3-i$, put $U_{i}:=U_{i}^{\prime}\cup(A_{j}\setminus
A_{i})$. Then $U_{i}$ is a random subset of the same ground set as $W_{i}$
above, moreover, the probability of containing each element is at least that
for $W_{i}$. It implies that there is $F_{i}\in\mathcal{G}_{i}$ such that
$F_{i}\subset U_{i}$ with probability strictly bigger than $\frac{1}{2}$.
Using the union bound, we conclude that, with positive probability, it holds
that there are such $F_{i}$, $F_{i}\subset U_{i},$ for both $i\in[2]$. Fix
such choices of $U_{i}$ and $F_{i}$, $i\in[2]$. Then, on the one hand, each
$F_{i}\cup A_{i}$ belongs to $\mathcal{F}$ and, on the other hand,
$|(F_{1}\cup A_{1})\cap(F_{2}\cup A_{2})|=|A_{1}\cap A_{2}|+|F_{1}\cap
A_{2}|+|F_{2}\cap A_{1}|<|A_{1}\cap A_{2}|+n^{1-\epsilon/2}<t$. The first
inequality follows from the definition of $\mathcal{G}_{i}$, and the second
inequality due to $|S_{1}\cap S_{2}|<t^{\prime}$ and the definition of
$t^{\prime}$. This is a contradiction with $\mathcal{F}$ being
$t$-intersecting. ∎

This concludes the proof of Theorem 6.∎

###  2.4. The peeling procedure and the structure of spread approximations for
large $t$-intersecting families

In this section, we analyze the ‘peeling’ procedure that captures the
structure of the $t$-intersecting families of partial permutations. One of the
key objectives is to control the number of permutations coming from higher
uniformity partial permutations.

We say that a $t$-intersecting family $\mathcal{T}$ is maximal if for any
$T\in\mathcal{T}$ and any proper subset $X\subsetneq T$ there exist
$T^{\prime}\in\mathcal{T}$ such that $|T\cap T^{\prime}|<t$ and, moreover,
$T_{1}\not\subset T_{2}$ for $T_{1},T_{2}\in\mathcal{T}$ (i.e., $\mathcal{T}$
is an antichain).

######  Observation 8.

For any positive integers $n,p$ and a $t$-intersecting family
$\mathcal{S}\subset\Sigma^{\leqslant q}_{n}$, there exists a maximal
$t$-intersecting family $\mathcal{T}$ such that for every $T\in\mathcal{T}$
there is $S\in\mathcal{S}$ such that $T\subseteq S$. Consequently, for any
family $\mathcal{F}\subset\Sigma_{n}$ we have
$\mathcal{F}[\mathcal{S}]\subset\mathcal{F}[\mathcal{T}]$.

The easiest way to see it is to construct $\mathcal{T}$ by repeatedly
replacing sets in $\mathcal{S}$ by their proper subsets while preserving the
$t$-intersecting property.

Consider a $t$-intersecting family $\mathcal{S}\subset\Sigma^{\leqslant
q}_{n}$. Let us iteratively define the following series of families.

  1. (1)

Put $\mathcal{T}_{q-t}=\mathcal{S}$.

  2. (2)

For $k=q-t,q-t-1,\ldots,0$ we put
$\mathcal{W}_{k}=\mathcal{T}_{k}\cap{[n]\choose t+k}$ and let
$\mathcal{T}_{k-1}$ be the family given by Observation 8 when applied to
$\mathcal{T}_{k}\setminus\mathcal{W}_{k}$ playing the role of $\mathcal{S}$.

Thus, we ‘peel’ the sets of the largest uniformity in $\mathcal{T}_{k}$ and
replace the resulting family by a maximal $t$-intersecting family using
Observation 8. Remark that $\mathcal{T}_{k}$ is $t$-intersecting for each
$k=q-t,q-t-1\ldots,0$ by definition. We summarize the basic properties of
these series of families in the following lemma.

######  Lemma 9.

The following properties hold for each $k=q-t,q-t-1\ldots,0$.

  * (i)

All sets in $\mathcal{T}_{k}$ have size at most $t+k$.

  * (ii)

For $k\leqslant q-t-1$ we have
$\mathcal{A}[\mathcal{T}_{k+1}]\subset\mathcal{A}[\mathcal{T}_{k}]\cup\mathcal{A}[\mathcal{W}_{k+1}]$.

  * (iii)

There is no set $X$ of size $\leqslant t+k-1$ such that $\mathcal{W}_{k}(X)$
(or any subfamily of $\mathcal{T}_{k}(X)$) is $\alpha$-spread for $\alpha>k$.

###### Proof.

(i) This easily follows by reverse induction on $k$. The base case is that all
sets in $\mathcal{S}$ have size at most $q$, and the induction step is via the
definition of $\mathcal{T}_{k-1}$.

(ii) We have
$\mathcal{A}[\mathcal{T}_{k+1}]=\mathcal{A}[\mathcal{T}_{k+1}\setminus\mathcal{W}_{k+1}]\cup\mathcal{A}[\mathcal{W}_{k+1}]$
and, by the definition of $\mathcal{T}_{k}$, we have
$\mathcal{A}[\mathcal{T}_{k}]\supset\mathcal{A}[\mathcal{T}_{k+1}\setminus\mathcal{W}_{k+1}]$.

(iii) Assume that there is such a set $X$. By the maximality of
$\mathcal{T}_{k}$, there must be a set $F\in\mathcal{T}_{k}$ such that $|X\cap
F|=z<t$. At the same time, the family $\mathcal{T}_{k}$ is $t$-intersecting.
So, for each set $G\in\mathcal{W}_{k}[X]$ we have $|G\cap F|\geqslant t$, and
thus $|F\cap(G\setminus X)|\geqslant t-z$ for each such $G$. Thus,
$\mathcal{W}_{k}[X]\subset\cup_{S\in{F\choose t-z}}\mathcal{W}_{k}[X\cup S]$
and so, using the $\alpha$-spreadness of $\mathcal{W}_{k}(X)$, we get

$\displaystyle|\mathcal{W}_{k}(X)|\leqslant$ $\displaystyle\ {|F|-z\choose
t-z}\max_{F^{\prime}\in{F\choose t-z}}|\mathcal{W}_{k}(X\cup F^{\prime})|$
$\displaystyle\leqslant$ $\displaystyle\ {|F|-z\choose
t-z}\alpha^{-(t-z)}|\mathcal{W}_{k}(X)|$ $\displaystyle=$ $\displaystyle\
\prod_{i=1}^{t-z}\frac{|F|-t+i}{i}\alpha^{-(t-z)}|\mathcal{W}_{k}(X)|$
$\displaystyle\leqslant$ $\displaystyle\
(|F|-t+1)^{t-z}\alpha^{-(t-z)}|\mathcal{W}_{k}(X)|<|\mathcal{W}_{k}(X)|,$

where the last inequality is due to $|F|-t+1\leqslant k<\alpha$. This a
contradiction. ∎

Our next goal is to bound the size of $\mathcal{W}_{k}$. Consider two sets
$A,B\in\mathcal{T}_{k}$ such that $A\cap B=I$, $|I|=t$. (There are such sets
by maximality of $\mathcal{T}_{k}$.) Recall that the sizes of sets of $A,B$
are at most $t+k$. Any set $C\in\mathcal{W}_{k}$ intersects both $A$ and $B$
in at least $t$ elements. Denote $C_{0}=C\cap I$, $C_{1}=C\cap(A\setminus I)$
and $C_{2}=C\cap(B\setminus I)$. Then, putting $|C_{0}|=t-j$, we must have
$|C_{1}|,|C_{2}|\geqslant j$. Select $C_{1}^{\prime}\subset
C_{1},C_{2}^{\prime}\subset C_{2}$ such that
$|C_{1}^{\prime}|=|C_{2}^{\prime}|=j$. The family $\mathcal{W}_{k}(C_{0}\cup
C_{1}^{\prime}\cup C_{2}^{\prime}\cup X)$ by Lemma 9 (iii) is not
$\alpha$-spread subfamily for $\alpha>k$ and any $X$, and thus
$|\mathcal{W}_{i}(C_{0}\cup C_{1}^{\prime}\cup C_{2}^{\prime})|\leqslant
k^{k-j}$ by Observation 2. From here, we see that we can upper bound the
number of sets in $\mathcal{W}_{k}$ as follows:

$|\mathcal{W}_{k}|\leqslant\sum_{j=0}^{k}{t\choose t-j}{|A|-t\choose
j}{|B|-t\choose j}k^{k-j}\leqslant\sum_{j=0}^{k}f(j),$

where

(4) $f(j):={t\choose t-j}{k\choose j}^{2}k^{k-j}.$

Note that

$\frac{f(j)}{f(j+1)}=\frac{j+1}{t-j}\Big{(}\frac{j+1}{k-j}\Big{)}^{2}k=\frac{(j+1)^{3}k}{(t-j)(k-j)^{2}}.$

The observation below is based on simple calculations that check whether the
last ratio above is bigger than $1$ or not.

######  Observation 10.

For sufficiently large $t$, $t\geqslant k$, we have the following. Denote by
$j_{0}$ the value at which $f(j)$ attains its maximum.

  1. (1)

For $k$ such that $t=o(k^{2})$, we have $j_{0}=(1+o(1))(tk)^{1/3}$.

  2. (2)

For $k=\Theta(\sqrt{t})$, we have $j_{0},k-j_{0}=\Theta(k)$.

  3. (3)

For $k=o(\sqrt{t})$ we have $k-j_{0}=o(k)$.

  4. (4)

For $k=o(t^{1/4})$, we have $j_{0}=k$.

Moreover, $|\mathcal{W}_{i}|\leqslant(k+1)f(j_{0})$ in general and
$|\mathcal{W}_{i}|\leqslant(1+o(1))f(k)=(1+o(1)){t\choose t-k}$ for
$k=o(t^{1/4})$.

We will need the following concrete statement concerning the size of
$\Sigma_{n}[\mathcal{W}_{k}].$

######  Lemma 11.

For any $\epsilon>0$, $n\geqslant(1+100\epsilon)t$, $t>t_{0}(\epsilon)$ and
$t^{0.01}\leqslant k\leqslant 2\epsilon t$ we have

(5) $\frac{|\mathcal{W}_{k}|(n-t-k)!}{(n-t)!}\leqslant 2^{-k}.$

###### Proof.

Using (4) and the inequality ${m\choose\ell}\leqslant(em/\ell)^{\ell}$, we get

(6) $f(j)\leqslant\Big{(}\frac{e^{3}tk^{2}}{j^{3}}\Big{)}^{j}k^{k-j}.$

Let us first consider the case when $k\geqslant t^{0.99}$. Then we can apply
Observation 10 (1) and get that the fraction in (6) for $f(j_{0})$ is
simplified to $((1+o(1))e^{3}k)^{j_{0}}$. We thus get

$\displaystyle\frac{|\mathcal{W}_{k}|(n-t-k)!}{(n-t)!}\leqslant$
$\displaystyle(k+1)\frac{f(j_{0})(n-t-k)!}{(n-t)!}$ $\displaystyle\leqslant$
$\displaystyle\frac{((1+o(1))e^{3}k)^{j_{0}}k^{k-j_{0}+1}}{(n-t-k)^{k}}\leqslant\frac{((1+o(1))e^{3}k)^{k}}{(n-t-k)^{k}}\leqslant\
2^{-k},$

where the last inequality is due to $n-t-k\geqslant 98\epsilon t\geqslant
49k>2.1e^{3}k$.

Next, assume that $t^{0.01}\leqslant k\leqslant t^{0.99}$. In this regime,
according to Observation 10, we have
$tk^{2}/j_{0}^{3}\leqslant(1+o(1))t^{0.99}$, and thus we can conclude that (6)
implies the following inequality.

$f(j)\leqslant(Ct^{0.99})^{k},$

where $C$ is some absolute constant. In this regime, we can conclude the
following.

$\displaystyle\frac{|\mathcal{W}_{k}|(n-t-k)!}{(n-t)!}\leqslant$
$\displaystyle(k+1)\frac{f(j_{0})(n-t-k)!}{(n-t)!}$ $\displaystyle\leqslant$
$\displaystyle\frac{(k+1)(Ct^{0.99})^{k}}{(n-t-k)^{k}}\leqslant\ 2^{-k},$

where in the last inequality we use that $n-t-k\geqslant\epsilon t$ and the
fact that $t>t_{0}(\epsilon)$. ∎

###  2.5. Finding a dense piece of $\mathcal{F}$ and a sharper spread
approximation

We return to the notation used in Theorem 6. The following theorem makes use
of the peeling procedure and allows us to find a partial permutation $X$ such
that the family $\mathcal{F}(X)$ is much denser in $\Sigma_{n}(X)$ than
$\mathcal{F}$ in $\Sigma_{n}$.

######  Theorem 12.

Assume that $\epsilon\in(0,1/2)$ and $n,t$ are positive integers such that
$n>(1+100\epsilon)t$ and $n>n_{0}(\epsilon)$, $t\geqslant 2n^{1-\epsilon/2}$.
Suppose that $\mathcal{F}\subset\Sigma_{n}$ is $t$-intersecting and satisfies
$|\mathcal{F}|\geqslant 2^{2-x}(n-t^{\prime})!$ for some integer $x$,
$t^{0.01}<x\leqslant\frac{1}{5}\epsilon t$ , and where
$t^{\prime}=t-n^{1-\epsilon/2}$. Then there is a subset $X$ of size
$t^{\prime}$ such that
$|\mathcal{F}[X]|\geqslant\frac{1}{2}{t^{\prime}+x\choose
t^{\prime}}^{-1}|\mathcal{F}|$.

###### Proof of Theorem 12.

Take a family $\mathcal{F}$ as in the statement. First, we use Theorem 6 to
get a spread approximation $\mathcal{S}$ of sets of size at most
$q=(1+\epsilon)t$, such that $\mathcal{S}$ is $t^{\prime}$-intersecting, and a
remainder $\mathcal{F}^{\prime}$, $|\mathcal{F}^{\prime}|\leqslant
n^{-\frac{1}{5}\epsilon t}(n-t)!$, that satisfy
$\mathcal{F}\setminus\mathcal{F}^{\prime}\subset\Sigma_{n}[\mathcal{S}]$. (It
is easy to see that all requirements of Theorem 6 are met.)

Next, we apply the peeling procedure from Section 2.4 to $\mathcal{S}$ with
$t^{\prime}$ playing the role of $t$, obtaining a sequence of families
$\mathcal{W}_{k}$. We want to bound the contribution of
$|\mathcal{F}[\mathcal{W}_{k}]|$ with large $k$ to $|\mathcal{F}|$. To this
end, we apply Lemma 11 with $t^{\prime}$ playing the role of $t$ for each
$k=x+1,\ldots,q-t^{\prime}=\epsilon t+(t-t^{\prime})$. Note that all
conditions are satisfied, most importantly, $k\leqslant\epsilon
t+(t-t^{\prime})\leqslant 2\epsilon t$. Then (5) implies the following bound
on the contribution of layers $\mathcal{W}_{k}$ to $|\mathcal{F}|$ for
$k\geqslant x+1$.

$\sum_{k=x+1}^{q-t^{\prime}}|\mathcal{F}[\mathcal{W}_{k}]|\leqslant\sum_{k=x+1}^{q-t^{\prime}}|\Sigma_{n}[\mathcal{W}_{k}]|\leqslant(n-t^{\prime})!\sum_{k=x+1}^{q-t^{\prime}}\frac{|\mathcal{W}_{k}|(n-t^{\prime}-k)!}{(n-t^{\prime})!}\leqslant$
$(n-t^{\prime})!\sum_{k=x+1}^{q-t^{\prime}}2^{-k}\leqslant(n-t^{\prime})!\cdot
2^{-x}.$

Put
$\mathcal{F}^{\prime\prime}=(\mathcal{F}\setminus\mathcal{F}^{\prime})\cap\Sigma_{n}[\mathcal{T}_{t^{\prime}+x}]$.
(In words, we removed from $\mathcal{F}$ the remainder $\mathcal{F}^{\prime}$
and ‘peeled off’ the layers $\mathcal{W}_{k}$ of uniformity at least
$t^{\prime}+x+1$.) We have $|\mathcal{F}|>4(n-t^{\prime})!\cdot 2^{-x}$, and
thus
$|\mathcal{F}\setminus\mathcal{F}^{\prime}|\geqslant\frac{3}{4}|\mathcal{F}|$
and $|\mathcal{F}^{\prime\prime}|\geqslant\frac{1}{2}|\mathcal{F}|$. Take any
set $F\in\mathcal{T}_{t^{\prime}+x}$. Via averaging, there is a
$t^{\prime}$-element subset $X\subset F$, such that
$|\mathcal{F}^{\prime\prime}(X)|\geqslant{t^{\prime}+x\choose
t^{\prime}}^{-1}|\mathcal{F}^{\prime\prime}|\geqslant\frac{1}{2}{t^{\prime}+x\choose
t^{\prime}}^{-1}|\mathcal{F}|$. ∎

The following corollary shall be the building block for a better spread
approximation result.

######  Corollary 13.

Assume that $\epsilon\in(0,1/2)$ and $n,t$ are positive integers such that
$n>(1+100\epsilon)t$, $n>n_{0}(\epsilon)$, and $t\geqslant 2n^{1-\epsilon/2}$.
Suppose that $\mathcal{F}\subset\Sigma_{n}$ is $t$-intersecting and satisfies
$|\mathcal{F}|\geqslant(n-t)!\cdot 2^{-\frac{1}{2}n^{1-\epsilon/4}}$. Then
there is a set $X$, $|X|\leqslant t+n^{1-\epsilon/6}$, such that
$\mathcal{F}(X)$ is $10\epsilon t$-spread.

###### Proof.

We apply Theorem 12 with $x=n^{1-\epsilon/4}$. Then

$4(n-t^{\prime})!\cdot 2^{-x}\leqslant(n-t)!\cdot
4n^{n^{1-\epsilon/2}}2^{-n^{1-\epsilon/4}}\leqslant(n-t)!\cdot
2^{-\frac{1}{2}n^{1-\epsilon/4}},$

and the condition on $|\mathcal{F}|$ in Theorem 12 is implied by
$|\mathcal{F}|\geqslant(n-t)!\cdot 2^{-\frac{1}{2}n^{1-\epsilon/4}}$. Theorem
12 gives us a $t^{\prime}$-element set $X$, such that

$|\mathcal{F}(X)|\geqslant\frac{1}{2}{t^{\prime}+x\choose
x}^{-1}|\mathcal{F}|\geqslant n^{-x}|\mathcal{F}|\geqslant(n-t^{\prime})!\cdot
2^{-x}n^{-x}\geqslant(n-t^{\prime})!\cdot 2^{-n^{1-\epsilon/5}}.$

We claim that there is a set $Y$ satisfying $|Y|\leqslant
t^{\prime}+n^{1-\epsilon/6}$ and $X\subset Y$, such that, moreover,
$\mathcal{F}(Y)$ is $10\epsilon t$-spread. Indeed, find a maximum set $Y$,
$Y\supset X$, that violates the $10\epsilon t$-spreadness of $\mathcal{F}(X)$.
If $|Y|>t^{\prime}+n^{1-\epsilon/6}$, then, using (2),

$|\mathcal{F}(X)|\leqslant(10\epsilon
t)^{|Y|-t^{\prime}}(n-|Y|)!\overset{\eqref{eqfac}}{\leqslant}(10\epsilon
t)^{|Y|-t^{\prime}}\Big{(}\frac{n-t^{\prime}}{e}\Big{)}^{|Y|-t^{\prime}}(n-t^{\prime})!\leqslant$
$2^{-|Y|+t^{\prime}}(n-t^{\prime})!<2^{-n^{1-\epsilon/6}}(n-t^{\prime})!<|\mathcal{F}(X)|,$

which is a contradiction. Here in the third inequality we used
$n-t^{\prime}\geqslant 100\epsilon t$. ∎

Using this corollary, we can get a much better spread approximation of our
family.

######  Theorem 14.

Let $n\geqslant 2$, $t\geqslant 1$ be some integers and fix a real number
$\epsilon\in(0,1/2)$, such that $n>n_{0}(\epsilon)$, $n>(1+100\epsilon)t$,
$t\geqslant 2n^{1-\epsilon/2}$. Consider a family
$\mathcal{F}\subset\Sigma_{n}$ that is $t$-intersecting. Then there exist a
$t$-intersecting family $\mathcal{S}\subset\Sigma_{n}^{\leqslant
t+n^{1-\epsilon/6}}$ of partial permutations of size at most
$t+n^{1-\epsilon/6}$ and a family $\mathcal{F}^{\prime}\subset\mathcal{F}$
such that the following holds.

  * (i)

$\mathcal{F}\setminus\mathcal{F}^{\prime}\subset\Sigma_{n}[\mathcal{S}]$;

  * (ii)

for any $B\in\mathcal{S}$ there is a family
$\mathcal{F}_{B}\subset\mathcal{F}$ such that $\mathcal{F}_{B}(B)$ is
$10\epsilon t$-spread;

  * (iii)

$|\mathcal{F}^{\prime}|\leqslant 2^{-\frac{1}{2}n^{1-\epsilon/4}}(n-t)!$.

###### Proof of Theorem 14.

We iteratively apply Corollary 13. We put $\mathcal{F}_{0}:=\mathcal{F}$, and
at the $i$-th step we get a set $Y$ and a family $\mathcal{F}_{i}[Y]$. We then
put $\mathcal{F}_{i+1}:=\mathcal{F}_{i}\setminus\mathcal{F}_{i}[Y]$ and apply
Corollary 13 to $\mathcal{F}_{i+1}$ as long as the corollary is applicable,
that is, until step $N$ when $|\mathcal{F}_{N}|\leqslant(n-t)!\cdot
2^{-\frac{1}{2}n^{1-\epsilon/4}}$ for some $N$. We then put
$\mathcal{F}^{\prime}:=\mathcal{F}_{N}$. The collection of $Y$’s accumulated
while running the procedure is our family $\mathcal{S}$, and we put
$\mathcal{F}_{Y}[Y]$ to be the corresponding family $\mathcal{F}_{i}[Y]$.

The only property that we are left to verify is that $\mathcal{S}$ is
$t$-intersecting. This is done in a way that is very similar to the proof of
Lemma 7, and we sketch it below. Arguing indirectly, take
$A_{1},A_{2}\in\mathcal{S}$ that are not $t$-intersecting and, putting
$x:=t-|A_{1}\cap A_{2}|$, for each $i\in[2]$ and $j=3-i$ define

$\mathcal{G}_{i}:=\mathcal{F}_{A_{i}}(A_{i})\setminus\Big{\\{}F\in\mathcal{F}_{A_{i}}(A_{i}):|F\cap
A_{j}\setminus A_{i}|\geqslant x\Big{\\}}.$

Using the bound on $|A_{i}|$ and the spreadness of
$\mathcal{F}_{A_{i}}(A_{i})$, the size of the subtracted family is at most

$\displaystyle{|A_{j}\setminus A_{i}|\choose x}\max_{X:|X|=x,X\cap
A_{i}=\emptyset}|\mathcal{F}_{A_{i}}(A_{i}\cup X)|\leqslant$
$\displaystyle{n^{1-\epsilon/6}+x\choose x}(10\epsilon
t)^{-x}|\mathcal{F}_{A_{i}}(A_{i})|\leqslant$
$\displaystyle(n^{1-\epsilon/6}+1)^{x}(10\epsilon
t)^{-x}|\mathcal{F}_{A_{i}}(A_{i})|\leqslant$ $\displaystyle\
\frac{1}{2}|\mathcal{F}_{A_{i}}(A_{i})|.$

We conclude that
$|\mathcal{G}_{i}|\geqslant\frac{1}{2}|\mathcal{F}_{A_{i}}(A_{i})|$ and,
consequently, that $\mathcal{G}_{i}$ is $5\epsilon t$-spread for both
$i\in[2]$. Since $n$ is sufficiently large and $t>2n^{1-\epsilon/2}$, we have
$5\epsilon t>2^{11}\log_{2}(2n)$, and we can apply the coloring argument,
finding two disjoint sets $U_{1},U_{2}$, where $U_{i}\in\mathcal{G}_{i}$. Then
$U_{i}\cup A_{i}$ violate the $t$-intersection property of $\mathcal{F}$. ∎

###  2.6. Proof of Theorem 1

Fix $\eta>0$ and consider a family $\mathcal{F}\subset\Sigma_{n}$ of
permutations that is $t$-intersecting and that has size at least half of the
largest such family. If $t<2n^{1-0.005\eta}$ then we are done by the result of
[32], so we assume that the opposite inequality holds.555We could have
incorporated this case into the framework of this paper, but decided to omit
it to reduce technicalities. Apply Theorem 14 with $\epsilon=0.01\eta$,
getting a family $\mathcal{S}$ of sets of size at most $q:=t+n^{1-\epsilon/6}$
and a small remainder $\mathcal{F}^{\prime}\subset\mathcal{F}$. (We note that
the conditions on $t$ and $n$ for such choice of $\epsilon$ are implied by the
condition on $n$ in Theorem 1 and our assumption on $t$ above.) Next, apply
the peeling procedure to $\mathcal{S}$. Fix $k$ to be the largest value such
that, first, $k\leqslant t^{0.01}$ and, second, $|\mathcal{W}_{k}|\geqslant
t^{-0.5}{t\choose k}$. We stop the peeling procedure at $k$ and shall show
that most of the family $\mathcal{F}$ is contained in
$\Sigma_{n}[\mathcal{W}_{k}]$. Recall that
$|\Sigma_{n}(\mathcal{W}_{k})|\leqslant|\mathcal{W}_{k}|(n-t-k)!$.

First, we note that, by (5), as in the proof of Theorem 12, we have

(7)
$\sum_{x=t^{0.01}+1}^{q-t}|\Sigma_{n}(\mathcal{W}_{x})|\leqslant\sum_{x=t^{0.01}+1}^{q-t}2^{-x}(n-t)!\leqslant
2^{-t^{0.01}}(n-t)!.$

Second, using the inequality on $|\mathcal{W}_{x}|$ for $x>k$ and Lemma 5, we
have

$\displaystyle\sum_{x=k+1}^{t^{0.01}}|\Sigma_{n}(\mathcal{W}_{x})|\leqslant$
$\displaystyle\sum_{x=k+1}^{t^{0.01}}\frac{|\mathcal{W}_{k}|(n-t-k)!}{(1+o(1)){t+2k\choose
k}(n-t-k)!}|\mathcal{A}_{x}|$ (8) $\displaystyle\leqslant$
$\displaystyle\sum_{x=k+1}^{t^{0.01}}(1+o(1))t^{-0.5}|\mathcal{A}_{x}|\leqslant
t^{-0.4}\max_{x}|\mathcal{A}_{x}|.$

For the subsequent analysis, we need to better understand the structure of
$\mathcal{W}_{k}$. Looking at the formula (4) and the displayed equation above
it, it should be clear that, (assuming $k<t^{0.01}$) for every $j\leqslant
k-1$ we have $f(j)=o\big{(}t^{-0.9}f(k)\big{)}=o\big{(}t^{-0.9}{t\choose
t-k}\big{)}$. Moreover, if any two sets in $\mathcal{W}_{k}$ intersect in at
least $t+1$ elements, then we can do the same analysis and calculations as the
one that preceded (4), but with $A,B\in\mathcal{W}_{k}$ and with $I$ of size
at least $t+1$ and $C$ intersecting $A,B$ in at least $t+1$ elements, and get
a bound $|\mathcal{W}_{k}|=o\big{(}t^{-0.9}{t\choose t-k}\big{)}$. Thus, we
conclude that, first, we have two sets $A,B\in\mathcal{W}_{k}$ such that
$|A\cap B|=t$, and, moreover, by Observation 10, most of the sets from
$\mathcal{W}_{k}$ must intersect $U_{0}=A\cap B$ in exactly $t-k$ elements and
thus contain $A\Delta B$. Let us fix one such set $C$ and put $I=A\cap B\cap
C$. Let $I^{\prime}$ stand for the set of elements that belong to exactly two
out of $A,B,C$. That is, $A\cup B\cup C=I\sqcup I^{\prime}$.

We are ready to complement (7), (8) with the analysis of the sizes of layers
below $k$. Put $\mathcal{G}_{j}:=\mathcal{T}_{k}\cap{[n]^{2}\choose t+j}$ for
$0\leqslant j<k$. First and foremost, let us bound the size of the
intersection of $G\in\mathcal{G}_{j}$ with $I$. The set $G$ intersects each of
$A,B,C$ in at least $t$ elements, thus $3t$ elements in total (with
multiplicities). By double-counting, knowing that elements in $I$ have
multiplicity $3$ and the elements in $I^{\prime}$ have multiplicity $2$, we
must have

$|G|\geqslant|G\cap I|+|G\cap I^{\prime}|\geqslant|G\cap
I|+\Big{\lceil}\frac{3}{2}(t-|G\cap
I|)\Big{\rceil}=t+\Big{\lceil}\frac{1}{2}(t-|G\cap I|)\Big{\rceil}.$

We have $|G|=t+j$, and thus $t-|G\cap I|\leqslant 2j$. In other words, $|G\cap
I|\geqslant t-2j=|I|+k-2j$. From here, we can conclude that

$|\mathcal{G}_{j}|\leqslant\sum_{m=t-2j}^{t-k}{t-k\choose
m}{3k\choose\big{\lceil}\frac{3}{2}(t-m)\big{\rceil}}k^{j-\lceil(t-m)/2\rceil},$

where the inequality is due to Lemma 9 (iii) that states that a subfamily of
$\mathcal{T}_{k}(X)$ cannot be $>k$-spread for a set $X$ of size at most
$t+j-1$ (applied for $\mathcal{G}_{j}(X)$), and Observation 2. Since
$k\leqslant t^{0.01}$, it is easy to see666Doing the same analysis as after
(4) that the maximum in the sum above is attained when $m=t-2j$, and,
moreover, the following holds

$|\mathcal{G}_{j}|\leqslant(1+o(1)){t-k\choose t-2j}{3k\choose
3j}k^{j-\lceil(t-(t-2j))/2\rceil}=(1+o(1)){t-k\choose t-2j}{3k\choose 3j}.$

It is a straightforward calculation to see that for any $0\leqslant j<k$

${t-k\choose t-2j}{3k\choose 3j}\leqslant\frac{k^{4}}{t}{t\choose
t-j}=o\Big{(}t^{-0.9}{t\choose t-j}\Big{)}.$

From here, using Lemma 5, we conclude that for each $j=0,\ldots,k-1$ we have

$|\Sigma_{n}[\mathcal{G}_{j}]|\leqslant(1+o(1)){t-k\choose t-2j}{3k\choose
3j}(n-t-j)!\leqslant t^{-0.9}|\mathcal{A}_{j}|,$

and thus

(9)
$|\Sigma_{n}[\mathcal{T}_{k}\setminus\mathcal{W}_{k}]|\leqslant\sum_{j=0}^{k-1}|\Sigma_{n}[\mathcal{G}_{j}]|\leqslant
t^{-0.9}\sum_{j=0}^{t^{0.01}}|\mathcal{A}_{j}|\leqslant
t^{-0.8}\max_{j}|\mathcal{A}_{j}|.$

From inequalities (7),(8) and (9), together with the bound on
$|\mathcal{F}^{\prime}|$ that is given by the application of Theorem 14, we
conclude that, as long as
$|\mathcal{F}|\geqslant\frac{1}{2}\max_{x}|\mathcal{A}_{x}|$, all but an
$o(1)$-fraction of all sets in $\mathcal{F}$ are contained in
$\Sigma_{n}(\mathcal{W}_{k})$. Using the last conclusion of Observation 10,
all but a $o(1)$-fraction of the sets in $\mathcal{W}_{k}$, are contained in
the union $A\cup B$, where $A,B\in\mathcal{W}_{k}$ and $|A\cap B|=t$. (cf. the
paragraph after (8)) That is, they belong to ${A\cup B\choose t+k}$, where
$|A\cup B|=t+2k$. In other words, up to isomorphism, all but a $o(1)$-fraction
of the sets in $\mathcal{F}$ belong to $\mathcal{A}_{k}$.

The last step is to show that $\mathcal{F}$ must be contained in
$\mathcal{A}_{k}$. Assume that there is a permutation $\sigma\in\mathcal{F}$
such that $|\sigma\cap(A\cup B)|\leqslant t+k-1$. Consider the family of
partial permutations $\mathcal{G}:=\\{F\in{A\cup B\choose
t+k}:|F\cap\sigma|\leqslant t-1\\}$ and $\mathcal{H}:={A\cup B\choose
t+k}\setminus\mathcal{G}$.

First, we note that $|\mathcal{G}|\geqslant{t+k-1\choose
k}=(1+O(t^{-0.9})){t+2k\choose k},$ since $k\leqslant t^{0.01}$. We of course
have $|\mathcal{H}|=O(t^{-0.9}){t+2k\choose k}$. From here, it should be clear
that
$|\mathcal{F}|=(1+o(1))|\mathcal{F}[\mathcal{G}]|\leqslant(1+o(1))\sum_{X\in\mathcal{G}}|\mathcal{F}(X)|$.
Let us bound $|\mathcal{F}(X)|$ for each specific $X$. Apply a suitable
isomorphism that maps $X$ to a partial permutation $\pi$: $\pi(i)=i$ for each
$i=n-t-k+1,\ldots,n$. Then $\sigma$ induces a certain partial permutation
$\sigma^{\prime}$ on $[n-t-k]$, and any $\sigma^{\prime}$-derangement (that
is, any permutation that does not intersect $\sigma^{\prime}$) on $[n-t-k]$
cannot appear in $\mathcal{F}(X)$. The number of partial derangements is at
least the number of derangements, which is at least $\frac{1}{e}(n-t-k)!$.
Therefore,
$|\mathcal{F}(X)|\leqslant\big{(}1-\frac{1}{e}\big{)}|\Sigma_{n}(X)|$, and
thus

$|\mathcal{F}|\sim|\mathcal{F}[\mathcal{G}]|\leqslant\sum_{X\in\mathcal{G}}|\mathcal{F}(X)|\leqslant\sum_{X\in\mathcal{G}}\big{(}1-\frac{1}{e}\big{)}|\Sigma_{n}(X)|\sim\big{(}1-\frac{1}{e}\big{)}|\mathcal{A}_{k}|,$

where the last asymptotic equality is due to the asymptotic of $|\mathcal{G}|$
and Lemma 5. We conclude that
$|\mathcal{F}|\leqslant\big{(}1-\frac{1}{e}+o(1)\big{)}|\mathcal{A}_{k}|$,
unless $\mathcal{F}$ is contained in $\mathcal{A}_{k}$. This completes the
proof of the theorem.

## References

  * [1] R. Ahlswede and L.H. Khachatrian, The Complete Intersection Theorem for Systems of Finite Sets, European Journal of Combinatorics. 18 (1997), 125–136.
  * [2] R. Ahlswede and L.H. Khachatrian, The Complete Nontrivial-Intersection Theorem for Systems of Finite Sets, Journal of Combinatorial Theory, Series A. 76 (1996), 121–138.
  * [3] R. Alweiss, S. Lovett, K. Wu, and J. Zhang, Improved bounds for the sunflower lemma, arXiv:1908.08483 (2019)
  * [4] P. Borg, Extremal t-intersecting sub-families of hereditary families, Journal of the London Mathematical Society 79 (2009), 167–185. https://doi.org/10.1112/jlms/jdn062.
  * [5] P. Cameron and C.Y. Ku, Intersecting families of permutations, Europ. J. Comb. 24 (2003), 881–890.
  * [6] I. Dinur and E. Friedgut, Intersecting Families are Essentially Contained in Juntas, Comb. Probab. Comput. 18 (2009), 107–122.
  * [7] I. Dinur and S. Safra, On the hardness of approximating minimum vertex cover, Annals of Mathematics 162 (2005), 439–485.
  * [8] D. Ellis, Y. Filmus, and E. Friedgut, Triangle-intersecting families of graphs, J. Eur. Math. Soc. 14 (2012), N3, 841–885.
  * [9] D. Ellis, E. Friedgut, and H. Pilpel, Intersecting Families of Permutations, J. Amer. Math. Soc. 24 (2011), 649–682.
  * [10] D. Ellis, N. Keller, and N. Lifshitz, Stability for the Complete Intersection Theorem, and the Forbidden Intersection Problem of Erdős and Sós, arXiv:1604.06135 (2016).
  * [11] D. Ellis and N. Lifshitz, Approximation by juntas in the symmetric group, and forbidden intersection problems, Duke Math. J. 171 (2022), N7, 1417–1467.
  * [12] P. Erdős, C. Ko, and R. Rado, Intersection theorems for systems of finite sets, The Quart. J. Math. 12 (1961), N1, 313–320.
  * [13] P. Frankl, The Erdős-Ko-Rado theorem is true for n=ckt, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, 365–375, Colloq. Math. Soc. János Bolyai, 18, North-Holland.
  * [14] P. Frankl, Erdos-Ko-Rado theorem with conditions on the maximal degree, J. Combin. Theory Ser. A 46 (1987), N2, 252–263.
  * [15] P. Frankl and M. Deza, On the maximum number of permutations with given maximal or minimal distance, J. Combin. Theory, Ser. A 22 (1977), 352–360.
  * [16] P. Frankl and Z. Füredi, Forbidding just one intersection, J. Combin. Theory Ser. A 39 (1985), 160–176.
  * [17] P. Frankl and Z. Füredi, Exact solution of some Turán-type problems, J. Combin. Theory Ser. A 45 (1987), 226–262.
  * [18] P. Frankl and Z. Füredi, Beyond the Erdos-Ko-Rado theorem, J. Combin. Theory Ser. A 56 (1991) N2, 182–194.
  * [19] P. Frankl, R.L. Graham, Intersection Theorems for Vector Spaces, European Journal of Combinatorics 6 (1985), 183–187.
  * [20] P. Frankl and V. Rödl, Forbidden intersections, Trans. Amer. Math. Soc. 300 (1987), 259–286.
  * [21] P. Frankl and V. Rödl, A partition property of simplices in Euclidean space, J. Amer. Math. Soc., 3 (1990), N1, 1–7.
  * [22] P. Frankl and R.Wilson, Intersection theorems with geometric consequences, Combinatorica 1 (1981), 357–368.
  * [23] Ehud Friedgut, On the measure of intersecting families, uniqueness and stability, Combinatorica 28 (2008), N5, 503–528.
  * [24] A.J.W. Hilton, E.C. Milner, Some intersection theorems for systems of finite sets, Quart. J. Math. Oxf. 18 (1967), 369–384.
  * [25] N. Keller and N. Lifshitz, The Junta Method for Hypergraphs and Chvátal’s Simplex Conjecture, arXiv:1707.02643 (2017).
  * [26] P. Keevash, N. Lifshitz, E. Long, and D. Minzer, Global hypercontractivity and its applications, arXiv.2103.04604 (2021).
  * [27] Nathan Keller, Noam Lifshitz, and Omri Marcus, Sharp hypercontractivity for global functions, arxiv:2307.01356
  * [28] N. Keller, N. Lifshitz, D. Minzer, and O. Sheinfeld, On $t$-intersecting families of permutations, http://arxiv.org/abs/2303.15755v2
  * [29] A. Kupavskii, Erdős–Ko–Rado type results for partitions via spread approximations (2023), arXiv.2309.00097.
  * [30] A. Kupavskii, Intersection theorems for uniform subfamilies of hereditary families (2023), arXiv.2311.02246.
  * [31] A. Kupavskii, D. Zakharov, Regular bipartite graphs and intersecting families, Journal of Combinatorial Theory, Series A 155 (2018), 180–189. https://doi.org/10.1016/j.jcta.2017.11.006.
  * [32] A. Kupavskii and D. Zakharov, Spread approximations for forbidden intersections problems, to appear in Advances in Mathematics, available at arxiv:2203.13379
  * [33] B. Larose and C. Malvenuto, Stable sets of maximal size in Kneser-type graphs, Eur. J. Comb. 25 (2004), N5, 657–673.
  * [34] K. Meagher, L. Moura, Erdős–Ko–Rado theorems for uniform set-partition systems, The Electronic Journal of Combinatorics (2005), R40. https://doi.org/10.37236/1937.
  * [35] A.M. Raigorodskii, Borsuk’s problem and the chromatic numbers of some metric spaces, Russian Math. Surveys, 56 (2001), N1, 103–139.
  * [36] A.M. Raigorodskii, Coloring Distance Graphs and Graphs of Diameters, Thirty Essays on Geometric Graph Theory, New York, Springer (2013), 429–460.
  * [37] T. Tao,The sunflower lemma via shannon entropy, https://terrytao.wordpress.com/2020/07/20/the-sunflower-lemma-via-shannon-entropy/
  * [38] R. M. Wilson, The exact bound in the Erds̋–Ko–Rado theorem, Combinatorica 4 (1984), N2- 3, 247–257.