# Uniqueness for 2-Intersecting Families of
Permutations and Perfect Matchings

Gilad Chase  Technion — Israel Institute of Technology  Neta Dafni  Technion —
Israel Institute of Technology  Yuval Filmus  Technion — Israel Institute of
Technology  Nathan Lindzey  Technion — Israel Institute of Technology

###### Abstract

We give a characterization of the largest $2$-intersecting families of
permutations of $\\{1,2,\ldots,n\\}$ and of perfect matchings of the complete
graph $K_{2n}$ for all $n\geq 2$.

##  1 Introduction

Erdős–Ko–Rado theory [EKR61] studies intersecting families of objects. One of
the high points of the theory is the Ahlswede–Khachatrian theorem [AK97,
AK99].

######  Theorem 1.1.

Let $\mathcal{F}$ be a subset of $\binom{[n]}{k}$ (the collection of all
subsets of $[n]:=\\{1,\ldots,n\\}$ of size $k$) which is _$t$ -intersecting_:
every $A,B\in\mathcal{F}$ satisfy $|A\cap B|\geq t$. Then

$|\mathcal{F}|\leq\max_{r\leq(n-t)/2}\left|\left\\{A\subseteq\binom{[n]}{k}:|A\cap[t+2r]|\geq
t+r\right\\}\right|.$

Furthermore, if $\mathcal{F}$ achieves this bound, then

$\mathcal{F}=\left\\{A\subseteq\binom{[n]}{k}:|A\cap S|\geq t+r\right\\}$

for some $r\leq(n-t)/2$ and some $S\subseteq[n]$ of size $t+2r$.

The theorem consists of two statements: an _upper bound_ on the size of
$t$-intersecting families, and a characterization of the extremal families.
The latter part is known as _uniqueness_.

The Ahlswede–Khachatrian theorem is about intersecting families of sets. In
this paper, we will be interested in intersecting families of permutations and
perfect matchings.

##### Permutations

Let $S_{n}$ be the group of all permutations of $[n]$. Two permutations
$\alpha,\beta\in S_{n}$ are _$t$ -intersecting_ if there exist $t$ distinct
indices $i_{1},\ldots,i_{t}\in[n]$ such that
$\alpha(i_{1})=\beta(i_{1}),\ldots,\alpha(i_{t})=\beta(i_{t})$. Ellis,
Friedgut and Pilpel [EFP11] conjectured that the Ahlswede–Khachatrian theorem
extends to intersecting families of permutations.

######  Conjecture 1.2.

Let $\mathcal{F}$ be a subset of $S_{n}$ which is $t$-intersecting. Then

$|\mathcal{F}|\leq\max_{r\leq(n-t)/2}\left|\left\\{\alpha\in
S_{n}:\alpha(i)=i\text{ for at least }t+r\text{ many
}i\in[t+2r]\right\\}\right|.$

Furthermore, if $\mathcal{F}$ achieves this bound, then

$\mathcal{F}=\left\\{\alpha\in S_{n}:\alpha(i_{s})=j_{s}\text{ for at least
}t+r\text{ many }s\in[t+2r]\right\\}$

for some $r\leq(n-t)/2$ and some distinct $i_{1},\ldots,i_{t+2r}\in[n]$ and
distinct $j_{1},\ldots,j_{t+2r}\in[n]$.

When $t\leq 3$, the maximum is always attained at $r=0$, in which case the
upper bound is $(n-t)!$, and the conjectured extremal families are the _$t$
-cosets_.

Deza and Frankl [FD77] proved the upper bound part of 1.2 in the special case
$t=1$ by noticing that the $n$ cyclic rotations of any fixed permutation are
pairwise non-$1$-intersecting. Proving uniqueness in this case proved a lot
harder, but eventually many proofs were found [CK03, LM04, GM09, EFP11].

The case $t>1$ is significantly harder. For every $t>1$, Ellis, Friedgut and
Pilpel [EFP11] proved that the upper bound in 1.2 holds for large enough $n$,
and Ellis [Ell12a] proved that the uniqueness part of 1.2 holds for large
enough $n$. Ellis, Friedgut and Pilpel used a spectral technique based on the
so-called Hoffman bound (closely related to the Lovász theta function and to
the linear programming bound in coding theory), which has found many other
applications in Erdős–Ko–Rado theory [GM16].

Recently, Meagher and Razafimahatratra [MR21], refining the techniques of
Ellis, Friedgut and Pilpel, proved that $2$-intersecting subsets of $S_{n}$
contain at most $(n-2)!$ permutations, thus verifying the upper bound part of
1.2 for $t=2$ and _all_ $n$. However, they were unable to characterize the
extremal families in this case. In this paper, we show that all such families
are $2$-cosets, thus verifying the uniqueness part of 1.2 for $t=2$ and all
$n$.

######  Theorem 1.3.

Let $n\geq 2$. If $\mathcal{F}$ is a $2$-intersecting subset of $S_{n}$ of
size $(n-2)!$, then there exist $i_{1}\neq i_{2}$ and $j_{1}\neq j_{2}$ such
that

$\mathcal{F}=\\{\alpha\in S_{n}:\alpha(i_{1})=j_{1}\text{ and
}\alpha(i_{2})=j_{2}\\}.$

##### Perfect matchings

So far we have considered intersecting families of permutations. A related
area of study is intersecting families of perfect matchings of the complete
graph $K_{2n}$. This can be seen as the non-bipartite analog of the symmetric
group, which is the set of perfect matchings in the complete bipartite graph
$K_{n,n}$.

A simple argument shows that a $1$-intersecting family of perfect matchings
contains at most $(2n-3)!!=(2n-3)(2n-5)\cdots(1)$ perfect matchings. More
difficult arguments [GM17, Lin17, MM05, DFL+21] show that this is attained
uniquely by $1$-cosets.

Lindzey [Lin18a, Lin18b] extended the arguments of Ellis, Friedgut and Pilpel
[EFP11, Ell12a] to the setting of perfect matchings, proving that for all $t$,
the maximum size $t$-intersecting families are $t$-cosets, for large enough
$n$.

Recently, Fallat, Meagher and Shirazi showed that the maximum size of a
$2$-intersecting family is at most $(2n-5)!!$ for all $n$. Extending our
arguments in the setting of the symmetric group, we prove an analog of Theorem
1.3 in the setting of the perfect matching scheme.

######  Theorem 1.4.

Let $n\geq 2$. If $\mathcal{F}$ is a $2$-intersecting subset of
$\mathcal{M}_{2n}$ of size $(2n-5)!!$, then there exist distinct
$i_{1},j_{1},i_{2},j_{2}$ such that $\mathcal{F}$ consists of all perfect
matchings containing the edges $\\{i_{1},j_{1}\\},\\{i_{2},j_{2}\\}$.

##### On the proof

The spectral technique used by Ellis, Friedgut and Pilpel shows that for every
$t\geq 1$, if $n$ is large enough and $\mathcal{F}\subseteq S_{n}$ is a
$t$-intersecting family of size $(n-t)!$, then the characteristic function of
$\mathcal{F}$, denoted as $1_{\mathcal{F}}$, has _degree_ at most $t$. This
means that $1_{\mathcal{F}}$ can be expressed as a polynomial of degree at
most $t$ in the Boolean variables $x_{ij}$, where $x_{ij}=1$ if the input
permutation maps $i$ to $j$. Equivalently, $x_{ij}$ is the $(i,j)$’th entry of
the permutation matrix representing the input permutation.

Similarly, Meagher and Razafimahatratra show that if $n\geq 5$ and
$\mathcal{F}\subseteq S_{n}$ is a $2$-intersecting family of size $(n-2)!$,
then the characteristic function of $\mathcal{F}$ has degree at most $2$. This
is the starting point of this work.

Ellis, Friedgut and Pilpel used polyhedral techniques (chiefly, the
Birkhoff–von Neumann theorem on bistochastic matrices) to show that Boolean
degree $1$ functions are _dictators_ , that is, they either depend only on
$\alpha(i)$ for some $i\in[n]$ (where $\alpha$ is the input permutation), or
they depend only on $\alpha^{-1}(j)$ for some $j\in[n]$. The only
$1$-intersecting dictators are $1$-cosets, and this provides a proof of the
uniqueness part of 1.2 when $t=1$.

Similar techniques do not work for larger degree [Fil17]. Instead, we turn to
the theory of _complexity measures of Boolean functions_ [BdW02], which was
recently generalized to the symmetric group and to the perfect matching scheme
by Dafni et al. [DFL+21]. Using these techniques, Dafni et al. give a simple
proof of the uniqueness part of 1.2, as well as of its analog for the perfect
matching scheme, for large $n$.

The chief tool used by Dafni et al., which we also employ in our proof, is
_certificate complexity_. Let $f\colon S_{n}\to\\{0,1\\}$ be a Boolean
function, and let $\alpha\in S_{n}$ be such that $f(\alpha)=b$. A
_certificate_ for $\alpha$ is a subset $\\{i_{1},\ldots,i_{m}\\}\subseteq[n]$
such that $f(\beta)=b$ whenever
$\beta(i_{1})=\alpha(i_{1}),\ldots,\beta(i_{m})=\alpha(i_{m})$. The idea is
that in order to verify that $f(\alpha)=b$, it suffices to check the value of
$\alpha(i_{1}),\ldots,\alpha(i_{m})$. The _certificate complexity_ of $\alpha$
is the minimum size of a certificate for $\alpha$, and the certificate
complexity of $f$ is the maximum, over all $\alpha\in S_{n}$, of the
certificate complexity of $\alpha$. We denote the certificate complexity of
$f$ by $C(f)$.

Suppose that $f$ is the characteristic function of a $2$-intersecting subset
of $S_{n}$. When $C(f)\leq n-2$, we give a structure theorem for $f$ which
suffices to bound the size of the family away from $(n-2)!$ unless $C(f)=2$,
in which case $f$ is the characteristic function of a $2$-coset. A simple
argument (using another complexity measure, _sensitivity_) shows that if
$n\geq 8$ and $f\colon S_{n}\to\\{0,1\\}$ has degree at most $2$ then
$C(f)\leq n-2$, allowing us to apply the preceding argument. Finally, we
handle the case $n\leq 7$ using exhaustive search, employing an algorithm for
enumerating maximum cliques.

Similar techniques work in the case of the perfect matching scheme, with one
complication: the proof of our structure theorem relies on the fact that
Boolean degree $1$ functions on the symmetric group have certificate
complexity $1$, but this fails for the perfect matching scheme. Using the
maximality of maximum-size $2$-intersecting families, we are able to overcome
this hurdle.

##### Future research

1.2 is about families of permutations in which any two permutations agree on
the images of $t$ points. A related question concerns $t$-setwise-intersecting
families of permutations, in which any two permutations $\alpha,\beta$ agree
on the image of a set of size $t$:
$\\{\alpha(i_{1}),\ldots,\alpha(i_{t})\\}=\\{\beta(i_{1}),\ldots,\beta(i_{t})\\}$
for a set of size $t$.

Ellis [Ell12b] showed that for every $t$, if $n$ is large enough then the
maximum size of a $t$-setwise-intersecting subset of $S_{n}$ is $t!(n-t)!$,
and this is achieved uniquely by families of the form

$\bigl{\\{}\alpha\in
S_{n}:\\{\alpha(i_{1}),\ldots,\alpha(i_{t})\\}=\\{j_{1},\ldots,j_{t}\\}\bigr{\\}},$

which we call _$t$ -setwise-cosets_.

Meagher and Razafimahatrata [MR21] showed that when $t=2$, the upper bound
holds for all $n\geq 2$, and moreover, if $n\geq 4$ and $f$ is the
characteristic function of a $2$-setwise-intersecting family of size
$2(n-2)!$, then $f$ has degree at most $2$ and additionally satisfies
$f^{=(n-2,1,1)}=0$ (see Section 2.1.1 for an explanation of this notation). In
other words, $f^{=\lambda}\neq 0$ only for $\lambda=(n),(n-1,1),(n-2,2)$.

Behajaina, Maleki, Rasoamanana and Razafimahatratra [BMRR21] showed that when
$t=3$, the upper bound holds for all $n\geq 11$, and moreover, if $f$ is the
characteristic function of a $3$-setwise-intersecting family of size
$6(n-3)!$, then $f^{=\lambda}\neq 0$ only for
$\lambda=(n),(n-1,1),(n-2,2),(n-3,3)$.

In both cases, the authors were unable to classify the extremal families. Can
we extend our techniques to show that the extremal families are $t$-setwise-
cosets? The first step in this direction was already taken by the second
author in her master’s thesis [Daf22], who showed that this holds for large
$n$. One of the difficulties in obtaining bounds for small $n$ is taking
advantage of the characterization of extremal $f$, which is stronger than a
mere degree bound.

We mention in passing two more challenges. One is to extend the theory of
setwise-intersecting families from permutations to perfect matchings. A
$t$-setwise intersecting family of perfect matchings is one in which for any
two perfect matchings $m_{1},m_{2}$ there are two sets $A,B$ of size $t$ such
that both $m_{1},m_{2}$ match the vertices in $A$ to vertices in $B$. Another
possible generalization is to require the existence of a single set $C$ of
size $2t$ such that both $m_{1}$ and $m_{2}$ match vertices in $C$ to vertices
in $C$.

The other is a common generalization of $t$-intersecting families and
$t$-setwise-intersecting families. Given a partition
$\lambda=\lambda_{1},\ldots,\lambda_{m}$, a $\lambda$-intersecting family of
permutations is one in which for any two permutations $\alpha,\beta$ there are
disjoint sets $A_{1},\ldots,A_{m}$ of sizes $\lambda_{1},\ldots,\lambda_{m}$
such that $\alpha(A_{1})=\beta(A_{1}),\ldots,\alpha(A_{m})=\beta(A_{m})$. A
$t$-intersecting family corresponds to $\lambda=(1^{t})$, and a $t$-setwise-
intersecting family corresponds to $\lambda=(t)$.

##### Structure of the paper

We start with a few preliminaries in Section 1. Apart from introducing several
key definitions and results, we also prove several results appearing in a more
general form in [DFL+21], in order to keep the paper self-contained. Theorem
1.3 is then proved in Section 3, and Theorem 1.4 in Section 4.

##### Acknowledgements

This project has received funding from the European Union’s Horizon 2020
research and innovation programme under grant agreement No 802020-ERC-
HARMONIC.

##  2 Preliminaries

###  2.1 Symmetric group

For integer $n\geq 1$, the _symmetric group_ $S_{n}$ is the collection of all
permutations of $[n]=\\{1,\ldots,n\\}$. We denote the identity permutation by
$\mathsf{id}$.

A _$t$ -coset_ of $S_{n}$ is a set of the form

$\\{\alpha\in S_{n}:\alpha(i_{1})=j_{1},\ldots,\alpha(i_{t})=j_{t}\\},$

where $i_{1},\ldots,i_{t}\in[n]$ are distinct and $j_{1},\ldots,j_{t}\in[n]$
are distinct. A $t$-coset contains $(n-t)!$ permutations.

We use the term _coset_ for a $1$-coset. For $i,j\in[n]$, the coset $[i\mapsto
j]$ consists of all permutations sending $i$ to $j$:

$[i\mapsto j]=\\{\alpha\in S_{n}:\alpha(i)=j\\}.$

Two permutations $\alpha,\beta\in S_{n}$ are _$t$ -intersecting_ if there is a
$t$-coset which contains both of them. Equivalently, the two permutations
$t$-intersect if there are distinct indices $i_{1},\ldots,i_{t}\in[n]$ such
that $\alpha(i_{1})=\beta(i_{1}),\ldots,\alpha(i_{t})=\beta(i_{t})$.

A subset $\mathcal{F}\subseteq S_{n}$ is _$t$ -intersecting_ if every pair of
permutations in $\mathcal{F}$ are $t$-intersecting.

####  2.1.1 Degree

We can represent permutations $\alpha\in S_{n}$ using $n^{2}$ variables
$x_{ij}$ whose semantics are: $x_{ij}=1$ if $\alpha(i)=j$, and $x_{ij}=0$
otherwise. The _degree_ of a function $f\colon S_{n}\to\mathbb{R}$, denoted
$\deg f$, is the minimal $d$ such that $f$ can be represented as a degree $d$
polynomial over the variables $x_{ij}$. For example, the characteristic
function of a $t$-coset has degree at most $t$, since it can be represented by
the polynomial $x_{i_{1}j_{1}}\cdots x_{i_{t}j_{t}}$.

An equivalent way to define degree is via the representation theory of the
symmetric group. Let $\mathbb{R}[S_{n}]$ be the vector space of all real-
valued functions over the symmetric group. Representation theory gives an
orthogonal decomposition (with respect to the inner product $\langle
f,g\rangle=\sum_{\alpha\in S_{n}}f(\alpha)g(\alpha)$)

$\mathbb{R}[S_{n}]=\bigoplus_{\lambda\vdash n}V^{\lambda},$

where $\lambda$ goes over all integer partitions of $n$, and $V^{\lambda}$ are
certain subspaces known as _isotypic components_ , which we define explicitly
in Section 2.1.3. Accordingly, every function $f\colon S_{n}\to\mathbb{R}$ has
a unique decomposition

$f=\sum_{\lambda\vdash n}f^{=\lambda},$

where $f^{=\lambda}\in V^{\lambda}$. Ellis, Friedgut and Pilpel [EFP11,
Theorem 7] showed that $\deg f$ is the maximal $d$ such that $f^{=\lambda}\neq
0$ for some $\lambda$ satisfying $\lambda_{1}=n-d$. In particular, every
function has degree at most $n-1$.

We can now formally state the main result of Meagher and Razafimahatratra
[MR21, Corollary 5.5].

######  Theorem 2.1.

If $n\geq 5$ then any $2$-intersecting family $\mathcal{F}\subseteq S_{n}$
contains at most $(n-2)!$ permutations. Furthermore, if $f\colon
S_{n}\to\\{0,1\\}$ is the characteristic vector of a $2$-intersecting family
of size $(n-2)!$, then $\deg f\leq 2$.

We will also need a result of Ellis, Friedgut and Pilpel [EFP11] classifying
degree $1$ functions.

######  Theorem 2.2 ([EFP11, Corollary 2]).

If $f\colon S_{n}\to\\{0,1\\}$ has degree at most $1$ then either

$f=\sum_{j\in J}x_{ij}$

for some $i\in[n]$ and $J\subseteq[n]$, or

$f=\sum_{i\in I}x_{ij}$

for some $I\subseteq[n]$ and $j\in[n]$.

See also [DFL+21, Theorem 6.1] for an alternative (but very similar) proof.

####  2.1.2 Certificate complexity

Fix $n$. A _certificate_ is a set
$C=\\{(i_{1},j_{1}),\ldots,(i_{m},j_{m})\\}\subseteq[n]\times[n]$. A
permutation $\alpha\in S_{n}$ _satisfies_ the certificate $C$ if
$\alpha(i_{1})=j_{1},\ldots,\alpha(i_{m})=j_{m}$. The set of permutations
satisfying a certificate $C$ is either empty or a $|C|$-coset.

We sometimes think of a permutation $\alpha\in S_{n}$ as the certificate
$\\{(1,\alpha(1)),\ldots,(n,\alpha(n))\\}$, which we call the _certificate
representation_ of $\alpha$.

A _Boolean function_ is a function $f\colon S_{n}\to\\{0,1\\}$. Given
$\alpha\in S_{n}$ such that $f(\alpha)=b$, a _certificate for $\alpha$_ (with
respect to $f$) is a certificate $C$ such that:

  1. (i)

$\alpha$ satisfies $C$.

  2. (ii)

If $\beta$ satisfies $C$ then $f(\beta)=b$.

Intuitively, in order to certify that $f(\alpha)=b$, it suffices to verify
that $\alpha$ satisfies $C$.

The _certificate complexity_ of $\alpha$, denoted $C(f,\alpha)$, is the
minimum size of a certificate for $\alpha$. A certificate for $\alpha$ of this
size is known as a _minimum certificate_. Since every permutation is
determined by its values on the points $1,\ldots,n-1$, the certificate
complexity of $\alpha$ is always at most $n-1$.

The _certificate complexity_ of $f$, denoted $C(f)$, is $\max_{\alpha\in
S_{n}}C(f,\alpha)$. The certificate complexity of $f$ is always at most $n-1$.

Dafni et al. [DFL+21, Theorem 3.1] showed that certificate complexity is
polynomially related to the degree: $C(f)=O((\deg f)^{8})$ and $\deg
f=O(C(f)^{4})$.

In the special case of degree $1$, Theorem 2.2 implies that $C(f)\leq 1$.

######  Lemma 2.3.

If $f\colon S_{n}\to\\{0,1\\}$ has degree at most $1$ then $C(f)\leq 1$.

###### Proof.

According to Theorem 2.2, either $f=\sum_{j\in J}x_{ij}$ for some $i\in[n]$
and $J\subseteq[n]$, or $f=\sum_{i\in I}x_{ij}$ for some $I\subseteq[n]$ and
$j\in[n]$. In the former case, every $\alpha\in S_{n}$ has the certificate
$\\{(i,\alpha(i))\\}$, and in the latter case, every $\alpha\in S_{n}$ has the
certificate $\\{(\alpha^{-1}(j),j)\\}$. ∎

The following lemma, which essentially follows from [DFL+21, Lemma 7.3], shows
that if $\mathcal{F}$ is a $2$-intersecting family then minimum certificates
of any two permutations in $\mathcal{F}$ must $2$-intersect, unless
$C(f)=n-1$.

######  Lemma 2.4.

Let $f\colon S_{n}\to\\{0,1\\}$ be the characteristic function of a
$2$-intersecting family, and suppose that $C(f)\leq n-2$. If
$f(\alpha)=f(\beta)=1$ and $C_{\alpha},C_{\beta}$ are minimum certificates for
$\alpha,\beta$ (respectively), then $|C_{\alpha}\cap C_{\beta}|\geq 2$.

###### Proof.

We will show that there exist $\alpha^{\prime}\in S_{n}$ satisfying
$C_{\alpha}$ and $\beta^{\prime}\in S_{n}$ satisfying $C_{\beta}$ such that
$\alpha^{\prime}\cap\beta^{\prime}=C_{\alpha}\cap C_{\beta}$, where we
identify $\alpha^{\prime},\beta^{\prime}$ with their certificate
representations. Since $f(\alpha^{\prime})=f(\beta^{\prime})=1$ and $f$ is the
characteristic function of a $2$-intersecting family, we have
$|\alpha^{\prime}\cap\beta^{\prime}|\geq 2$, and so $|C_{\alpha}\cap
C_{\beta}|\geq 2$.

We start by constructing $\alpha^{\prime}$ satisfying $C_{\alpha}$ such that
$\alpha^{\prime}\cap C_{\beta}=C_{\alpha}\cap C_{\beta}$. Let
$C_{\alpha}=\\{(i_{1},j_{1}),\ldots,(i_{m},j_{m})\\}$, where $m\leq n-2$, let
$i^{\prime}_{1},\ldots,i^{\prime}_{n-m}$ be the $i$-indices not mentioned in
$C_{\alpha}$, and let $j^{\prime}_{1},\ldots,j^{\prime}_{n-m}$ be the
$j$-indices not mentioned in $C_{\alpha}$.

For each $i^{\prime}_{s}$, there is at most one $j^{\prime}_{t}$ such that
$(i^{\prime}_{s},j^{\prime}_{t})\in C_{\beta}$. We can therefore arrange the
indices in such a way that if $(i^{\prime}_{s},j^{\prime}_{t})\in C_{\beta}$
then $s=t$. We can now define $\alpha^{\prime}$ explicitly:

$\alpha^{\prime}(i_{1})=j_{1},\ldots,\alpha^{\prime}(i_{m})=j_{m},\alpha^{\prime}(i^{\prime}_{1})=j^{\prime}_{2},\ldots,\alpha^{\prime}(i^{\prime}_{n-m-1})=j^{\prime}_{n-m},\alpha^{\prime}(i^{\prime}_{n-m})=j^{\prime}_{1}.$

The same argument (replacing $C_{\alpha},C_{\beta}$ by
$C_{\beta},\alpha^{\prime}$) shows that we can find $\beta^{\prime}$
satisfying $C_{\beta}$ such that
$\alpha^{\prime}\cap\beta^{\prime}=\alpha^{\prime}\cap
C_{\beta}=C_{\alpha}\cap C_{\beta}$, completing the proof. ∎

When $C(f)=n-1$, the conclusion of Lemma 2.4 indeed fails. For example,
consider the family $\mathcal{F}\subseteq S_{5}$ given by
$\mathcal{F}=\\{\mathsf{id},(1\;2\;3)\\}$, and the minimum certificates
$\\{(1,1),(2,2),(3,3),(4,4)\\}$ and $\\{(1,2),(2,3),(3,1),(4,4)\\}$.

Using the concept of _sensitivity_ , we can rule out the case $C(f)=n-1$ for
functions of degree at most $2$. The proof is based on the technique used to
prove [DFL+21, Lemma 3.6].

######  Lemma 2.5.

If $n\geq 8$ and $f\colon S_{n}\to\\{0,1\\}$ has degree at most $2$, then
$C(f)\leq n-2$.

###### Proof.

The proof is by contradiction. Suppose that $n\geq 8$, that $f\colon
S_{n}\to\\{0,1\\}$ has degree at most $2$, and that $C(f)=n-1$. Without loss
of generality, $C(f,\mathsf{id})=n-1$ and $f(\mathsf{id})=0$. Then
$f((i\;j))=1$ for all $i\neq j\in[n]$ (here $(i\;j)$ is the transposition
switching $i$ and $j$), since otherwise $\\{(k,k):k\neq i,j\\}$ would be a
certificate for $\mathsf{id}$ of size $n-2$.

We construct a function $g\colon\\{0,1\\}^{4}\to\\{0,1\\}$ as follows:

$g(y_{1},y_{2},y_{3},y_{4})=f\bigl{(}(1\;2)^{y_{1}}(3\;4)^{y_{2}}(5\;6)^{y_{3}}(7\;8)^{y_{4}}\bigr{)}.$

Here $(i\;j)^{0}=\mathsf{id}$, $(i\;j)^{1}=(i\;j)$, and the input to $f$ is
the product of four powers of this kind.

Since $f$ has degree at most $2$, it can be written as a polynomial of degree
at most $2$ in the variables $x_{ij}$. Given $y_{1},y_{2},y_{3},y_{4}$, the
value of the variables $x_{ij}$ is:

$\displaystyle x_{11}=x_{22}=1-y_{1}$ $\displaystyle x_{12}=x_{21}=y_{1}$
$\displaystyle x_{33}=x_{44}=1-y_{2}$ $\displaystyle x_{34}=x_{43}=y_{2}$
$\displaystyle x_{55}=x_{66}=1-y_{3}$ $\displaystyle x_{56}=x_{65}=y_{3}$
$\displaystyle x_{77}=x_{88}=1-y_{4}$ $\displaystyle x_{78}=x_{87}=y_{4}$

All other variables are assigned zero. This shows that $g$ can be expressed as
a polynomial of degree at most $2$ in the variables $y_{1},y_{2},y_{3},y_{4}$.
We say that $g$ has _degree at most $2$_.

By construction, the function $g$ satisfies the following constraints:

$\displaystyle g(0,0,0,0)=f(\mathsf{id})=0$ $\displaystyle
g(1,0,0,0)=f((1\;2))=1$ $\displaystyle g(0,1,0,0)=f((3\;4))=1$ $\displaystyle
g(0,0,1,0)=f((5\;6))=1$ $\displaystyle g(0,0,0,1)=f((7\;8))=1$

We say that $g$ has _sensitivity $4$_.

There are only $2^{16}$ many functions from $\\{0,1\\}^{4}$ to $\\{0,1\\}$.
For each function, we can check whether it has degree at most $2$ by solving
linear equations, since each function has a unique representation as a
multilinear polynomial in $y_{1},y_{2},y_{3},y_{4}$ (this is a basic fact in
Boolean function analysis). Going over all such functions in SAGE [Sag22], we
find out that none of them has sensitivity $4$, a contradiction. The relevant
code appears in Section A.1. ∎

For experts in Boolean function analysis, here is an alternative proof that
$g$ cannot have sensitivity $4$. Since $\deg g\leq 2$, every influential
variable has influence at least $1/2$ [O’D14, Proposition 3.6]. If $g$ has
sensitivity $4$, then it depends on $4$ variables, and so its total influence
is $2$. Since $g$ has degree $2$, this can only happen if $g$ is homogeneous
of degree $2$. But in that case, the sensitivity of $g$ at every point is
exactly $2$ [FHKL16, Proposition 3.7].

The bound on the sensitivity cannot be improved: the Boolean function

$g(y_{1},y_{2},y_{3})=y_{1}y_{2}y_{3}+(1-y_{1})(1-y_{2})(1-y_{3})$

has degree $2$ and satisfies

$g(0,0,0)=1,\quad g(1,0,0)=g(0,1,0)=g(0,0,1)=0.$

####  2.1.3 Degree reduction

Let $\mathcal{F}\subseteq S_{n}$. We denote the restriction of $\mathcal{F}$
to the coset $[i\mapsto j]$ by $\mathcal{F}|_{[i\mapsto j]}$. We can think of
$\mathcal{F}|_{[i\mapsto j]}$ as a subset of $S_{n-1}$. Formally speaking, we
can think of $S_{n}$ as the set of all injections from $[n]$ to $[n]$. The
restriction of $S_{n}$ to the coset $[i\mapsto j]$ is isomorphic to the set of
all injections from $[n]\setminus\\{i\\}$ to $[n]\setminus\\{j\\}$, which is
the same as $S_{n-1}$ up to renumbering.

Let $f$ be the characteristic function of $\mathcal{F}$. The definition of
degree using polynomials shows that $\deg f|_{[i\mapsto j]}\leq\deg f$, where
$f$ is the characteristic function of $\mathcal{F}|_{[i\mapsto j]}$. Indeed,
given a polynomial representing $f$, we can obtain a polynomial representing
$f|_{[i\mapsto j]}$ by substituting $x_{ij}=1$ and
$x_{ij^{\prime}}=x_{i^{\prime}j}=0$ for any $i^{\prime}\neq i$ and
$j^{\prime}\neq j$.

The following crucial lemma, which forms part of the proof of [DFL+21, Lemma
5.7], states that if $\mathcal{F}$ is contained in $[i\mapsto j]$, then the
degree of $f$ strictly decreases when restricting to $[i\mapsto j]$.

######  Lemma 2.6.

Suppose that $f\colon S_{n}\to\\{0,1\\}$ is the characteristic function of a
family which is a subset of the coset $[i\mapsto j]$. Then $\deg f|_{[i\mapsto
j]}\leq\max(\deg f-1,0)$.

The corresponding result for functions on the Boolean cube $\\{0,1\\}^{n}$ is
easy to prove. Suppose that $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ is such that
$f(x)=1$ implies $x_{n}=1$. We can write

$f(x_{1},\ldots,x_{n})=(1-x_{n})f_{0}(x_{1},\ldots,x_{n-1})+x_{n}f_{1}(x_{1},\ldots,x_{n-1}).$

Substituting $x_{n}=0$, we get $f_{0}=0$, and so $f=x_{n}f_{1}$. The
restriction of $f$ to the coset $\\{x:x_{n}=1\\}$ is $f_{1}$. If $f_{1}\neq 0$
then clearly $\deg f=\deg f_{1}+1$, where $\deg f$ is the degree of the unique
multilinear polynomial representing $f$.

The argument proving Lemma 2.6 is more subtle. The starting point is the
following explicit description of the subspaces $V^{\lambda}$, which we
mentioned in Section 2.1.1.

Let $\lambda=\lambda_{1},\ldots,\lambda_{m}\vdash n$. A _Young tableau_ of
_shape_ $\lambda$ is an arrangement of the numbers $1,\ldots,n$ in $m$ rows of
lengths $\lambda_{1},\ldots,\lambda_{m}$, left justified. Here are some
examples:

$\begin{array}[]{ccc}\ytableaushort{341,2}&&\ytableaushort{14,23}\\\ \\\
\lambda=(3,1)&&\lambda=(2,2)\end{array}$

Let $s,t$ be a pair of Young tableaux of the same shape
$\lambda_{1},\ldots,\lambda_{m}\vdash n$. The function $e_{s,t}\colon
S_{n}\to\\{0,1\\}$ is defined as follows: $e_{s,t}(\alpha)=1$ if for every
$k\in[m]$, $\alpha$ sends every number on the $k$-th row of $s$ to a number on
the $k$-th row of $t$, and $e_{s,t}(\alpha)=0$ otherwise. For example,
consider

$s=\ytableaushort{123,45}\quad t=\ytableaushort{315,24}$

Then $e_{s,t}(\alpha)=1$ if $\alpha(1),\alpha(2),\alpha(3)\in\\{3,1,5\\}$ and
$\alpha(4),\alpha(5)\in\\{2,4\\}$.

For a tableau $t$ with $m^{\prime}$ columns, we denote by $C(t)$ the _column
stabilizer_ of $t$, which is the set of all permutations of the entries of $t$
which only move entries within the same column. Each permutation $\pi\in C(t)$
thus consists of $m^{\prime}$ permutations $\pi_{1},\ldots,\pi_{m^{\prime}}$,
one for each column. The _sign_ of $\pi$, denote $(-1)^{\pi}$, is the product
of the signs of the permutations $\pi_{1},\ldots,\pi_{m^{\prime}}$. We denote
the result of applying $\pi$ to $t$ by $t^{\pi}$.

Let $s,t$ be a pair of Young tableaux of the same shape $\lambda\vdash n$. We
define a function $\chi_{s,t}\colon S_{n}\to\\{-1,0,1\\}$ as follows:

$\chi_{s,t}=\sum_{\pi\in C(t)}(-1)^{\pi}e_{s,t^{\pi}}.$

Continuing our above example, here is $t^{\pi}$ for all elements $\pi\in
C(t)$, together with their sign:

$\left(\ytableaushort{315,24}~{},+1\right)\quad\left(\ytableaushort{345,21}~{},-1\right)\quad\left(\ytableaushort{215,34}~{},-1\right)\quad\left(\ytableaushort{245,31}~{},+1\right)$

We are interested in the functions $\chi_{s,t}$ since they span $V^{\lambda}$.

######  Theorem 2.7 ([Sag01, Chapter 2]).

Let $\lambda\vdash n$. The subspace $V^{\lambda}$ is spanned by the functions
$\chi_{s,t}$, where $s,t$ go over all pairs of Young tableaux of shape
$\lambda$.

We can now prove Lemma 2.6.

###### Proof of Lemma 2.6.

Assume, for concreteness, that $i=j=n$. If $n=1$ then $\deg f|_{[n\mapsto
n]}=0$, so there is nothing to prove. If $f|_{[n\mapsto n]}=0$ then again
$\deg f|_{[n\mapsto n]}=0$, so there is nothing to prove. Therefore we can
assume that $n\geq 2$ and that $f|_{[n\mapsto n]}\neq 0$.

Let $d=\deg f|_{[n\mapsto n]}$. According to the spectral definition of degree
(see Section 2.1.1), $f|_{[n\mapsto n]}^{=\lambda}\neq 0$ for some
$\lambda\vdash n-1$ such that $\lambda_{1}=(n-1)-d$. Since the decomposition
into isotypic components is orthogonal, this implies that $\langle
f|_{[n\mapsto n]},f|_{[n\mapsto n]}^{=\lambda}\rangle=\langle f|_{[n\mapsto
n]}^{=\lambda},f|_{[n\mapsto n]}^{=\lambda}\rangle\neq 0$. Since
$f|_{[n\mapsto n]}^{=\lambda}\in V^{\lambda}$, Theorem 2.7 implies that
$\langle f|_{[n\mapsto n]},\chi_{s,t}\rangle\neq 0$ for some Young tableaux
$s,t$ of shape $\lambda$.

Let $s^{\prime},t^{\prime}$ be the Young tableaux obtained by adding a new row
to $s,t$ (respectively) consisting only of the number $n$. Here is an example:

$s=\ytableaushort{123,45}\quad
t=\ytableaushort{315,24}\quad\longrightarrow\quad
s^{\prime}=\ytableaushort{123,45,6}\quad t^{\prime}=\ytableaushort{315,24,6}$

The tableaux $s^{\prime},t^{\prime}$ have shape $\mu$ satisfying
$\mu_{1}=\lambda_{1}=(n-1)-d=n-(d+1)$. We will show that $\langle
f,\chi_{s^{\prime},t^{\prime}}\rangle\neq 0$. The orthogonality of the
decomposition into isotypic components would imply that $f^{=\mu}\neq 0$, and
so $\deg f\geq d+1$ by the spectral definition of degree.

Let $\pi^{\prime}\in C(t^{\prime})$ be any permutation such that
$\pi^{\prime}(n)\neq n$. By assumption, $f(\alpha^{\prime})=1$ only if
$\alpha^{\prime}(n)=n$, in which case
$e_{s^{\prime},(t^{\prime})^{\pi^{\prime}}}(\alpha^{\prime})=0$. Therefore
$\langle f,e_{s^{\prime},(t^{\prime})^{\pi^{\prime}}}\rangle=0$. This shows
that

$\langle
f,\chi_{s^{\prime},t^{\prime}}\rangle=\sum_{\begin{subarray}{c}\pi^{\prime}\in
C(t^{\prime})\\\ \pi^{\prime}(n)=n\end{subarray}}(-1)^{\pi^{\prime}}\langle
f,e_{s^{\prime},(t^{\prime})^{\pi^{\prime}}}\rangle.$

If $\pi^{\prime}(n)=n$ then
$e_{s^{\prime},(t^{\prime})^{\pi^{\prime}}}(\alpha^{\prime})\neq 0$ only if
$\alpha^{\prime}(n)=n$. Conversely, if $\alpha^{\prime}(n)=n$, that is, if
$\alpha^{\prime}\in[n\mapsto n]$, then
$e_{s^{\prime},(t^{\prime})^{\pi^{\prime}}}(\alpha^{\prime})=e_{s,t^{\pi}}(\alpha)$,
where $\alpha,\pi$ are the restrictions of $\alpha^{\prime},\pi^{\prime}$ to
$[n-1]$. Moreover, $(-1)^{\pi}=(-1)^{\pi^{\prime}}$. Therefore

$\langle f,\chi_{s^{\prime},t^{\prime}}\rangle=\sum_{\pi\in
C(t)}(-1)^{\pi}\langle f|_{[n\mapsto n]},e_{s,t^{\pi}}\rangle=\langle
f|_{[n\mapsto n]},\chi_{s,t}\rangle\neq 0.\qed$

###  2.2 Perfect matching scheme

For integer $n\geq 1$, the _perfect matching scheme_ $\mathcal{M}_{2n}$ is the
collection of all perfect matchings of the complete graph $K_{2n}$. Since the
symmetric group $S_{n}$ can be viewed as the collection of all perfect
matchings of the complete _bipartite_ graph $K_{n,n}$, we can think of the
perfect matching scheme as the non-bipartite analog of the symmetric group.

The perfect matching scheme $\mathcal{M}_{2n}$ contains $(2n-1)!!$ many
different perfect matchings. Here

$(2n-1)!!=(2n-1)(2n-3)(2n-5)\cdots(5)(3)(1)=\frac{(2n)!}{2^{n}n!}.$

We sometimes think of a perfect matching in $\mathcal{M}_{2n}$ as a set of $n$
pairs of elements from $[2n]$, which together cover all of $[2n]$ (the _pair
representation_). At other times, it will be useful to think of a perfect
matching in $\mathcal{M}_{2n}$ as a fixed-point-free involution on $[2n]$,
that is, $m(i)\neq i$ is the element that $i$ is matched to, and $m(m(i))=i$.

A _$t$ -coset_ of $\mathcal{M}_{2n}$ is a set of the form

$\\{m\in\mathcal{M}_{2n}:m(i_{1})=j_{1},\ldots,m(i_{t})=j_{t}\\},$

where $i_{1},\ldots,i_{t},j_{1},\ldots,j_{t}\in[2n]$ are distinct.111This is a
slight abuse of terminology as $\mathcal{M}_{2n}$ doesn’t afford a natural
group structure. A $t$-coset contains $(2(n-t)-1)!!$ perfect matchings.

We use the term _coset_ for a $1$-coset. For $i\neq j\in[2n]$, the coset
$[i\leftrightarrow j]$ consists of all perfect matchings in which $i,j$ are
matched:

$[i\leftrightarrow j]=\\{m\in\mathcal{M}_{2n}:m(i)=j\\}.$

Note that $[i\leftrightarrow j]=[j\leftrightarrow i]$.

Two perfect matchings $m_{1},m_{2}\in\mathcal{M}_{2n}$ are _$t$ -intersecting_
if there is a $t$-coset which contains both of them. A subset
$\mathcal{F}\subseteq\mathcal{M}_{2n}$ is _$t$ -intersecting_ if any two
perfect matchings in $\mathcal{F}$ are $t$-intersecting.

####  2.2.1 Degree

We can represent perfect matchings $m\in\mathcal{M}_{2n}$ using
$\binom{2n}{2}$ variables $x_{ij}$ (where the index is an unordered pair of
elements) whose semantics are: $x_{ij}=1$ if $m(i)=j$, and $x_{ij}=0$
otherwise. The _degree_ of a function $f\colon\mathcal{M}_{2n}\to\mathbb{R}$,
denoted $\deg f$, is the minimal $d$ such that $f$ can be represented as a
degree $d$ polynomial over the variables $x_{ij}$. For exampole, the
characteristic function of a $t$-coset has degree at most $t$.

An equivalent way to define degree is via the representation theory of the
perfect matching scheme. Let $\mathbb{R}[\mathcal{M}_{2n}]$ be the vector
space of all real-valued functions over the perfect matching scheme.
Representation theory (for example, [CSST08, Chapter 11]) gives an orthogonal
decomposition (with respect to the inner product $\langle
f,g\rangle=\sum_{m\in\mathcal{M}_{2n}}f(m)g(m)$)

$\mathbb{R}[\mathcal{M}_{2n}]=\bigoplus_{\lambda\vdash n}V^{2\lambda},$

where $\lambda$ goes over all integer partitions of $n$, $2\lambda$ is the
partition of $2n$ obtained by doubling each part, and $V^{2\lambda}$ are the
isotypic components, which we define explicitly in Section 2.2.3. Accordingly,
every function $f\colon\mathcal{M}_{2n}\to\mathbb{R}$ has a unique
decomposition

$f=\sum_{\lambda\vdash n}f^{=\lambda},$

where $f^{=\lambda}\in V^{2\lambda}$. Lindzey [Lin18b, Theorem 5.1.1] showed
that $\deg f$ is the maximal $d$ such that $f^{=\lambda}\neq 0$ for some
$\lambda$ satisfying $\lambda_{1}=n-d$. In particular, every function has
degree at most $n-1$.

We can now formally state the main result of Fallat, Meagher and Shirazi
[FMS21, Theorem 4.13].

######  Theorem 2.8.

If $n\geq 3$ then any $2$-intersecting family
$\mathcal{F}\subseteq\mathcal{M}_{2n}$ contains at most $(2n-5)!!$ perfect
matchings. Furthermore, if $f\colon\mathcal{M}_{2n}\to\\{0,1\\}$ is the
characteristic vector of a $2$-intersecting family of size $(2n-5)!!$, then
$\deg f\leq 2$.

We will also need a result of Dafni et al. [DFL+21] classifying degree $1$
functions.

######  Theorem 2.9 ([DFL+21, Theorem 6.2]).

If $f\colon\mathcal{M}_{2n}\to\\{0,1\\}$ has degree at most $1$ then $f$ is
either a _dictator_ :

$f=\sum_{j\in J}x_{ij},$

for some $i\in[2n]$ and $J\subseteq[2n]$ not containing $i$; or $f$ is a
_triangle_ :

$f=x_{ij}+x_{ik}+x_{jk},$

for some distinct $i,j,k\in[2n]$; or $f$ is an _anti-triangle_ :

$f=1-x_{ij}-x_{ik}-x_{jk},$

for some distinct $i,j,k\in[2n]$.

####  2.2.2 Certificate complexity

Fix $n$. A _certificate_ is a set
$C=\bigl{\\{}\\{i_{1},j_{1}\\},\ldots,\\{i_{r},j_{r}\\}\bigr{\\}}\subseteq\binom{[2n]}{2}$,
where $\binom{[2n]}{2}$ is the collection of all subsets of $[2n]$ of size
$2$. A perfect matching $m\in\mathcal{M}_{2n}$ _satisfies_ the certificate $C$
if $m(i_{1})=j_{1},\ldots,m(i_{r})=j_{r}$.

A _Boolean function_ is a function $f\colon\mathcal{M}_{2n}\to\\{0,1\\}$. Just
as in Section 2.1.2, for each $m\in\mathcal{M}_{2n}$ we can define the
following notions: a certificate for $m$ (with respect to $f$); the
certificate complexity of $m$, denoted $C(f,m)$; a minimum certificate; and
the certificate complexity of $f$, denoted $C(f)$. As in the case of the
symmetric group, $C(f)\leq n-1$, since a perfect matching is determined by any
$n-1$ of its edges. Dafni et al. [DFL+21] showed that $C(f)$ is polynomially
related to $\deg f$.

In the case of the symmetric group, degree $1$ functions have certificate
complexity $1$. This is no longer the case for the perfect matching scheme,
since triangles and anti-triangles have certificate complexity $2$.

######  Lemma 2.10.

If $f\colon\mathcal{M}_{2n}\to\\{0,1\\}$ has degree at most $1$ then $C(f)\leq
2$.

###### Proof.

According to Theorem 2.9, $f$ is either a dictator, a triangle, or an anti-
triangle. If $f=\sum_{j\in J}x_{ij}$ is a dictator, then every $m$ has a
certificate $\bigl{\\{}\\{i,m(i)\\}\bigr{\\}}$. If $f=x_{ij}+x_{ik}+x_{jk}$ is
a triangle, then every $m$ such that $f(m)=1$ has one of the certificates
$\bigl{\\{}\\{i,j\\}\bigr{\\}},\bigl{\\{}\\{i,k\\}\bigr{\\}},\bigl{\\{}\\{j,k\\}\bigr{\\}}$,
and every $m$ such that $f(m)=0$ has the certificate
$\bigl{\\{}\\{i,m(i)\\},\\{j,m(j)\\}\bigr{\\}}$. If $f$ is an anti-triangle
then $1-f$ is a triangle, so we can use the same certificates as in the case
of a triangle. ∎

The proof of Lemma 2.4 extends to the perfect matching scheme with minor
changes.

######  Lemma 2.11.

Let $f\colon\mathcal{M}_{2n}\to\\{0,1\\}$ be the characteristic function of a
$2$-intersecting family, and suppose that $C(f)\leq n-2$. If
$f(m_{1})=f(m_{2})=1$ and $C_{m_{1}},C_{m_{2}}$ are minimum certificates for
$m_{1},m_{2}$ (respectively), then $|C_{m_{1}}\cap C_{m_{2}}|\geq 2$.

###### Proof.

We will show how to construct a perfect matching $m^{\prime}_{1}$ satisfying
$C_{m_{1}}$ such that $m^{\prime}_{1}\cap C_{m_{2}}=C_{m_{1}}\cap C_{m_{2}}$.
The same argument can be used to construct a perfect matching $m^{\prime}_{2}$
satisfying $C_{m_{2}}$ such that $m^{\prime}_{1}\cap
m^{\prime}_{2}=m^{\prime}_{1}\cap C_{m_{2}}$. It follows that $|C_{m_{1}}\cap
C_{m_{2}}|=|m^{\prime}_{1}\cap m^{\prime}_{2}|\geq 2$, since $f$ is the
characteristic function of a $2$-intersecting family.

Let
$C_{m_{1}}=\bigl{\\{}\\{i_{1},j_{1}\\},\ldots,\\{i_{r},j_{r}\\}\bigr{\\}}$,
where $r\leq n-2$, and let $k_{1},\ldots,k_{2(n-r)}$ be the indices not
mentioned in $C_{m_{1}}$. Rearrange the indices so that if
$\\{k_{s},k_{t}\\}\in C_{m_{2}}$ then $\\{s,t\\}=\\{2\ell-1,2\ell\\}$ for some
$\ell\in[n-r]$. The perfect matching $m^{\prime}_{1}$ has the pair
representation

$\\{i_{1},j_{1}\\},\ldots,\\{i_{r},j_{r}\\},\\{k_{1},k_{n-r+1}\\},\\{k_{2},k_{n-r+2}\\},\ldots,\\{k_{n-r},k_{2(n-r)}\\}.$

Since $n-r\geq 2$, the new pairs do not intersect $C_{m_{2}}$, completing the
proof. ∎

Using sensitivity, we can rule out the case $C(f)=n-1$ for functions of degree
at most $2$, just as we did for the symmetric group.

######  Lemma 2.12.

If $n\geq 8$ and $f\colon\mathcal{M}_{2n}\to\\{0,1\\}$ has degree at most $2$,
then $C(f)\leq n-2$.

###### Proof.

The proof is by contradiction. Suppose that $n\geq 8$, that
$f\colon\mathcal{M}_{2n}\to\\{0,1\\}$ has degree at most $2$, and that
$C(f)=n-1$, say $C(f,m)=n-1$ for
$m=\bigl{\\{}\\{1,2\\},\\{3,4\\},\ldots,\\{2n-1,2n\\}\bigr{\\}}$. Since
$C(f,m)>n-2$, $m\setminus\bigl{\\{}\\{2i-1,2i\\},\\{2j-1,2j\\}\bigr{\\}}$ is
not a certificate for $m$ for any $i\neq j\in[n]$, and so $f(m^{ij})\neq
f(m)$, where $m^{ij}$ is obtained from $m$ by replacing
$\bigl{\\{}\\{2i-1,2i\\},\\{2j-1,2j\\}\bigr{\\}}$ with
$\bigl{\\{}\\{2i-1,2j\\},\\{2j-1,2i\\}\bigr{\\}}$.

We construct a function $g\colon\\{0,1\\}^{4}\to\\{0,1\\}$ as follows:
$g(y_{1},y_{2},y_{3},y_{4})$ is the value of $f$ on the perfect matching
obtained from $m$ by applying the subset of the operations
${}^{12},^{34},^{56},^{78}$ specified by the input (for example, if $y_{1}=1$
then we apply 12). As in the proof of Lemma 2.5, this results in a function of
degree at most $2$ satisfying $g(0,0,0,0)\neq
g(1,0,0,0)=g(0,1,0,0)=g(0,0,1,0)=g(0,0,0,1)$, which is impossible. ∎

####  2.2.3 Degree reduction

Let $\mathcal{F}\subseteq\mathcal{M}_{2n}$. We denote the restriction of
$\mathcal{F}$ to the coset $[i\leftrightarrow j]$ by
$\mathcal{F}|_{[i\leftrightarrow j]}$, which we can think of as a subset of
$\mathcal{M}_{2(n-1)}$.

Let $f$ be the characteristic function of $\mathcal{F}$. The definition of
degree using polynomials shows that $\deg f|_{[i\leftrightarrow j]}\leq\deg
f$. The following analog of Lemma 2.6 shows that if $\mathcal{F}$ is contained
in $[i\leftrightarrow j]$, then the degree of $f$ strictly decreases when
restriction to $[i\leftrightarrow j]$.

######  Lemma 2.13.

Suppose that $f\colon\mathcal{M}_{2n}\to\\{0,1\\}$ is the characteristic
function of a family which is a subset of the coset $[i\leftrightarrow j]$.
Then $\deg f|_{[i\leftrightarrow j]}\leq\max(\deg f-1,0)$.

Before we can prove this lemma, we need an explicit description of the
subspaces $V^{2\lambda}$, which were mentioned in Section 2.2.1.

Let $\lambda\vdash n$, and let $t$ be a Young tableau of shape $2\lambda$. The
function $e_{t}\colon\mathcal{M}_{2n}\to\\{0,1\\}$ is defined as follows:
$e_{t}(m)=1$ if for all $i\in[2n]$, the element $m(i)$ is in the same row of
$t$ as $i$, and $e_{t}(m)=0$ otherwise. For example, consider

$t=\ytableaushort{1234,5678}$

Then $e_{t}(m)=1$ if $m(1),m(2),m(3),m(4)\in\\{1,2,3,4\\}$ and
$m(5),m(6),m(7),m(8)\in\\{5,6,7,8\\}$.

Given a Young tableau $t$ of shape $2\lambda$, we define a function
$\chi_{t}\colon\mathcal{M}_{2n}\to\\{-1,0,1\\}$ as follows:

$\chi_{t}=\sum_{\pi\in C(t)}(-1)^{\pi}e_{t^{\pi}}.$

These functions span $V^{2\lambda}$.

######  Theorem 2.14 ([Lin18b, Theorem 5.2.6]).

Let $\lambda\vdash n$. The subspace $V^{2\lambda}$ is spanned by the functions
$\chi_{t}$, where $t$ goes over all Young tableaux of shape $2\lambda$.

We can now prove Lemma 2.13. The proof is along the lines of Lemma 2.6.

###### Proof of Lemma 2.13.

Assume, for concreteness, that $i=2n-1$ and $j=2n$. If $n=1$ then $\deg
f|_{[2n-1\leftrightarrow 2n]}=0$, so there is nothing to prove. Similarly, if
$f|_{[2n-1\leftrightarrow 2n]}=0$ then there is nothing to prove. Therefore we
can assume that $n\geq 2$ and that $f|_{[2n-1\leftrightarrow 2n]}\neq 0$.

Let $d=degf|_{[2n-1\leftrightarrow 2n]}$. According to the spectral definition
of degree (see Section 2.2.1), $f|_{[2n-1\leftrightarrow 2n]}^{=\lambda}\neq
0$ for some $\lambda\vdash n-1$ such that $\lambda_{1}=(n-1)-d$. Since the
decomposition into isotypic components is orthogonal, Theorem 2.14 implies
that $\langle f|_{[2n-1\leftrightarrow 2n]},\chi_{t}\rangle\neq 0$ for some
Young tableau $t$ of shape $2\lambda$. Among all tableau $t$ with $2(n-1-d)$
squares on the first lines satisfying $\langle f|_{[2n-1\leftrightarrow
2n]},\chi_{t}\rangle\neq 0$, we choose one which maximizes the number of rows
(which is the number of parts in the corresponding partition), say $t$ has $R$
rows.

Let $t^{\prime}$ be the Young tableau obtained by adding a new row to $t$
consisting only of the numbers $2n-1,2n$. The tableau $t^{\prime}$ has shape
$\mu$ satisfying $\mu_{1}=\lambda_{1}=n-(d+1)$. We will show that $\langle
f,\chi_{t^{\prime}}\rangle\neq 0$, and so $\deg f\geq d+1$ by the spectral
definition of degree.

If $\pi^{\prime}\in C(t^{\prime})$ is any permutation such that $2n-1,2n$ do
not end up in the same row, then $\langle
f,e_{(t^{\prime})^{\pi^{\prime}}}\rangle=0$, since
$e_{(t^{\prime})^{\pi^{\prime}}}(m)\neq 0$ implies that $m(2n-1)\neq 2n$, and
so $f(m)=0$. Therefore

$\langle
f,\chi_{t^{\prime}}\rangle=\sum_{r=1}^{R+1}\sum_{\begin{subarray}{c}\pi^{\prime}\in
C(t^{\prime})\\\ 2n-1,2n\text{ are on}\\\ \text{row $r$ of
$(t^{\prime})^{\pi^{\prime}}$}\end{subarray}}(-1)^{\pi^{\prime}}\langle
f,e_{(t^{\prime})^{\pi^{\prime}}}\rangle.$

For $r\leq R$, let $t^{r}$ be the tableau obtained from $t$ by taking the
first two elements of row $r$, moving them to a new row at then very end,
removing row $r$ if it is empty, and otherwise sliding the remainder of row
$r$ to the left. For example:

$t=\ytableaushort{1234,56,78}\quad t^{1}=\ytableaushort{34,56,78,12}\quad
t^{2}=\ytableaushort{1234,78,56}\quad t^{3}=t$

We also define $t^{R+1}=t$. Observe that

$\langle f,\chi_{t^{\prime}}\rangle=\sum_{r=1}^{R+1}\sum_{\pi\in
C(t^{r})}(-1)^{\pi}\langle f|_{[2n-1\leftrightarrow
2n]},e_{(t^{r})^{\pi}}\rangle=\sum_{r}\langle f|_{[2n-1\leftrightarrow
2n]},\chi_{t^{r}}\rangle.$

If the $r$-th row of $t$ contains more than two elements then $t^{r}$ contains
more rows than $t$, and so by the choice of $t$, we have $\langle
f|_{[2n-1\leftrightarrow 2n]},\chi_{t^{r}}\rangle=0$. Otherwise,
$\chi_{t^{r}}$ differs from $\chi_{t}$ by an identical permutation of the
first two columns, and so $\langle f|_{[2n-1\leftrightarrow
2n]},\chi_{t^{r}}\rangle=\langle f|_{[2n-1\leftrightarrow
2n]},\chi_{t}\rangle$. Therefore, denoting by $\ell$ the number of rows of $t$
of length $2$, we have

$\langle f,\chi_{t^{\prime}}\rangle=(\ell+1)\langle f|_{[2n-1\leftrightarrow
2n]},\chi_{t}\rangle\neq 0.$

The reason we get $\ell+1$ rather than $\ell$ is the choice $r=R+1$, which
always leads to $t^{R+1}=t$. ∎

##  3 Main theorem: symmetric group

###  3.1 Structure theorem

We start with a simple observation on $2$-intersecting families, whose
statement requires a few definitions.

Two cosets $[i_{1}\mapsto j_{1}],[i_{2}\mapsto j_{2}]$ are _compatible_ if
their intersection is non-empty. In other words, either the two cosets are
equal, or $i_{1}\neq i_{2}$ and $j_{1}\neq j_{2}$. A family
$\mathcal{F}\subseteq S_{n}$ is _$m$ -covered_, for some integer $m\geq 1$, if
there are $m$ compatible cosets $[i_{1}\mapsto j_{1}],\ldots,[i_{m}\mapsto
j_{m}]$ such that $\mathcal{F}\subseteq[i_{1}\mapsto
j_{1}]\cup\cdots\cup[i_{m}\mapsto j_{m}]$.

######  Lemma 3.1.

Let $f$ be the characteristic function of a $2$-intersecting family
$\mathcal{F}\subseteq S_{n}$, and suppose that $C(f)\leq n-2$.

If $\alpha\in\mathcal{F}$ then $\mathcal{F}$ is $m$-covered for
$m=C(f,\alpha)-1$.

###### Proof.

Let $C_{\alpha}=\\{(i_{1},j_{1}),\ldots,(i_{m+1},j_{m+1})\\}$ be a minimal
certificate for $\alpha$. We will show that $\mathcal{F}\subseteq[i_{1}\mapsto
j_{1}]\cup\cdots\cup[i_{m}\mapsto j_{m}]$.

Suppose that $\beta\in\mathcal{F}$, and let $C_{\beta}$ be a minimal
certificate for $\beta$. According to Lemma 2.4, $|C_{\alpha}\cap
C_{\beta}|\geq 2$. Therefore $(i_{s},j_{s})\in C_{\beta}$ for some $s\in[m]$,
implying that $\beta\in[i_{s}\mapsto j_{s}]\subseteq[i_{1}\mapsto
j_{1}]\cup\cdots\cup[i_{m}\mapsto j_{m}]$. ∎

The following structure lemma provides a kind of converse to Lemma 3.1.

######  Lemma 3.2.

Let $\mathcal{F}\subseteq S_{n}$ be an $m$-covered family, say
$\mathcal{F}\subseteq[i_{1}\mapsto j_{1}]\cup\cdots\cup[i_{m}\mapsto j_{m}]$.
Suppose that its characteristic function $f$ has degree at most $2$.

Every $\alpha$ has a certificate of the form
$\\{(i_{1},\alpha(i_{1})),\ldots,(i_{m},\alpha(i_{m})),(i,j)\\}$, and in
particular, $C(f)\leq m+1$.

###### Proof.

We will prove by induction on $m$ that if $\mathcal{F}\subseteq S_{n}$ is
$m$-covered, say $\mathcal{F}\subseteq[i_{1}\mapsto
j_{1}]\cup\cdots\cup[i_{m}\mapsto j_{m}]$, and its characteristic function $f$
has degree at most $2$, then for every distinct $k_{1},\ldots,k_{m}\in[n]$,
the restriction of $f$ to $[i_{1}\mapsto k_{1}]\cap\cdots\cap[i_{m}\mapsto
k_{m}]$ has degree at most $1$. By Lemma 2.3, this restriction has certificate
complexity at most $1$. For any $\alpha\in S_{n}$, choosing
$k_{1}=\alpha(i_{1}),\ldots,k_{m}=\alpha(i_{m})$, we deduce that $\alpha$ has
a certificate of the required form.

We start with the base case $m=1$. Let $\mathcal{F}\subseteq S_{n}$ be such
that $\mathcal{F}\subseteq[i_{1}\mapsto j_{1}]$, and suppose that its
characteristic function $f$ has degree at most $2$. Lemma 2.6 directly implies
that the restriction of $f$ to $[i_{1}\mapsto j_{1}]$ has degree at most $1$,
as required.

Suppose now that $m\geq 2$. Let $\mathcal{F}\subseteq S_{n}$ be such that
$\mathcal{F}\subseteq[i_{1}\mapsto j_{1}]\cup\cdots\cup[i_{m}\mapsto j_{m}]$,
and suppose that its characteristic function $f$ has degree at most $2$.
Consider any distinct $k_{1},\ldots,k_{m}\in[n]$. We need to show that the
restriction of $f$ to $[i_{1}\mapsto k_{1}]\cap\cdots\cap[i_{m}\mapsto k_{m}]$
has degree at most $1$.

Suppose first that $k_{s}\neq j_{s}$ for some $s\in[m]$, say $k_{m}\neq
j_{m}$. The restriction of $\mathcal{F}$ to $[i_{m}\mapsto k_{m}]$ is
contained in $[i_{1}\mapsto j_{1}]\cup\cdots\cup[i_{m-1}\mapsto j_{m-1}]$, and
its characteristic function has degree at most $2$. Therefore the induction
hypothesis implies that the restriction of $f$ to $[i_{1}\mapsto
k_{1}]\cap\cdots\cap[i_{m}\mapsto k_{m}]$ has degree at most $1$.

It remains to show that the restriction of $f$ to $[i_{1}\mapsto
j_{1}]\cap\cdots\cap[i_{m}\mapsto j_{m}]$ has degree at most $1$. To see this,
consider the function

$g:=x_{i_{1}j_{1}}\cdots
x_{i_{m}j_{m}}f=f-\sum_{\begin{subarray}{c}k_{1},\ldots,k_{m}\\\
(k_{1},\ldots,k_{m})\neq(j_{1},\ldots,j_{m})\end{subarray}}x_{i_{1}k_{1}}\cdots
x_{i_{m}k_{m}}f.$

We showed above that the restriction of $f$ to $[i_{1}\mapsto
k_{1}]\cap\cdots\cap[i_{m}\mapsto k_{m}]$ has degree at most $1$ whenever
$(k_{1},\ldots,k_{m})\neq(j_{1},\ldots,j_{m})$. Therefore every term in the
sum on the right-hand side has degree at most $m+1$, since it can be
represented as $x_{i_{1}k_{1}}\cdots x_{i_{m}k_{m}}$ times the linear
polynomial representing the restriction of $f$ to $[i_{1}\mapsto
k_{1}]\cap\cdots\cap[i_{m}\mapsto k_{m}]$. Consequently, $\deg g\leq\max(\deg
f,m+1)=m+1$.

By construction, $g$ is the characteristic function of a family which is
contained in the coset intersection $\mathcal{I}=[i_{1}\mapsto
j_{1}]\cap\cdots\cap[i_{m}\mapsto j_{m}]$. Applying Lemma 2.6 repeatedly, we
conclude that the restriction of $g$ to $\mathcal{I}$ has degree at most
$\max(m+1-m,0)=1$. Since the restriction of $f$ to $\mathcal{I}$ is the same
as the restriction of $g$ to $\mathcal{I}$, this completes the proof of the
induction step. ∎

###  3.2 Proof of main theorem

We are now ready to prove our main upper bound, from which Theorem 1.3 will
quickly follow.

######  Lemma 3.3.

Let $\mathcal{F}\subseteq S_{n}$ be a $2$-intersecting family whose
characteristic function $f$ has degree at most $2$. Suppose that $C(f)\leq
n-2$.

The family $\mathcal{F}$ is contained in the union of at most $T$ many
$C(f)$-cosets, where

$T=\frac{2\lfloor C(f)/2\rfloor(C(f)-1)!}{2^{\lfloor C(f)/2\rfloor}}.$

Moreover, $C(f)\geq 2$.

###### Proof.

If $\mathcal{F}$ is empty then the lemma is vacuously true. Otherwise, choose
an arbitrary $\beta\in\mathcal{F}$. Lemma 2.4, applied to $\alpha=\beta$,
shows that $C(f,\beta)\geq 2$. Lemma 3.1 shows that $\mathcal{F}$ is
$m$-covered, where $m=C(f,\beta)-1$. Without loss of generality, we can assume
that $\mathcal{F}\subseteq[1\mapsto 1]\cup\cdots\cup[m\mapsto m]$.

Lemma 3.2 shows that $C(f)\leq m+1$, and so $m=C(f)-1$ and
$C(f)=C(f,\beta)\geq 2$. The Lemma also shows that every
$\alpha\in\mathcal{F}$ has a certificate $C_{\alpha}$ of the form
$\\{(1,\alpha(1)),\ldots,(m,\alpha(m)),(i,j)\\}$. It also implies that
$\mathcal{F}$ is not $(m-1)$-covered (otherwise its certificate complexity
would be at most $m<C(f)$). Therefore, if $X$ is any set of at most $m-1$
compatible cosets, then there is $\alpha_{X}\in\mathcal{F}$ which is not
contained in the union of the cosets in $X$. Fix a certificate $C_{X}$ for
$\alpha_{X}$ of the form
$\\{(1,\alpha_{X}(1)),\ldots,(m,\alpha_{X}(m)),(i_{X},j_{X})\\}$.

We think of the certificates $C_{\alpha},C_{X}$ as colored using $m+1$ colors:
for $k\in[m]$, a pair $(k,\ast)$ is colored $k$, and the remaining pair
$(i,j)$ is colored $m+1$. We can determine the color of a pair
$(i^{\prime},j^{\prime})$ given only the pair: if $i^{\prime}\in[m]$ then the
color is $i^{\prime}$, and otherwise the color is $m+1$.

We will prove the lemma by showing that if $\alpha\in\mathcal{F}$ then
$C_{\alpha}$ is one of at most $T$ possible certificates. Since $C_{\alpha}$
corresponds to a $C(f)$-coset containing $\alpha$, the lemma would follow. In
the proof, we will freely identify a pair $(i,j)$ with the corresponding coset
$[i\mapsto j]$, and from now on we will only ever mention cosets.

The proof is slightly different depending on the parity of $C(f)$. We start
with the case in which $C(f)=2r$ is even. Let $\alpha\in\mathcal{F}$. We
define a sequence $X_{0}\subset\cdots\subset X_{r}\subseteq C_{\alpha}$, where
$X_{s}$ is a collection of $2s$ compatible cosets, as follows. The starting
point is $X_{0}=\emptyset$. Now let $s<r$, and suppose that $X_{s}$ has been
defined. Since $|X_{s}|=2s\leq C(f)-2=m-1$, there is a permutation
$\alpha_{X_{s}}\in\mathcal{F}$ which lies outside of the union of the cosets
in $X_{s}$. According to Lemma 2.4, the certificates $C_{\alpha}$ and
$C_{X_{s}}$ must have at least two cosets in common $q_{1},q_{2}$. The choice
of $\alpha_{X_{s}}$ guarantees that $q_{1},q_{2}\notin X_{s}$, and we define
$X_{s+1}=X_{s}\cup\\{q_{1},q_{2}\\}$. By construction, $X_{s+1}\subseteq
C_{\alpha}$, and so the cosets in $X_{s+1}$ are indeed compatible.

Note that $|X_{r}|=2r=|C_{\alpha}|$, and so $X_{r}=C_{\alpha}$. For $s<r$,
given $X_{s}$, the set $X_{s+1}\setminus X_{s}$ consists of two cosets
belonging to $C_{X_{s}}$. Moreover, since $X_{s+1}\subseteq C_{\alpha}$ and
$C_{\alpha}$ contains one coset of each color, the colors of the two cosets in
$X_{s+1}\setminus X_{s}$ are different from the colors of the cosets in
$X_{s}$. Since $C_{X_{s}}$ also contains one coset of each color, this means
that there are $\binom{|C_{X_{s}}|-|X_{s}|}{2}=\binom{C(f)-2s}{2}$ choices for
$X_{s+1}\setminus X_{s}$. In total, the number of possible choices for
$C_{\alpha}$ is

$\prod_{s=0}^{r-1}\binom{C(f)-2s}{2}=\frac{C(f)!}{2^{r}},$

matching the formula for $T$ in the statement of the lemma.

Now suppose that $C(f)=2r+1$ is odd. Let $\alpha\in\mathcal{F}$. We define a
sequence $X_{0}\subset\cdots\subset X_{r}\subseteq C_{\alpha}$, where $X_{s}$
is a collection of $2s+1$ compatible cosets, as follows. We start by defining
$X_{0}$. According to Lemma 2.4, the certificates $C_{\alpha}$ and
$C_{\emptyset}$ must contain at least two cosets in common $q_{1},q_{2}$. At
least one of these cosets is of the form $(k,\alpha(k))$ for some $k\in[m]$.
We define $X_{0}=\\{(k,\alpha(k))\\}$. Now let $s<r$, and suppose that $X_{s}$
has been defined. Since $|X_{s}|=2s+1\leq C(f)-2=m-1$, we can define $X_{s+1}$
as in the case of even $C(f)$.

Note that $|X_{r}|=2r+1=|C_{\alpha}|$, and so $X_{r}=C_{\alpha}$. The
certificate $X_{0}$ contains a single coset $(k,\ell)\in C_{\emptyset}$, where
$k\in[m]$, and so there are $m=C(f)-1$ choices for $X_{0}$. For $s<r$, given
$X_{s}$, there are $\binom{|C_{X_{s}}|-|X_{s}|}{2}=\binom{C(f)-2s-1}{2}$
choices for $X_{s+1}$ (this is the same as in the case of even $C(f)$). In
total, the number of possible choices for $C_{\alpha}$ is

$(C(f)-1)\prod_{s=0}^{r-1}\binom{C(f)-2s-1}{2}=(C(f)-1)\frac{(C(f)-1)!}{2^{r}},$

matching the formula for $T$ in the statement of the lemma. ∎

We can now prove Theorem 1.3.

###### Proof of Theorem 1.3.

Let $\mathcal{F}$ be a $2$-intersecting subset of $S_{n}$ of size $(n-2)!$,
where $n\geq 2$, and let $f$ be its characteristic function. Our goal is to
show that

$\mathcal{F}=\\{\alpha\in S_{n}:\alpha(i_{1})=j_{1}\text{ and
}\alpha(i_{2})=j_{2}\\}$

for some $i_{1}\neq i_{2}\in[n]$ and $j_{1}\neq j_{2}\in[n]$. In other words,
we need to show that $\mathcal{F}$ is a $2$-coset.

Suppose first that $n\geq 8$. Since $n\geq 5$, Theorem 2.1 shows that $\deg
f\leq 2$. Lemma 2.5 shows that $C(f)\leq n-2$. Lemma 3.3 implies that
$C(f)\geq 2$ and $|\mathcal{F}|\leq T(n-C(f))!$, where $T=\lfloor
C(f)/2\rfloor(C(f)-1)!/2^{\lfloor C(f)/2\rfloor}$. Therefore

$\frac{(n-2)!}{(n-C(f))!}\leq\frac{2\lfloor C(f)/2\rfloor(C(f)-1)!}{2^{\lfloor
C(f)/2\rfloor}}.$

The left-hand side is clearly increasing in $n$. Since $n\geq C(f)+2$, it
follows that

$\frac{C(f)!}{2}\leq\frac{2\lfloor C(f)/2\rfloor(C(f)-1)!}{2^{\lfloor
C(f)/2\rfloor}},$

and so

$C(f)\leq\frac{2\lfloor C(f)/2\rfloor}{2^{\lfloor C(f)/2\rfloor-1}}.$

If $C(f)=2r$ is even then this reads $2r\leq 2r/2^{r-1}$, and so $r=1$. If
$C(f)=2r+1$ is odd then this reads $2r+1\leq 2r/2^{r-1}$, which never holds.
We conclude that $C(f)=2$.

Let $\alpha\in\mathcal{F}$ be arbitrary. Since $C(f)=2$, there is a
certificate of the form $\\{(i_{1},j_{1}),(i_{2},j_{2})\\}$ for $\alpha$. The
number of permutations satisfying this certificate is $(n-2)!$, and we
conclude that $\mathcal{F}$ consists of all permutations satisfying the
certificate, completing the proof in this case.

In order to complete the proof, we consider the case $n\leq 7$. It suffices to
show that for $n\in\\{2,3,4,5,6,7\\}$, any $2$-intersecting family of size
$(n-2)!$ which contains the identity permutation is of the form

$\\{\alpha\in S_{n}:\alpha(i_{1})=i_{1},\alpha(i_{2})=i_{2}\\}$

for some $i_{1}\neq i_{2}$.

If $n=2$ or $n=3$ then $(n-2)!=1$, and the claim can be verified directly. In
order to verify the remaining cases $n\in\\{4,5,6,7\\}$, we formulate the task
as a maximum clique problem. Let $G_{n}$ be the graph whose vertex set
consists of all permutations which $2$-intersect the identity permutation, and
in which two permutations are connected if they $2$-intersect. A
$2$-intersecting family containing the identity permutation is the same as a
clique in $G_{n}$. Using SAGE [Sag22], which internally uses the software
library Cliquer [NÖ03], we verify that a maximum clique in $G_{n}$ contains
$(n-2)!$ many permutations, and furthermore, there are exactly $\binom{n}{2}$
many maximum cliques, matching the number of $2$-cosets containing the
identity permutation. The relevant code appears in Section A.2. This completes
the proof. ∎

##  4 Main theorem: perfect matching scheme

The proof of Theorem 1.4 is similar to that of Theorem 1.3, but there is an
additional complication: Lemma 2.10 only states that degree $1$ Boolean
functions have certificate complexity $2$. This causes the proof of Lemma 3.2
to fail. In order to get around this, we show that the bad case never occurs
for _(inclusion-)maximal_ $2$-intersecting families.

Fix $n\geq 1$, and work over $\mathcal{M}_{2n}$. We start by defining
_extended certificates_. An extended certificate of size $c$ is either a
standard certificate of size $c$, or a pair $(C^{\prime},\\{i,j,k\\})$, where
$C^{\prime}$ is a certificate of size $c-1$ and $i,j,k\in[2n]$ are distinct
elements not appearing in $C^{\prime}$. A perfect matching
$m\in\mathcal{M}_{2n}$ satisfies a certificate $(C^{\prime},\\{i,j,k\\})$ if
it satisfies $C^{\prime}$ and doesn’t contain any of the pairs
$\\{i,j\\},\\{i,k\\},\\{j,k\\}$.

######  Lemma 4.1.

Fix $n\geq 1$, work over $\mathcal{M}_{2n}$, and let $c\leq n-2$. Let
$C_{1}=(C^{\prime}_{1},\\{i,j,k\\})$ be an extended certificate of size $c$,
and let $C_{2}$ be an extended certificate of size $c$. If any perfect
matching satisfying $C_{1}$ and any perfect matching satisfying $C_{2}$ are
$2$-intersecting, then the same holds when $C_{1}$ is replaced by
$C^{\prime}_{1}$.

###### Proof.

Suppose that $m_{1}$ is a perfect matching satisfying $C^{\prime}_{1}$ but not
$C_{1}$. Without loss of generality, $m_{1}(i)=j$. We need to show that if
$m_{2}$ is a perfect matching satisfying $C_{2}$ then $m_{1}$ and $m_{2}$ are
$2$-intersecting.

Since $m_{1}$ satisfies $C_{1}$, its pair representation consists of $C_{1}$
together with $n-(c-1)\geq 3$ more pairs, one of which is $\\{i,j\\}$. Among
the other pairs, at least one $\\{a,b\\}$ does not involve $k$. Consider the
following two perfect matchings:

$\displaystyle m^{\prime}_{1}$
$\displaystyle=m_{1}\setminus\bigl{\\{}\\{i,j\\},\\{a,b\\}\bigr{\\}}\cup\bigl{\\{}\\{i,a\\},\\{j,b\\}\bigr{\\}},$
$\displaystyle m^{\prime\prime}_{1}$
$\displaystyle=m_{1}\setminus\bigl{\\{}\\{i,j\\},\\{a,b\\}\bigr{\\}}\cup\bigl{\\{}\\{i,b\\},\\{j,a\\}\bigr{\\}}.$

Both of these perfect matchings avoid the edges
$\\{i,j\\},\\{i,k\\},\\{j,k\\}$. If $m_{2}$ contains $\\{i,a\\}$ then it
cannot contain $\\{i,b\\}$ or $\\{j,a\\}$, and similarly for
$\\{j,b\\},\\{i,b\\},\\{j,a\\}$. Therefore $m_{2}$ cannot intersect both
$\bigl{\\{}\\{i,a\\},\\{j,b\\}\bigr{\\}}$ and
$\bigl{\\{}\\{i,b\\},\\{j,a\\}\bigr{\\}}$. Suppose that $m_{2}$ does not
intersect $\bigl{\\{}\\{i,a\\},\\{j,b\\}\bigr{\\}}$. Then $m^{\prime}_{1}\cap
m_{2}\subseteq m_{1}\cap m_{2}$. On the other hand, $m^{\prime}_{1}$ satisfies
$C_{1}$, and so $|m^{\prime}_{1}\cap m_{2}|\geq 2$. We conclude that
$|m_{1}\cap m_{2}|\geq 2$, as needed. ∎

###  4.1 Structure theorem

Two cosets $[i_{1}\leftrightarrow j_{1}],[i_{2}\leftrightarrow j_{2}]$ are
_compatible_ if their intersection is non-empty. A family is _$r$ -covered_ if
it is contained in the union of $r$ compatible cosets.

######  Lemma 4.2.

Let $f$ be the characteristic function of a $2$-intersecting family
$\mathcal{F}\subseteq\mathcal{M}_{2n}$, and suppose that $C(f)\leq n-2$.

If $m\in\mathcal{F}$ then $\mathcal{F}$ is $r$-covered for $r=C(f,m)-1$.

Since the proof is identical to that of Lemma 3.1 (with Lemma 2.11 standing
for Lemma 2.4), we omit it.

The following structure theorem is the analog of Lemma 3.2. There are three
differences in the statement. First, we assume that $\mathcal{F}$ is _maximal_
: it is not properly contained in any larger $2$-intersecting family. Second,
we assume that $r\leq n-2$. Third, we only provide certificates to perfect
matchings which belong to $\mathcal{F}$.

######  Lemma 4.3.

Let $\mathcal{F}\subseteq\mathcal{M}_{2n}$ be an $r$-covered family, say
$\mathcal{F}\subseteq[i_{1}\leftrightarrow
j_{1}]\cup\cdots\cup[i_{r}\leftrightarrow j_{r}]$, where $r\leq n-3$. Suppose
that $\mathcal{F}$ is maximal, and that its characteristic function $f$ has
degree at most $2$.

Every $m\in\mathcal{F}$ has a certificate of the form
$\bigl{\\{}\\{i_{1},m(i_{1})\\},\ldots,\\{i_{r},m(i_{r})\\},\\{i,j\\}\bigr{\\}}$.

Note that the certificate could mention the same pair twice, for example if
$m(i_{1})=i_{2}$.

###### Proof.

The first step is to prove that for every distinct $k_{1},\ldots,k_{r}$, the
restriction of $f$ to $[i_{1}\leftrightarrow
k_{1}]\cap\cdots\cap[i_{r}\leftrightarrow k_{r}]$ has degree at most $1$,
assuming the coset intersection is non-empty. This part is identical to the
proof of Lemma 3.2, so we do not repeat it here (the only difference is that
we never consider $k_{1},\ldots,k_{r}$ such that the coset intersection is
empty).

Now suppose that $m\in\mathcal{F}$. Then the restriction of $f$ to
$I=[i_{1}\leftrightarrow m(i_{1})]\cap\cdots\cap[i_{r}\leftrightarrow
m(i_{r})]$ (which is non-empty) has degree $1$. According to Theorem 2.9,
$f|_{I}$ is either a dictator, a triangle, or an anti-triangle. If $f|_{I}$ is
a dictator or a triangle, then $m|_{I}$ has a certificate of size $1$, and we
are done. We would like to show that the remaining case is impossible.

Suppose that $f|_{I}$ is an anti-triangle. Then $m$ has an extended
certificate $(C^{\prime},\\{i,j,k\\})$ of size $r+1\leq n-2$. The same
argument shows that every perfect matching in $\mathcal{F}$ has an extended
certificate of size $r+1\leq n-2$. Therefore Lemma 4.1 implies that if
$m^{\prime}\notin\mathcal{F}$ is a perfect matching satisfying $C^{\prime}$,
then $\mathcal{F}\cup\\{m^{\prime}\\}$ is also $2$-intersecting. Hence either
$\mathcal{F}$ is not maximal (if such $m^{\prime}\notin\mathcal{F}$ exists),
or in fact $C^{\prime}$ is already a certificate for $m$. ∎

###  4.2 Proof of main theorem

We can now prove the analog of Lemma 3.3, from which Theorem 1.4 will easily
follow. The only difference in the statement is the additional assumption that
$\mathcal{F}$ is maximal.

######  Lemma 4.4.

Let $\mathcal{F}\subseteq\mathcal{M}_{2n}$ be a maximal $2$-intersecting
family whose characteristic function $f$ has degree at most $2$, and suppose
that $C(f)\leq n-2$. Let $C_{1}(f)$ the maximum certificate complexity of any
$m\in\mathcal{F}$.

The family $\mathcal{F}$ is contained in the union of at most $T$ many
$C_{1}(f)$-cosets, where

$T=\frac{2\lfloor C_{1}(f)/2\rfloor(C_{1}(f)-1)!}{2^{\lfloor
C_{1}(f)/2\rfloor}}.$

Moreover, $C_{1}(f)\geq 2$.

###### Proof.

Let $\mu\in\mathcal{F}$ be a perfect matching satisfying $C(f,\mu)=C_{1}(f)$.
Lemma 2.11, applied to $m_{1}=m_{2}=\mu$, shows that $C(f,\mu)\geq 2$, and so
$C_{1}(f)\geq 2$. Lemma 4.2 shows that $\mathcal{F}$ is $r$-covered, where
$r=C(f,\mu)-1$. Note that $r\leq C(f)-1\leq n-3$. Without loss of generality,
we can assume that $\mathcal{F}\subseteq[1\leftrightarrow
r+1]\cup[2\leftrightarrow r+2]\cup\cdots\cup[r\leftrightarrow 2r]$.

Lemma 4.3 shows that every $m\in\mathcal{F}$ has a certificate of the form
$\bigl{\\{}\\{1,m(1)\\},\ldots,\\{r,m(r)\\},\\{i,j\\}\bigr{\\}}$, which we
call the _standard certificate_. The Lemma also implies that $\mathcal{F}$ is
not $(r-1)$-covered: otherwise, every perfect matching in $\mathcal{F}$ would
have a certificate of size $r<C_{1}(f)$, which contradicts the definition of
$C_{1}(f)$.

A standard certificate
$\bigl{\\{}\\{1,m(1)\\},\ldots,\\{r,m(r)\\},\\{i,j\\}\bigr{\\}}$ satisfies
$m(1),\ldots,m(r)\notin[r]$, since otherwise Lemma 4.3 would imply that
$\mathcal{F}$ is $(r-1)$-covered (since some of the pairs $\\{t,m(t)\\}$
coincide), which is impossible. This allows us to color the pairs in a
standard certificate unambiguously: a pair $\\{t,m(t)\\}$ is colored $t$, and
a pair $\\{i,j\\}$ with $i,j\notin[r]$ is colored $r+1$. Every standard
certificate contains exactly one pair of each color.

The remainder of the proof is identical to that of Lemma 3.3. ∎

We can now prove Theorem 1.4. The proof is very similar to that of Theorem
1.3.

###### Proof of Theorem 1.4.

Let $\mathcal{F}$ be a $2$-intersecting subset of $\mathcal{M}_{2n}$ of size
$(2n-5)!!$, where $n\geq 2$, and let $f$ be its characteristic function. Our
goal is to show that

$\mathcal{F}=\\{m\in\mathcal{M}_{2n}:m(i_{1})=j_{1}\text{ and
}m(i_{2})=j_{2}\\}$

for some distinct $i_{1},j_{1},i_{2},j_{2}\in[2n]$.

Suppose first that $n\geq 8$. Since $n\geq 3$, Theorem 2.8 shows that
$\mathcal{F}$ is maximal and that $\deg f\leq 2$. Lemma 2.12 shows that
$C_{1}(f)\leq n-2$. Lemma 4.4 implies that $C_{1}(f)\geq 2$ and
$|\mathcal{F}|\leq T(2n-2C_{1}(f)-1)!!$, where $T=\lfloor
C_{1}(f)/2\rfloor(C_{1}(f)-1)!/2^{\lfloor C_{1}(f)/2\rfloor}$. Therefore

$\frac{(2n-5)!!}{(2n-2C_{1}(f)-1)!!}\leq\frac{2\lfloor
C_{1}(f)/2\rfloor(C_{1}(f)-1)!}{2^{\lfloor C_{1}(f)/2\rfloor}}.$

The left-hand side is clearly increasing in $n$. Since $n\geq C_{1}(f)+2$, it
follows that

$\frac{(2C_{1}(f))!}{3\cdot
2^{C_{1}(f)}C_{1}(f)!}=\frac{(2C_{1}(f)-1)!!}{3}\leq\frac{2\lfloor
C_{1}(f)/2\rfloor(C_{1}(f)-1)!}{2^{\lfloor C_{1}(f)/2\rfloor}},$

and so

$(2C_{1}(f))!\leq 3\cdot 2^{\lceil C_{1}(f)/2\rceil}C_{1}(f)!(2\lfloor
C_{1}(f)/2\rfloor)(C_{1}(f)-1)!.$

If $C_{1}(f)$ is even then this reads

$(2C_{1}(f))!\leq 3\cdot 2^{C_{1}(f)/2}C_{1}(f)!^{2}.$

When $C=C_{1}(f)$ increases by $1$, the left-hand side increases by a factor
of $(2C+2)(2C+1)$, while the right-hand side increases by a factor of
$\sqrt{2}(C+1)^{2}$, which is smaller for $C\geq 2$. When $C=3$, the
inequality fails. Therefore in this case, $C_{1}(f)=2$.

If $C_{1}(f)$ is odd then the inequality reads

$(2C_{1}(f))!\leq 3\cdot
2^{(C_{1}(f)+1)/2}C_{1}(f)!(C_{1}(f)-1)(C_{1}(f)-1)!<3\cdot
2^{(C_{1}(f)+1)/2}C_{1}(f)!^{2}.$

As before, if we increase $C=C_{1}(f)$ by $1$, the left-hand side increases by
a larger factor than the (far) right-hand side. When $C=3$, the inequality
fails, and so this case cannot happen.

Now let $m\in\mathcal{F}$ be arbitrary. Since $C_{1}(f)=2$, there is a
certificate of the form
$\bigl{\\{}\\{i_{1},j_{1}\\},\\{i_{2},j_{2}\\}\bigr{\\}}$ for $m$. The number
of permutations satisfying this certificate is $(2n-5)!!$, and we conclude
that $\mathcal{F}$ consists of all perfect matchings satisfying the
certificate, completing the proof in this case.

In order to complete the proof, we consider the case $n\leq 7$. It suffices to
show that for $n\in\\{2,3,4,5,6,7\\}$, any $2$-intersecting family of size
$(2n-5)!!$ which contains the perfect matching $\\{1,n+1\\},\ldots,\\{n+2n\\}$
is of the form

$\\{m\in\mathcal{M}_{2n}:m(i_{1})=n+i_{1},m(i_{2})=n+i_{2}\\}$

for some $i_{1}\neq i_{2}\in[n]$.

If $n=2$ or $n=3$ then $(2n-5)!!=1$, and the claim can be verified directly.
In order to verify the remaining cases $n\in\\{4,5,6,7\\}$, we use exhaustive
search just as in the proof of Theorem 1.3. The relevant code appears in
Section A.3. ∎

## References

  * [AK97] Rudolf Ahlswede and Levon H. Khachatrian.  The complete intersection theorem for systems of finite sets.  European J. Combin., 18(2):125–136, 1997.
  * [AK99] Rudolf Ahlswede and Levon H. Khachatrian.  A pushing-pulling method: new proofs of intersection theorems.  Combinatorica, 19(1):1–15, 1999.
  * [BdW02] Harry Buhrman and Ronald de Wolf.  Complexity measures and decision tree complexity: a survey.  Theoret. Comput. Sci., 288(1):21–43, 2002.  Complexity and logic (Vienna, 1998).
  * [BMRR21] Angelot Behajaina, Roghayeh Maleki, Aina Toky Rasoamanana, and A. Sarobidy Razafimahatratra.  3-setwise intersecting families of the symmetric group.  Discrete Math., 344(8):Paper No. 112467, 15, 2021.
  * [CK03] Peter J. Cameron and C. Y. Ku.  Intersecting families of permutations.  European J. Combin., 24(7):881–890, 2003.
  * [CSST08] Tullio Ceccherini-Silberstein, Fabio Scarabotti, and Filippo Tolli.  Harmonic analysis on finite groups, volume 108 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, 2008.  Representation theory, Gelfand pairs and Markov chains.
  * [Daf22] Neta Dafni.  Complexity measures on the symmetric group and beyond.  Master’s thesis, Technion — Israel Institute of Technology, 2022.
  * [DFL+21] Neta Dafni, Yuval Filmus, Noam Lifshitz, Nathan Lindzey, and Marc Vinyals.  Complexity measures on the symmetric group and beyond.  In 12th Innovations in Theoretical Computer Science Conference, volume 185 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 87, 5. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2021.
  * [EFP11] David Ellis, Ehud Friedgut, and Haran Pilpel.  Intersecting families of permutations.  J. Amer. Math. Soc., 24(3):649–682, 2011.
  * [EKR61] P. Erdős, Chao Ko, and R. Rado.  Intersection theorems for systems of finite sets.  Quart. J. Math. Oxford Ser. (2), 12:313–320, 1961.
  * [Ell12a] David Ellis.  A proof of the Cameron-Ku conjecture.  J. Lond. Math. Soc. (2), 85(1):165–190, 2012.
  * [Ell12b] David Ellis.  Setwise intersecting families of permutations.  J. Combin. Theory Ser. A, 119(4):825–849, 2012.
  * [FD77] Péter Frankl and Mikhail Deza.  On the maximum number of permutations with given maximal or minimal distance.  J. Combinatorial Theory Ser. A, 22(3):352–360, 1977.
  * [FHKL16] Yuval Filmus, Hamed Hatami, Nathan Keller, and Noam Lifshitz.  On the sum of the $L_{1}$ influences of bounded functions.  Israel J. Math., 214(1):167–192, 2016.
  * [Fil17] Yuval Filmus.  A comment on intersecting families of permutations.  arXiv:1706.10146, 2017.
  * [FMS21] Shaun Fallat, Karen Meagher, and Mahsa N. Shirazi.  The Erdős-Ko-Rado theorem for 2-intersecting families of perfect matchings.  Algebr. Comb., 4(4):575–598, 2021.
  * [GM09] Chris Godsil and Karen Meagher.  A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations.  European J. Combin., 30(2):404–414, 2009.
  * [GM16] Chris Godsil and Karen Meagher.  Erdős-Ko-Rado theorems: algebraic approaches, volume 149 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, 2016.
  * [GM17] Chris Godsil and Karen Meagher.  An algebraic proof of the Erdős-Ko-Rado theorem for intersecting families of perfect matchings.  Ars Math. Contemp., 12(2):205–217, 2017.
  * [Lin17] Nathan Lindzey.  Erdős-Ko-Rado for perfect matchings.  European J. Combin., 65:130–142, 2017.
  * [Lin18a] Nathan Lindzey.  Intersecting families of permutations of perfect matchints.  arXiv:1811.06160, 2018.
  * [Lin18b] Nathan Lindzey.  Matchings and Representation Theory.  PhD thesis, University of Waterloo, 2018.
  * [LM04] Benoit Larose and Claudia Malvenuto.  Stable sets of maximal size in Kneser-type graphs.  European J. Combin., 25(5):657–673, 2004.
  * [MM05] Karen Meagher and Lucia Moura.  Erdős-Ko-Rado theorems for uniform set-partition systems.  Electron. J. Combin., 12:Research Paper 40, 12, 2005.
  * [MR21] Karen Meagher and A. Sarobidy Razafimahatratra.  The Erdős-Ko-Rado theorem for 2-pointwise and 2-setwise intersecting permutations.  Electron. J. Combin., 28(4):Paper No. 4.10, 21, 2021.
  * [NÖ03] Sampo Niskanen and Patric R. J. Östergård.  Cliquer user’s guide, version 1.0.  Technical Report T48, Communications Laboratory, Helsinki University of Technology, Espoo, Finland, 2003.
  * [O’D14] Ryan O’Donnell.  Analysis of Boolean functions.  Cambridge University Press, New York, 2014.
  * [Sag01] Bruce E. Sagan.  The symmetric group, volume 203 of Graduate Texts in Mathematics.  Springer-Verlag, New York, second edition, 2001.  Representations, combinatorial algorithms, and symmetric functions.
  * [Sag22] Sage Developers.  SageMath, the Sage Mathematics Software System (Version 9.5), 2022.  https://www.sagemath.org.

##  Appendix A SAGE code

The code snippets below form part of the proofs of Lemmas 2.5, 1.3 and 1.4.
They are also available as part of the arXiv version of the paper.

###  A.1 Code for Lemma 2.5

⬇

import itertools

def degree_2_functions():

"Generate vector space of degree 2 functions, represented as truth table"

return span(QQ, [vector(int((x & m) == m) for x in range(16)) \

for m in [0, 1, 2, 4, 8, 3, 5, 9, 6, 10, 12]])

def verify_no_sensitivity_4():

"Verify that no function from {0,1}^4 to {0,1} has sensitivity 4 at zero"

degree_2 = degree_2_functions()

return not any(f for f in itertools.product([0,1], repeat=16) \

if f[0] != f[1] == f[2] == f[4] == f[8] and \

vector(f) in degree_2)

###  A.2 Code for Theorem 1.3

⬇

def intersection_size(a, b):

"Size of intersection of two permutations"

return sum(i==j for (i,j) in zip(a,b))

def generate_G_n(n, t):

"Generate graph whose cliques are t-intersecting families of S_n containing
id"

idp = list(range(n))

V = [a for a in Permutations(range(n)) if intersection_size(a, idp) >= t]

E = [(a,b) for a in V for b in V if t <= intersection_size(a, b) < n]

return Graph([V, E])

def verify_main_theorem_n(n):

"Verify that all 2-intersecting families containing id are 2-cosets for given
n"

G_n = generate_G_n(n, 2)

return G_n.clique_number() == factorial(n - 2) and \

len(G_n.cliques_maximum()) == binomial(n, 2)

def verify_main_theorem():

"Verify that all 2-intersecting families containing id are 2-cosets for 4 <= n
<= 7"

return all(verify_main_theorem_n(n) for n in [4,5,6,7])

###  A.3 Code for Theorem 1.4

⬇

def intersection_size(a, b):

"Size of intersection of two perfect matchings"

return len(a.intersection(b))

def generate_G_n(n, t):

"Generate graph whose cliques are t-intersecting families of M_2n containing a
fixed PM"

idm = frozenset(PerfectMatchings(2*n).__iter__().__next__())

V = [frozenset(a) for a in PerfectMatchings(2*n) if \

intersection_size(frozenset(a), idm) >= t]

E = [(a,b) for a in V for b in V if t <= intersection_size(a, b) < n]

return Graph([V, E])

def verify_main_theorem_n(n):

"Verify that all 2-intersecting families containing a fixed PM are 2-cosets
for given n"

G_n = generate_G_n(n, 2)

return G_n.clique_number() == factorial(2*n-4)/(2^(n-2) * factorial(n-2)) and
\

len(G_n.cliques_maximum()) == binomial(n, 2)

def verify_main_theorem():

"Verify that all 2-intersecting families containing a fixed PM are 2-cosets
for 4 <= n <= 7"

return all(verify_main_theorem_n(n) for n in [4,5,6,7])