کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4665604 | 1633819 | 2015 | 70 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Polynomial-time perfect matchings in dense hypergraphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات (عمومی)
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Let H be a k-graph on n vertices, with minimum codegree at least n/k+cnn/k+cn for some fixed c>0c>0. In this paper we construct a polynomial-time algorithm which finds either a perfect matching in H or a certificate that none exists. This essentially solves a problem of Karpiński, Ruciński and Szymańska; Szymańska previously showed that this problem is NP-hard for a minimum codegree of n/k−cnn/k−cn. Our algorithm relies on a theoretical result of independent interest, in which we characterise any such hypergraph with no perfect matching using a family of lattice-based constructions.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Advances in Mathematics - Volume 269, 10 January 2015, Pages 265–334
Journal: Advances in Mathematics - Volume 269, 10 January 2015, Pages 265–334
نویسندگان
Peter Keevash, Fiachra Knox, Richard Mycroft,