The Erdős-Ko-Rado Theorem for 2-Pointwise and 2-Setwise Intersecting Permutations

Abstract

In this paper we consider the conjectured Erdős-Ko-Rado property for $2$-pointwise and $2$-setwise intersecting permutations.

Two permutations $\sigma,\tau \in \operatorname{Sym}(n)$ are $t$-setwise intersecting if there exists a $t$-subset $S$ of $\{1,2,\dots,n\}$ such that $S^\sigma = S^\tau$. Further, two permutations $\sigma,\tau \in \operatorname{Sym}(n)$ are $t$-pointwise intersecting if there exists a $t$-subset $S$ of $\{1,2,\dots,n\}$ such that $s^\sigma = s^\tau$ for each $s \in S$. A family of permutations $\mathcal{F} \subset \operatorname{Sym}(n)$ is called $t$-setwise (resp. $t$-pointwise) intersecting, if any two permutations in $\mathcal{F}$ are $t$-setwise (resp. $t$-pointwise) intersecting. We say that $\operatorname{Sym}(n)$ has the $t$-setwise intersecting property if for any family $\mathcal{F}$ of $t$-setwise intersecting permutations, $|\mathcal{F}| \leqslant t!(n-t)!$. Similarly, $\operatorname{Sym}(n)$ has the $t$-pointwise intersecting property if for any family $\mathcal{F}$ of $t$-pointwise intersecting permutations, $|\mathcal{F}| \leqslant (n-t)!$.

Ellis ([``"Setwise intersecting families of permutations".  J. Combin. Theory Ser. A, 119(4):825-849, 2012]), proved that if $n$ is sufficiently large relative to $t$, then $\operatorname{Sym}(n)$ has the $t$-setwise intersecting property. Ellis also conjectured that this result holds for all $n \geqslant t$. Ellis, Friedgut and Pilpel ["``Intersecting families of permutations."  J. Amer. Math. Soc. 24(3):649-682, 2011] also proved that for $n$ sufficiently large relative to $t$, $\operatorname{Sym}(n)$ has the $t$-pointwise intersecting property. It is also conjectured that $\operatorname{Sym}(n)$ has the $t$-pointwise intersecting property for $n\geqslant 2t+1$. In this work, we prove these two conjectures for $\operatorname{Sym}(n)$ when $t=2$.