An Erdős-Ko-Rado theorem for permutations with fixed number of cycles

Cheng Yeaw Ku ; Kok Bin Wong

The electronic journal of combinatorics, Tome 21 (2014) no. 3

Résumé

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\ge n_{0}(k,t)$ where $n_{0}(k,t) = O(k^{t+2})$, 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.

Détail

DOI : 10.37236/4071

Classification : 05A05, 05D05
Mots-clés : \(t\)-intersecting family, Erdős-Ko-Rado, permutations, Stirling number of the first kind