کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647661 1342365 2013 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Non-trivial intersecting uniform sub-families of hereditary families
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Non-trivial intersecting uniform sub-families of hereditary families
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 313, Issue 17, 6 September 2013, Pages 1754–1761
نویسندگان
,