Abstract | ||
---|---|---|
More than forty years ago, ErdÅ聭s conjectured that for any $t \leq \frac{n}{k}$, every k-uniform hypergraph on n vertices without t disjoint edges has at most max${\binom{kt-1}{k}, \binom{n}{k}-\binom{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 . This improves upon the best previously known range $t = O\bigl(\frac{n}{k^3}\bigr)$, which dates back to the 1970s. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1017/S096354831100068X | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
disjoint edge,hypergraph tur,n vertex,n problem,matching number,forty year,t-edge matching,basic instance,k-uniform hypergraph | Discrete mathematics,Combinatorics,Disjoint sets,Vertex (geometry),Hypergraph,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
21 | 3 | 0963-5483 |
Citations | PageRank | References |
23 | 2.10 | 4 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Hao Huang | 1 | 589 | 104.49 |
Po-Shen Loh | 2 | 133 | 18.68 |
Benny Sudakov | 3 | 1391 | 159.71 |