The Erdős-Ko-Rado theorem for 2-pointwise and 2-setwise intersecting permutations

Karen Meagher¹ ; A. Sarobidy Razafimahatratra²

¹University of Regina
²University or Regina

The electronic journal of combinatorics, Tome 28 (2021) no. 4

Résumé

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$.

Détail

DOI : 10.37236/9556

Classification : 05D05, 05C35, 05C69, 20B05
Mots-clés : intersecting permutations