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

چکیده انگلیسی
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
Journal: European Journal of Combinatorics - Volume 27, Issue 8, November 2006, Pages 1333–1349
نویسندگان
Vojtech Rödl, Andrzej Ruciński, Endre Szemerédi,