Cross-intersecting sub-families of hereditary families

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:119

Article

Borg, Peter

关键词: Chvatal's conjecture;    Cross-intersecting families;    Extremal set theory;    Hereditary families;    Intersecting families;   

DOI  :  10.1016/j.jcta.2011.12.002

来源: Elsevier

【 摘 要 】

Families A(1), A(2) ..... A(k) of sets are said to be cross-intersecting if for any i and j in (1,2, with i not equal j, any set in A(i) intersects any set in A(j) For a finite set X, let 2(x) denote the power set of X (the family of all subsets of X). A family H is said to be hereditary if all subsets of any set in H are in H: so H is hereditary if and only if it is a union of power sets. We conjecture that for any nonempty hereditary sub-family H not equal {empty set} of 2(x) and any k >= broken vertical bar X broken vertical bar + 1, both the sum and the product of sizes of k cross-intersecting sub-families A1 . A(2) ..... A(k) (not necessarily distinct or non-empty) of H are maxima if A(1) = A(2) = ... = A(k) = S for some largest star S of H (a sub-family of H whose sets have a common element). We prove this for the case when H is compressed with respect to an element x of X. and for this purpose we establish new properties of the usual compression operation. As we will show, for the sum, the condition k >= broken vertical bar X broken vertical bar + 1 is sharp. However, for the product, we actually conjecture that the configuration A(1) = A(2) = ... = A(k) = S is optimal for any hereditary H and any k >= 2. and we prove this for a special case. (C) 2011 Elsevier Inc. All rights reserved.

【 授权许可】

Free