Problem 1178

For $r\geq 3$ let $d_r(e)$ be the minimal $d$ such that

\mathrm{ex}_r(n,\mathcal{F})=o(n^2),

where $\mathcal{F}$ is the family of $r$ -uniform hypergraphs on $d$ vertices with $e$ edges.

Prove that

d_r(e)=(r-2)e+3

for all $r,e\geq 3$ .

Source: erdosproblems.com/1178

Graph theory
Hypergraphs

Wiki page

Status

Open

No claim settles this problem.

Open. The site labels the problem OPEN (page last edited 26 January 2026). Two accepted partial claims settle the case $e=3$ for every $r\ge3$ : Erdős, Frankl and Rödl's theorem and Sárközy and Selkow's bound, each with the Brown–Erdős–Sós lower bound. The other results the site credits have no claim page here, for these reasons:

Ruzsa and Szemerédi's $d_3(3)=6$ [RuSz78] appeared in a proceedings volume, lies inside Erdős, Frankl and Rödl's theorem, and has its accepted claim page on Problem 716.
Brown, Erdős and Sós's lower bound $d_r(e)\ge(r-2)e+3$ [BES73] appeared in a proceedings volume and is one-sided, so it settles no instance alone; it is the lower half both claim pages use.
Solymosi and Solymosi's $d_3(10)\le14$ [SoSo17] and Conlon, Gishboliner, Levanzov and Shapira's $d_3(e)\le e+O(\log e/\log\log e)$ [CGLS23] are upper bounds above the conjectured value and settle no instance.

BES73: Brown, W. G. and Erdős, P. and Sós, V. T., Some extremal problems on $r$ -graphs. (1973), 53-63.
CGLS23: Conlon, David and Gishboliner, Lior and Levanzov, Yevgeny and Shapira, Asaf, A new bound for the Brown-Erd\H os-Sós problem. J. Combin. Theory Ser. B 158 (2023), 1-35.
EFR86: Erdős, P. and Frankl, P. and Rödl, V., The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent. Graphs Combin. (1986), 113-121.
Er75b: Erdős, Paul, Problems and results in combinatorial number theory. Journées Arithmétiques de Bordeaux (Conf., Univ. Bordeaux, Bordeaux, 1974) (1975), 295-310.
Er81: Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42.
RuSz78: Ruzsa, I. Z. and Szemerédi, E., Triple systems with no six points carrying three triangles. Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II (1978), 939-945.
SaSe05: Sárközy, Gábor N. and Selkow, Stanley, An extension of the Ruzsa-Szemerédi theorem. Combinatorica (2005), 77-84.
SoSo17: Solymosi, David and Solymosi, Jozsef, Small cores in 3-uniform hypergraphs. J. Combin. Theory Ser. B (2017), 897-910.

Problem 1178

Status

Proof claims

Discussion