An Erd{\H o}s-Ko-Rado theorem for permutations with fixed number of cycles

Abstract

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} = \{π\in S_{n}: π= 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 given by $\left[\begin{array}{c}n\\ k\end{array}\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$-{\em 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\ge t+1$, there exists an integer $n_0=n_0(k,t)$, such that for all $n\ge n_0$, if $\mathcal{A}\subseteq S_{n,k}$ is $t$-intersecting, then \[ |\mathcal{A}| \le \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.

arXiv comment8 pages