An Erdős-Ko-Rado theorem for permutations with fixed number of cycles (Q405301): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05A05 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05D05 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6340240 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
\(t\)-intersecting family | |||
Property / zbMATH Keywords: \(t\)-intersecting family / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Erdős-Ko-Rado | |||
Property / zbMATH Keywords: Erdős-Ko-Rado / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
permutations | |||
Property / zbMATH Keywords: permutations / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Stirling number of the first kind | |||
Property / zbMATH Keywords: Stirling number of the first kind / rank | |||
Normal rank |
Revision as of 18:19, 29 June 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An Erdős-Ko-Rado theorem for permutations with fixed number of cycles |
scientific article |
Statements
An Erdős-Ko-Rado theorem for permutations with fixed number of cycles (English)
0 references
4 September 2014
0 references
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.
0 references
\(t\)-intersecting family
0 references
Erdős-Ko-Rado
0 references
permutations
0 references
Stirling number of the first kind
0 references