Fractional and integer matchings in uniform hypergraphs

Daniela Kühn, Deryk Osthus, Timothy Townsend

Research output: Contribution to journalArticlepeer-review

14 Citations (Scopus)

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.

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

ASJC Scopus subject areas

  • Geometry and Topology
  • Theoretical Computer Science
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Fractional and integer matchings in uniform hypergraphs'. Together they form a unique fingerprint.

Cite this