Non-trivial intersecting uniform sub-families of hereditary families

作者：Borg Peter^*

来源：Discrete Mathematics, 2013, 313(17): 1754-1761.

DOI：10.1016/j.disc.2013.04.017

• Non-trivial intersecting families
• Hereditary families
• Erdos-Ko-Rado theorem
• Hilton-Milner theorem
• Extremal set theory

For a family F of sets, let mu(F) denote the size of a smallest set in F that is not a subset of any other set in F, and for any positive integer r, let F-(r) denote the family of r-element sets in F. We say that a family A is of Hilton-Milner (HM) type if for some A is an element of A, all sets in A backslash {A} have a common element x is not an element of A and intersect A. We show that if a hereditary family H is compressed and mu(H) >= 2r >= 4, then the HM-type family {A is an element of H-(r): 1 is an element of A, A boolean AND[2, r+1] not equal empty set} boolean OR {[2, r+1]} is a largest non-trivial intersecting sub-family of H-(r); this generalises a well-known result of Hilton and Milner. We demonstrate that for any r >= 3 and m >= 2r, there exist non-compressed hereditary families H with mu(H) = m such that no largest non-trivial intersecting sub-family of H-(r) is of HM type, and we suggest two conjectures about the extremal structures for arbitrary hereditary families.

• 出版日期2013-9-6