Fractional and integer matchings in uniform hypergraphs

Research output: Contribution to journalArticle

Authors

Colleges, School and Institutes

Abstract

Our main result improves bounds of Markström and Ruciński on the minimum d-degree which forces a perfect matching in a k-uniform hypergraph on n vertices. We also extend bounds of Bollobás, Daykin and Erdos by asymptotically determining the minimum vertex degree which forces a matching of size t < n / 2 (k - 1) in a k-uniform hypergraph on n vertices. Further asymptotically tight results on d-degrees which force large matchings are also obtained. Our approach is to prove fractional versions of the above results and then translate these into integer versions.

Details

Original languageEnglish
Pages (from-to)83-96
Number of pages14
JournalEuropean Journal of Combinatorics
Volume38
Publication statusPublished - 1 May 2014