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

Noga Alon; Asaf Shapira

doi:10.1007/s00493-006-0035-9

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

Noga Alon, Asaf Shapira

Research output: Contribution to journal › Article › peer-review

30 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) < f_r (n, 3(r - k) + k + 1, 3) = o(n ^k).

Original language	English (US)
Pages (from-to)	627-645
Number of pages	19
Journal	Combinatorica
Volume	26
Issue number	6
DOIs	https://doi.org/10.1007/s00493-006-0035-9
State	Published - Dec 2006
Externally published	Yes

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Keywords

05C65
05D99

Access to Document

10.1007/s00493-006-0035-9

Cite this

@article{b1422ee0ce284db0881f2b857a184906,

title = "On an extremal hypergraph problem of brown, Erdos and S{\'o}s",

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{\'e}di and of Erdos, Frankl and R{\"o}dl, we partially resolve a problem raised by Brown, Erdos and S{\'o}s in 1973, by showing that for any fixed 2≤kk-o(1) < fr (n, 3(r - k) + k + 1, 3) = o(n k).",

keywords = "05C65, 05D99",

author = "Noga Alon and Asaf Shapira",

note = "Funding Information: * Research supported in part by a USA-Israeli BSF grant, by th e Israel Science Foundation and by th e Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. † Th is work forms part of th e auth or{\textquoteright}s Ph .D. Th esis. Research supported by a Ch arles Clore Foundation Fellowsh ip and an IBM Ph .D. Fellowsh ip.",

year = "2006",

month = dec,

doi = "10.1007/s00493-006-0035-9",

language = "English (US)",

volume = "26",

pages = "627--645",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "6",

}

TY - JOUR

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

AU - Alon, Noga

AU - Shapira, Asaf

N1 - Funding Information: * Research supported in part by a USA-Israeli BSF grant, by th e Israel Science Foundation and by th e Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. † Th is work forms part of th e auth or’s Ph .D. Th esis. Research supported by a Ch arles Clore Foundation Fellowsh ip and an IBM Ph .D. Fellowsh ip.

PY - 2006/12

Y1 - 2006/12

N2 - 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≤kk-o(1) < fr (n, 3(r - k) + k + 1, 3) = o(n k).

AB - 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≤kk-o(1) < fr (n, 3(r - k) + k + 1, 3) = o(n k).

KW - 05C65

KW - 05D99

UR - http://www.scopus.com/inward/record.url?scp=33847304518&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33847304518&partnerID=8YFLogxK

U2 - 10.1007/s00493-006-0035-9

DO - 10.1007/s00493-006-0035-9

M3 - Article

AN - SCOPUS:33847304518

SN - 0209-9683

VL - 26

SP - 627

EP - 645

JO - Combinatorica

JF - Combinatorica

IS - 6

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this