کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5777541 1632922 2017 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Degree versions of the Erdős-Ko-Rado theorem and Erdős hypergraph matching conjecture
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Degree versions of the Erdős-Ko-Rado theorem and Erdős hypergraph matching conjecture
چکیده انگلیسی
We use an algebraic method to prove a degree version of the celebrated Erdős-Ko-Rado theorem: given n>2k, every intersecting k-uniform hypergraph H on n vertices contains a vertex that lies on at most (n−2k−2) edges. This result implies the Erdős-Ko-Rado Theorem as a corollary. It can also be viewed as a special case of the degree version of a well-known conjecture of Erdős on hypergraph matchings. Improving the work of Bollobás, Daykin, and Erdős from 1976, we show that, given integers n, k, s with n≥3k2s, every k-uniform hypergraph H on n vertices with minimum vertex degree greater than (n−1k−1)−(n−sk−1) contains s disjoint edges.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series A - Volume 150, August 2017, Pages 233-247
نویسندگان
, ,