Problem 1157

Let $t,k,r\geq 2$ . Let $\mathcal{F}$ be the family of all $r$ -uniform hypergraphs with $k$ vertices and $s$ edges. Determine

\mathrm{ex}_r(n,\mathcal{F}).

Source: erdosproblems.com/1157

Hypergraphs
Turán numbers

Wiki page

Status

Open

No claim settles this problem.

Open. The problem is a whole family of Turán-type questions, and no cited source determines $\mathrm{ex}_r(n,\mathcal F)$ in general. What the cited sources prove: the general lower bound $\mathrm{ex}_r(n,\mathcal F)>c_{k,s}n^{(rs-k)/(s-1)}$ for $k>r$ and $s>1$ (the Theorem of Section 4 of [BES73], result page, which the authors remark, without proof, is sharp in the exponent when $s-1$ divides $rs-k$ ); the Brown--Erdős--Sós conjecture, that $\mathrm{ex}_r(n,\mathcal F)=o(n^t)$ once $k\ge(r-t)s+t+1$ , proved for $s=3$ and every $r>t\ge2$ with a matching $n^{t-o(1)}$ lower bound (Theorem 1 of [AlSh06], result page, extending the Ruzsa--Szemerédi $(6,3)$ -theorem and the Erdős--Frankl--Rödl case $t=2$ ) and, in its $t=2$ linear form, for every uniformity $r$ large enough in terms of the density (Theorem 3 of [KeLo20], result page); for 3-graphs and $t=2$ the approximate versions $\mathrm{ex}_3(n,\mathcal F)=o(n^2)$ for $k=s+\lfloor\log_2s\rfloor+2$ (Sárközy and Selkow, quoted) and $k=s+O(\log s/\log\log s)$ (Conlon, Gishboliner, Levanzov and Shapira, quoted), and the power saving $\mathrm{ex}_3(n,\mathcal F)=O(n^{2-\varepsilon})$ for $k=s+\lfloor\log_2s\rfloor+38$ (Theorem 1.3 of [JMMS25], result page); and a conditional reduction of the constant-deficiency form to a Turán conjecture on 2-degenerate bipartite graphs (Theorem 1.4 of [ShTy23], result page). The conjecture itself, $\mathrm{ex}_3(n,\mathcal F)=o(n^2)$ for $k=s+3$ , is open for every $s\ge4$ , the $(7,4)$ case included, in every cited source. No resolution and no proof claim was found in the search whose scope the Current assessment records. This is a bounded negative finding, not a certificate of openness.

BES73: Brown, W. G., Erdős, P. and Sós, V. T., Some extremal problems on $r$ -graphs. New Directions in the Theory of Graphs (Proc. Third Ann Arbor Conf., Univ. Michigan, 1971), Academic Press (1973), 53--63 (the venue from the running head of the Rényi archive scan and from the arXiv abstract of Glock, Kim, Lichev, Pikhurko and Sun, arXiv:2403.04474; the site's reference text gives "(1973), 53--63"); the definition, p. 55; the Theorem of Section 4 and the remark after it, p. 59. Cited from the Rényi archive copy (https://users.renyi.hu/~p_erdos/), an eleven-page typescript scan of printed pp. 53--63. Library home: Brown, Erdős and Sós 1973.
Va99: Various, Some of Paul's favorite problems. Booklet produced for the conference "Paul Erdős and his mathematics", Budapest, July 1999; item 3.64 in Section 3.5, Set-systems. Library home: Various 1999 (the booklet's scan is image-only, in paired pages, and the item's leaf carries no legible printed page number).
AlSh06: Alon, N. and Shapira, A., On an extremal hypergraph problem of Brown, Erdős and Sós. Combinatorica 26 (2006), no. 6, 627--645, doi:10.1007/s00493-006-0035-9; Theorem 1, p. 2 of the authors' public preprint (https://www.cs.tau.ac.il/~nogaa/PDFS/asaferdos4.pdf, 15 pages, dated 2004). Not cited by the site. Library home: Alon and Shapira 2006.
KeLo20: Keevash, P. and Long, J., The Brown--Erdős--Sós conjecture for hypergraphs of large uniformity. arXiv:2007.14824v1 (29 July 2020); Proc. Amer. Math. Soc., doi:10.1090/proc/15487 (2021); Conjectures 1--2 and Theorem 3, pp. 1--2 of the arXiv version. Not cited by the site. Library home: Keevash and Long 2020.
ShTy23: Shapira, A. and Tyomkyn, M., A new approach for the Brown--Erdős--Sós problem. arXiv:2301.07758v1 (18 January 2023); EuroComb 2023 proceedings, doi:10.5817/cz.muni.eurocomb23-112, 812--818; Israel J. Math. 267 (2025), no. 2, 717--728, doi:10.1007/s11856-025-2714-5; Conjectures 1.1--1.3, p. 2; Theorem 1.4, p. 3 of the arXiv version. Not cited by the site. Library home: Shapira and Tyomkyn 2023.
JMMS25: Janzer, O., Methuku, A., Milojević, A. and Sudakov, B., Power saving for the Brown--Erdős--Sós problem. Discrete Analysis 2025:5, 16 pp., doi:10.19086/da.138191 (published 10 July 2025; arXiv:2311.12765v2 is the journal typesetting); Conjecture 1.1 and Theorem 1.2, p. 2; Theorem 1.3, p. 3. Not cited by the site. Library home: Janzer 2025.
Er74c: Erdős, Paul, Extremal problems on graphs and hypergraphs. Hypergraph Seminar, Lecture Notes in Math. 411 (1974), 75--84; pp. 80--81. Not cited by the site. Library home: Erdős 1974; cited from the Rényi archive copy (https://users.renyi.hu/~p_erdos/), a ten-page typescript scan of printed pp. 75--84.
GiSo26: Gishboliner, L. and Solymosi, J., A simple counting argument for dense linear hypergraphs. arXiv:2606.25931 (24 June 2026, 7 pages), a preprint; Theorem 1.1 and Corollary 1.4, pp. 1--2; not held; a lead, recorded below. [SaTy25] Santos, G. and Tyomkyn, M., The Brown--Erdős--Sós conjecture in dense triple systems. arXiv:2508.09841 (13 August 2025); a lead, cited from its abstract. The $(k+2,k)$ -problem papers named below are cited from their arXiv abstracts.

Problem 1157

Status

Proof claims

Discussion