Bir Hipergrafın Boyutu ve Eşleşme Sayısı

Özet (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 < \frac{n}{3k^2}$ . This improves upon the best previously known range $t = O\bigl(\frac{n}{k^3}\bigr)$ , which dates back to the 1970s.

Yazarların özeti; kaynağından alınmıştır. Combinatorics Probability Computing, 2012 · DOI ↗