A non-trivial intersection theorem for permutations with fixed number of cycles

详细信息    查看全文

• 作者：Cheng Yeaw Ku^a ; ^{matkcy@nus.edu.sg" class="auth_mail" title="E-mail the corresponding author} ; Kok Bin Wong^b ; ^{kbwong@um.edu.my" class="auth_mail" title="E-mail the corresponding author}
• 关键词：tt-intersecting family ; Frankl&ndash ; Hilton&ndash ; Milner ; Erdős&ndash ; Ko&ndash ; Rado ; Permutations
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 February 2016
• 年：2016
• 卷：339
• 期：2
• 页码：646-657
• 全文大小：402 K

文摘

Let S_n$S_n$ denote the set of permutations of 741c8eaf76c56" title="Click to view the MathML source">[n]={1,2,…,n}$\left[n\right]=\{1,2,\dots ,n\}$. For a positive integer k$k$, define S_n,k$S_{n,k}$ to be the set of all permutations of [n]$\left[n\right]$ with exactly k$k$ disjoint cycles, i.e., where 7267e1f2008b6" title="Click to view the MathML source">c₁,c₂,…,c_k$c_1,c_2,\dots ,c_k$ are disjoint cycles. The size of S_n,k$S_{n,k}$ is given by 7477bf1470424">$\left[\begin{array}{c}\hfill n\hfill \\ \hfill k\hfill \end{array}\right]={(-1)}^{n-k}s(n,k)$, where s(n,k)$s(n,k)$ is the Stirling number of the first kind. A family A⊆S_n,k$\mathcal{A}\subseteq S_{n,k}$ is said to be t$t$-cycle-intersecting if any two elements of A$\mathcal{A}$ have at least t$t$ common cycles. A family A⊆S_n,k$\mathcal{A}\subseteq S_{n,k}$ is said to be trivially t$t$-cycle-intersecting if A$\mathcal{A}$ is the stabiliser of t$t$ fixed points, i.e., A$\mathcal{A}$ consists of all permutations in S_n,k$S_{n,k}$ with some t$t$ fixed cycles of length one. For 1≤j≤t$1\le j\le t$, let For t+1≤s≤k$t+1\le s\le k$, let In this paper, we show that, given any positive integers k,t$k,t$ with k≥2t+3$k\ge 2t+3$, there exists an 7290ee5ffd6debfd291f638d3f749" title="Click to view the MathML source">n₀=n₀(k,t)$n_0=n_0(k,t)$, such that for all n≥n₀$n\ge n_0$, if A⊆S_n,k$\mathcal{A}\subseteq S_{n,k}$ is non-trivially t$t$-cycle-intersecting, then where $\mathcal{B}={\bigcup }_{s=t+1}^k{\mathcal{B}}_s\cup {\bigcup }_{j=1}^t{\mathcal{Q}}_j$. Furthermore, equality holds if and only if A$\mathcal{A}$ is a conjugate of B$\mathcal{B}$, i.e., A=β⁻¹Bβ$\mathcal{A}={\beta }^{-1}\mathcal{B}\beta$ for some β∈S_n$\beta \in S_n$.