• Title of article

    Large matchings in uniform hypergraphs and the conjectures of Erdős and Samuels

  • Author/Authors

    Alon، نويسنده , , Noga and Frankl، نويسنده , , Peter and Huang، نويسنده , , Hao and R?dl، نويسنده , , Vojtech and Ruci?ski، نويسنده , , Andrzej and Sudakov، نويسنده , , Benny، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2012
  • Pages
    16
  • From page
    1200
  • To page
    1215
  • Abstract
    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 Erdős 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.
  • Keywords
    degree condition , Distributed storage system , Hypergraph , Perfect matching
  • Journal title
    Journal of Combinatorial Theory Series A
  • Serial Year
    2012
  • Journal title
    Journal of Combinatorial Theory Series A
  • Record number

    1531790