Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Problem 1178

claims/: The 2 claim pages of Problem 1178, one per claimant's result; the problem's standing derives from them.

Statement. 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$ .

Status. 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.

Source. erdosproblems.com/1178, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #1178, https://www.erdosproblems.com/1178.

References.

[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., [[../library/set_systems/erdos_1981_combinatorial_problems_which_i_would_most/_index|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.

Formalization. Statement in formal-conjectures.

Current assessment

The case $e=3$ is settled for every $r\ge3$ by the two accepted partial claims named under Status, each combined with the Brown–Erdős–Sós lower bound; every case $e\ge4$ is open. The upper bounds the site credits for those cases are Sárközy and Selkow's $(r-2)e+2+\lfloor\log_2e\rfloor$ for all $r$ , and for $r=3$ Solymosi and Solymosi's $d_3(10)\le14$ and Conlon, Gishboliner, Levanzov and Shapira's $e+O(\log e/\log\log e)$ . Search scope: the site's problem page and the references it lists; no wider literature search is recorded.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (33)

Problem 1157 Problem 810 Problem 716 Erdős, Frankl and Rödl settle the three-edge case Sárközy and Selkow's logarithmic upper bound problems/set_systems/E1178/claims Set Systems, Designs and Hypergraphs additive_combinatorics/erdos_1975_problems_results_combinatorial_number_theory extremal_graph_theory/alon_2006_extremal_hypergraph_problem_brown_erdos_sos Conjecture 1: n^{k-o(1)} < f_r(n, e(r-k)+k+1, e) = o(n^k) for every fixed 2 ≤ k < r and 3 ≤ e Proposition 5.2: the o(n^2) case k = 2 for every e and r ≥ 3 implies f_r(n, e(r-k)+k+1, e) = o(n^k) for every 2 ≤ k < r Theorem 1: n^{k-o(1)} < f_r(n, 3(r-k)+k+1, 3) = o(n^k) for every fixed 2 ≤ k < r extremal_graph_theory/brown_1973_extremal_problems_graphs Question (p. 58): is f^{(3)}(n; 6, 3) = o(n^2)?Theorem (Section 4): f^{(r)}(n; k, s) > c_{k,s} n^{(rs-k)/(s-1)} for integers k > r and s > 1 extremal_graph_theory/erdos_1986_asymptotic_number_graphs_not_containing_fixed Problem 6.2 (p. 120): no exponent for ℓ edges on ℓ(r-2)+3 vertices?Proposition 6.3 (p. 120): g_n(2+(r-2)e,e,r) = Θ(n²)Theorem 1.7 (pp. 114-115): g_n(3r-3,3,r) is o(n²) but exceeds n^c for every c < 2 extremal_graph_theory/janzer_2025_power_saving_brown_erdos_sos_problem ramsey_theory/burr_1989_maximal_anti_ramsey_graphs_strong_chromatic Question (p. 273): can χ_S(n,εn²,C_4) ≤ n hold for some small ε > 0?Set Systems, Designs and Hypergraphs set_systems/conlon_2023_new_bound_brown_erdos_sos_problem Conjecture 1.1 (p. 2): the Brown–Erdős–Sós conjecture f_3(n, e+3, e) = o(n^2) for every e >= 3 Corollary 2 (p. 3): f_r(n, (r-k)e + k + ceil(26 log e / log log e) - 2, e) = o(n^k)Proposition 1.2 (p. 2): the r-uniform Brown–Erdős–Sós function is bounded by the 3-uniform one Theorem 1 (p. 2): f_3(n, e + ceil(26 log e / log log e), e) = o(n^2) for every e >= 3 set_systems/solymosi_2017_small_cores_3_uniform_hypergraphs Conjecture (p. 5, Section 3.1): quadratically many edges force a core on at most 9 vertices Theorem 1.3 (p. 2): quantitative Ruzsa-Szemerédi, cn^2 edges give delta n^3 copies of six vertices carrying three edges Theorem 3.4 (p. 7): with no 14 vertices carrying 10 edges, a 3-uniform hypergraph has o(n^2) edges Theorem 3.6 (p. 9): core(n, 15) = o(n^2)

Graph