CROSS-INTERSECTING FAMILIES OF FINITE SETS

[摘要] It is proved that if A is a family of a-element sets and B is a family of b-element sets on the common undelying set [n], and A boolean AND B not equal empty set for all A is an element of A, B is an element of B (i.e., cross-intersecting), and n greater than or equal to a + b,) \A\ greater than or equal to ((n-1)(a-1)) - ((n-b-1)(a-1)) + 1, and \B\ > ((n-1)(b-1)) - ((n-a-1)(b-1)) + 1, then there exists an element x is an element of [n] such that it belongs to all members of A and B. This is an extension of a result of Hilton and Milner who generalized the Erdos-Ko-Rado theorem for non-trivial intersecting families. Several problems remain open. (C) 1995 Academic Press, Inc.

[发布日期] 1995-11-01