The Erdős-Ko-Rado theorem for 2-pointwise and 2-setwise intersecting permutations (Q2236813): Difference between revisions

The set of permutations of \([n] := \{1, \dots, n\}\) is denoted by \(\mbox{Sym}(n)\). A subset \(\mathcal{A}\) of \(\mbox{Sym}(n)\) is said to be \(t\)-pointwise intersecting if for every \(\sigma, \tau \in \mathcal{A}\) there exists some \(t\)-subset \(S\) of \([n]\) such that \(\sigma(x) = \tau(x)\) for each \(x \in S\). A subset \(\mathcal{A}\) of \(\mbox{Sym}(n)\) is said to be \(t\)-setwise intersecting if for every \(\sigma, \tau \in \mathcal{A}\) there exists some \(t\)-subset \(S\) of \([n]\) such that \(\{\sigma(x) \colon x \in S\} = \{\tau(x) \colon x \in S\}\). We say that \(\mbox{Sym}(n)\) has the \(t\)-pointwise star property if the size of a largest \(t\)-pointwise intersecting subset of \(\mbox{Sym}(n)\) is the size \((n-t)!\) of the \(t\)-pointwise intersecting subset \(\{\sigma \in \mbox{Sym}(n) \colon \sigma(i) = i \mbox{ for each } i \in [t]\}\). We say that \(\mbox{Sym}(n)\) has the \(t\)-setwise star property if the size of a largest \(t\)-setwise intersecting subset of \(\mbox{Sym}(n)\) is the size \(t!(n-t)!\) of the \(t\)-setwise intersecting subset \(\{\sigma \in \mbox{Sym}(n) \colon \{\sigma(1), \dots, \sigma(t)\} = [t]\}\). \textit{P. Frankl} and \textit{M. Deza} [J. Comb. Theory, Ser. A 22, 352--360 (1977; Zbl 0352.05003)] proved that \(\mbox{Sym}(n)\) has the \(1\)-pointwise star property. This is an analogue of the Erdős-Ko-Rado Theorem [\textit{P. Erdős} et al., Q. J. Math., Oxf. II. Ser. 12, 313--320 (1961; Zbl 0100.01902)]. Deza and Frankl conjectured that \(\mbox{Sym}(n)\) has the \(t\)-pointwise star property if \(n\) is sufficiently large depending on \(t\). \textit{D. Ellis} et al. [J. Am. Math. Soc. 24, No. 3, 649--682 (2011; Zbl 1285.05171)] proved this conjecture, and they conjectured that \(\mbox{Sym}(n)\) has the \(t\)-pointwise star property for \(n \geq 2t+1\). \textit{D. Ellis} [J. Comb. Theory, Ser. A 119, No. 4, 825--849 (2012; Zbl 1237.05210)] conjectured that \(\mbox{Sym}(n)\) has the \(t\)-setwise star property for \(n \geq t\), and he proved this for \(n\) sufficiently large depending on \(t\). The authors prove that for \(n \geq 2\), \(\mbox{Sym}(n)\) has the \(2\)-pointwise star property and the \(2\)-setwise star property.