کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4655870 1343408 2012 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Large matchings in uniform hypergraphs and the conjectures of Erdős and Samuels
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Large matchings in uniform hypergraphs and the conjectures of Erdős and Samuels
چکیده انگلیسی

In this paper we study degree conditions which guarantee the existence of perfect matchings and perfect fractional matchings in uniform hypergraphs. We reduce this problem to an old conjecture by Erdős on estimating the maximum number of edges in a hypergraph when the (fractional) matching number is given, which we are able to solve in some special cases using probabilistic techniques. Based on these results, we obtain some general theorems on the minimum d-degree ensuring the existence of perfect (fractional) matchings. In particular, we asymptotically determine the minimum vertex degree which guarantees a perfect matching in 4-uniform and 5-uniform hypergraphs. We also discuss an application to a problem of finding an optimal data allocation in a distributed storage system.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series A - Volume 119, Issue 6, August 2012, Pages 1200-1215