کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8903816 1632917 2018 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A degree version of the Hilton-Milner theorem
ترجمه فارسی عنوان
نسخه درجهی قضیه هیلتون-میلنر
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
An intersecting family of sets is trivial if all of its members share a common element. Hilton and Milner proved a strong stability result for the celebrated Erdős-Ko-Rado theorem: when n>2k, every non-trivial intersecting family of k-subsets of [n] has at most (n−1k−1)−(n−k−1k−1)+1 members. One extremal family HMn,k consists of a k-set S and all k-subsets of [n] containing a fixed element x∉S and at least one element of S. We prove a degree version of the Hilton-Milner theorem: if n=Ω(k2) and F is a non-trivial intersecting family of k-subsets of [n], then δ(F)≤δ(HMn.k), where δ(F) denotes the minimum (vertex) degree of F. Our proof uses several fundamental results in extremal set theory, the concept of kernels, and a new variant of the Erdős-Ko-Rado theorem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series A - Volume 155, April 2018, Pages 493-502
نویسندگان
, , , ,