TY - JOUR
T1 - Large matchings in uniform hypergraphs and the conjectures of Erdos and Samuels
AU - Alon, Noga
AU - Frankl, Peter
AU - Huang, Hao
AU - Rödl, Vojtech
AU - Ruciński, Andrzej
AU - Sudakov, Benny
N1 - Funding Information:
E-mail addresses: [email protected] (N. Alon), [email protected] (P. Frankl), [email protected] (H. Huang), [email protected] (V. Rödl), [email protected] (A. Ruciński), [email protected] (B. Sudakov). 1 Research supported in part by an ERC advanced grant, by a USA–Israeli BSF grant and by the Israeli I-Core program. 2 Research supported by NSF grant DMS 080070. 3 Research supported by the National Science Center grant N N201 604940, and the NSF grant DMS-1102086. Part of research performed at Emory University, Atlanta. 4 Research supported in part by NSF grant DMS-1101185, NSF CAREER award DMS-0812005 and by USA–Israeli BSF grant.
PY - 2012/8
Y1 - 2012/8
N2 - 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 Erdos 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.
AB - 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 Erdos 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.
KW - Degree condition
KW - Distributed storage system
KW - Hypergraph
KW - Perfect matching
UR - http://www.scopus.com/inward/record.url?scp=84862777543&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84862777543&partnerID=8YFLogxK
U2 - 10.1016/j.jcta.2012.02.004
DO - 10.1016/j.jcta.2012.02.004
M3 - Article
AN - SCOPUS:84862777543
SN - 0097-3165
VL - 119
SP - 1200
EP - 1215
JO - Journal of Combinatorial Theory. Series A
JF - Journal of Combinatorial Theory. Series A
IS - 6
ER -