Erdos-Ko-Rado with conditions on the minimum complementary degree

摘要

Let X = {1, 2,...,n}, 2k < n, and let X-(k) denote the set of all subsets of X of size k. A set system F subset of or equal to X-(k) is intersecting if no two of its elements are disjoint. The minimum complementary degree c(F) of F is the minimum over all i is an element of X of the number of sets in F not containing i. A set system F subset of or equal to X-(k) is complementary degree condition maximal (CDCM) if H subset of or equal to X-(k) intersecting, c(H) greater than or equal to c(F) double right arrow H less than or equal to F and SCDCM (S for strict) if equality holds on the right only if it holds on the left. In this paper we characterize all intersecting F subset of or equal to X-(k) with c(F) less than or equal to (n-3 k-2) which are CDCM and SCDCM. The characterization is in terms of the cascade form of c(F), a representation in terms of sums of certain binomial coefficients. This result generalizes the Erdos-Ko-Rado and Hilton-Milner theorems and a theorem of Frankl's with conditions on the maximum degree. The number of isomorphically distinct set systems F subset of or equal to X-(k) which are SCDCM is the Catalan number Ck-2 = 1/k-1 (2k-4 k-2) and the number which are CDCM is Sigma k-2 i=0C(i). (C) 2004 Elsevier Inc. All rights reserved.