Erdős-Ko-Rado theorems for permutations and set partitions (Q941314): Difference between revisions

\(\text{Sym}([n])\) consists of all permutations of \([n]=\{1,2,\dots,n\}\); \({\mathcal A}\subseteq\text{Sym}([n])\) is \textsl{\(t\)-intersecting} if any \(g,h\in{\mathcal A}\) have at least \(t\) positions in common, and \textsl{\(t\)-cycle-intersecting} if any \(g,h\in{\mathcal A}\) have, when written in disjoint cycle decomposition, at least \(t\) cycles in common. \({\mathcal B}(n)\) denotes the set of all set partitions of \([n]\). Following a proof of a theorem stated in [\textit{M. Deza} and \textit{P. Frankl}, ``Erdős-Ko-Rado theorem --- 22 years later'', SIAM J. Algebraic Discrete Methods 4, 419--431 (1983; Zbl 0526.05001)], the authors prove \newline{Theorem 1.4:} Let \(t\geq2\). Suppose \({\mathcal A}\subseteq\text{Sym}([n])\) is \(t\)-cycle-intersecting, and \(n\geq n_0(t)=\text{O}(t^2)\) as \(t\to\infty\). Then \(| {\mathcal A}| \leq(n-t)!\), with equality iff \(\mathcal A\) is the stabilizer of \(t\) fixed points. In \S3, using methods they describe as ``similar to those given in'' [\textit{P. J. Cameron} and \textit{C. Y. Ku}, ``Intersecting families of permutations'', Eur.\ J. Comb.\ 24, No.\,7, 881--890 (2003; Zbl 1026.05001)], they prove \newline{Theorem 1.7:} Let \(n\geq2\). Suppose \({\mathcal A}\subseteq{\mathcal B}(n)\) is 1-intersecting. Then \(| {\mathcal A}| \leq| {\mathcal B}(n-1)| \), with equality iff \(\mathcal A\) consists of all set partitions with a fixed singleton; \newline{Theorem 1.8:} Let \(t\geq2\). Suppose \({\mathcal A}\subseteq{\mathcal B}(n)\) is \(t\)-intersecting. If \(n\geq n_0(t)\), then \(| {\mathcal A}| \leq| {\mathcal B}(n-1)| \), with equality iff \(\mathcal A\) consists of all set partitions with \(t\) fixed singletons.