Article ID Journal Published Year Pages File Type
4647661 Discrete Mathematics 2013 8 Pages PDF
Abstract

For a family FF of sets, let μ(F)μ(F) denote the size of a smallest set in FF that is not a subset of any other set in FF, and for any positive integer rr, let F(r)F(r) denote the family of rr-element sets in FF. We say that a family AA is of Hilton–Milner (HM) type   if for some A∈AA∈A, all sets in A∖{A}A∖{A} have a common element x∉Ax∉A and intersect AA. We show that if a hereditary   family HH is compressed   and μ(H)≥2r≥4μ(H)≥2r≥4, then the HM-type family {A∈H(r):1∈A,A∩[2,r+1]≠0̸}∪{[2,r+1]}{A∈H(r):1∈A,A∩[2,r+1]≠0̸}∪{[2,r+1]} is a largest non-trivial intersecting   sub-family of H(r)H(r); this generalises a well-known result of Hilton and Milner. We demonstrate that for any r≥3r≥3 and m≥2rm≥2r, there exist non-compressed hereditary families HH with μ(H)=mμ(H)=m such that no largest non-trivial intersecting sub-family of H(r)H(r) is of HM type, and we suggest two conjectures about the extremal structures for arbitrary hereditary families.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,