Matchings in 3-uniform hypergraphs of large minimum vertex degree

Research output: Contribution to journalArticlepeer-review

Colleges, School and Institutes

Abstract

We determine the minimum vertex degree that ensures a perfect matching in a 3-uniform hypergraph. More precisely, suppose that H is a sufficiently large 3-uniform hypergraph whose order n is divisible by 3. If the minimum vertex degree of H is greater than (n-12)-(2n/32), then H contains a perfect matching. This bound is tight and answers a question of Hàn, Person and Schacht. More generally, we determine the minimum vertex degree threshold that ensures that H contains a matching of size d≤n/3.

Details

Original languageEnglish
Pages (from-to)813-818
Number of pages6
JournalElectronic Notes in Discrete Mathematics
Volume38
Publication statusPublished - 1 Dec 2011

Keywords

  • Hypergraphs, Matchings, Vertex degree