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

作者：Ku Cheng Yeaw^*; Wong Kok Bin

来源：Discrete Mathematics, 2016, 339(2): 646-657.

DOI：10.1016/j.disc.2015.09.032

• t-intersecting family
• Frankl-Hilton-Milner
• Erdos-Ko-Rado
• Permutations

Let S-n denote the set of permutations of [n] = {1, 2, ... , n}. For a positive integer k, define S-n,S-k to be the set of all permutations of [n] with exactly k disjoint cycles, i.e.,
S-n,S-k = {pi is an element of S-n : pi = c(1)c(2) ... c(k)},
where c(1), c(2), ... , c(k) are disjoint cycles. The size of S-n,S-k is given by
[GRAPHICS]
= (-1)(n-k)s(n, k), where s(n, k) is the Stirling number of the first kind. A family A subset of S-n,S-k is said to be t-cycle-intersecting if any two elements of A have at least t common cycles. A family A subset of S-n,S-k is said to be trivially t-cycle-intersecting if A is the stabiliser oft fixed points, i.e., A consists of all permutations in S-n,S-k with some t fixed cycles of length one. For 1 <= j <= t, let
Q(j) = {sigma is an element of S-n,S-k : sigma(i) = i for all i is an element of [k] \ {j}}.
For t + 1 <= s <= k, let
B-s = {sigma is an element of S-n,S-k : sigma(i) = i for all i is an element of [t] boolean OR {s}}.
In this paper, we show that, given any positive integers k, t with k >= 2t + 3, there exists an n(0) = n(0)(k, t), such that for all n >= n(0), if A subset of S-n,S-k is non-trivially t-cycle-intersecting, then
vertical bar A vertical bar <= vertical bar B vertical bar,
where b = boolean OR(k)(s=t+1) B-s U boolean OR(t)(j=1) Q(j). Furthermore, equality holds if and only if A is a conjugate of B, i.e., A = beta(-1) B beta for some beta is an element of S-n.

• 出版日期2016-2-6