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

Noga Alon, Peter Frankl, Hao Huang, Vojtech Rödl, Andrzej Ruciński, Benny Sudakov

Research output: Contribution to journalArticle

55 Scopus citations

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 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.

Original languageEnglish (US)
Pages (from-to)1200-1215
Number of pages16
JournalJournal of Combinatorial Theory. Series A
Volume119
Issue number6
DOIs
StatePublished - Aug 1 2012
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Degree condition
  • Distributed storage system
  • Hypergraph
  • Perfect matching

Fingerprint Dive into the research topics of 'Large matchings in uniform hypergraphs and the conjectures of Erdos and Samuels'. Together they form a unique fingerprint.

  • Cite this