کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4654951 1632841 2006 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Perfect matchings in uniform hypergraphs with large minimum degree
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Perfect matchings in uniform hypergraphs with large minimum degree
چکیده انگلیسی

A perfect matching in a kk-uniform hypergraph on nn vertices, nn divisible by kk, is a set of n/kn/k disjoint edges. In this paper we give a sufficient condition for the existence of a perfect matching in terms of a variant of the minimum degree. We prove that for every k≥3k≥3 and sufficiently large nn, a perfect matching exists in every nn-vertex kk-uniform hypergraph in which each set of k−1k−1 vertices is contained in n/2+Ω(logn)n/2+Ω(logn) edges. Owing to a construction in [D. Kühn, D. Osthus, Matchings in hypergraphs of large minimum degree, J. Graph Theory 51 (1) (2006) 269–280], this is nearly optimal. For almost perfect and fractional perfect matchings we show that analogous thresholds are close to n/kn/k rather than n/2n/2.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 27, Issue 8, November 2006, Pages 1333–1349
نویسندگان
, , ,