Large matchings in uniform hypergraphs and the conjectures of Erdos and Samuels

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:119

Article

Alon, Noga^1,2  Huang, Hao³  Roedl, Vojtech⁴  Rucinski, Andrzej⁵  Sudakov, Benny³ 

[1] Tel Aviv Univ, Sackler Sch Math, IL-69978 Tel Aviv, Israel

[2] Tel Aviv Univ, Blavatnik Sch Comp Sci, IL-69978 Tel Aviv, Israel

[3] Univ Calif Los Angeles, Dept Math, Los Angeles, CA 90095 USA

[4] Emory Univ, Atlanta, GA 30322 USA

[5] Adam Mickiewicz Univ, Poznan, Poland

关键词: Perfect matching;    Hypergraph;    Degree condition;    Distributed storage system;   

DOI  :  10.1016/j.jcta.2012.02.004

来源: Elsevier

【 摘 要 】

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. (C) 2012 Elsevier Inc. All rights reserved.

【 授权许可】

Free