An Erdős-Ko-Rado theorem for permutations with fixed number of cycles (Q405301): Difference between revisions

Summary: Let \(S_{n}\) denote the set of permutations of \([n]=\{1,2,\dots, n\}\). For a positive integer \(k\), define \(S_{n,k}\) to be the set of all permutations of \([n]\) with exactly \(k\) disjoint cycles, i.e., \[ S_{n,k} = \{\pi\in S_{n}: \pi = c_{1}c_{2} \cdots c_{k}\}, \] where \(c_1,c_2,\dots ,c_k\) are disjoint cycles. The size of \(S_{n,k}\) is \(\left [ \begin{matrix} n\\ k \end{matrix}\right]=(-1)^{n-k}s(n,k)\), where \(s(n,k)\) is the Stirling number of the first kind. A family \(\mathcal{A} \subseteq S_{n,k}\) is said to be \(t\)-cycle-intersecting if any two elements of \(\mathcal{A}\) have at least \(t\) common cycles. In this paper we show that, given any positive integers \(k,t\) with \(k\geq t+1\), if \(\mathcal{A} \subseteq S_{n,k}\) is \(t\)-cycle-intersecting and \(n\geq n_{0}(k,t)\) where \(n_{0}(k,t) = O(k^{t+2})\), then \[ |\mathcal{A}| \leq \left [ \begin{matrix} n-t\\ k-t \end{matrix}\right], \] with equality if and only if \(\mathcal{A}\) is the stabiliser of \(t\) fixed points.