The size of a hypergraph and its matching number

Hao Huang, Po Shen Loh, Benny Sudakov

Research output: Contribution to journalArticlepeer-review

74 Scopus citations

Abstract

More than forty years ago, Erdós conjectured that for any t ≤ n/k, every k-uniform hypergraph on n vertices without t disjoint edges has at most max {( kt-1 k),( n k)- n-t+1 k}, edges. Although this appears to be a basic instance of the hypergraph Turán problem (with a t-edge matching as the excluded hypergraph), progress on this question has remained elusive. In this paper, we verify this conjecture for all t < n/3k 2. This improves upon the best previously known range t = O (n/k 3), which dates back to the 1970s.

Original languageEnglish (US)
Pages (from-to)442-450
Number of pages9
JournalCombinatorics Probability and Computing
Volume21
Issue number3
DOIs
StatePublished - May 2012
Externally publishedYes

Fingerprint

Dive into the research topics of 'The size of a hypergraph and its matching number'. Together they form a unique fingerprint.

Cite this