On an extremal hypergraph problem of brown, Erdos and Sós

Noga Alon, Asaf Shapira

Research output: Contribution to journalArticle

13 Scopus citations

Abstract

Let f r (n,v,e) denote the maximum number of edges in an r-uniform hypergraph on n vertices, which does not contain e edges spanned by v vertices. Extending previous results of Ruzsa and Szemerédi and of Erdos, Frankl and Rödl, we partially resolve a problem raised by Brown, Erdos and Sós in 1973, by showing that for any fixed 2≤k<r, we have n k-o(1) < fr (n, 3(r - k) + k + 1, 3) = o(n k).

Original languageEnglish (US)
Pages (from-to)627-645
Number of pages19
JournalCombinatorica
Volume26
Issue number6
DOIs
StatePublished - Dec 1 2006
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Keywords

  • 05C65
  • 05D99

Fingerprint Dive into the research topics of 'On an extremal hypergraph problem of brown, Erdos and Sós'. Together they form a unique fingerprint.

Cite this