Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
Problem 1157
Statement. Let . Let be the family of all -uniform hypergraphs with vertices and edges. Determine
Formulation. The site's wording as of 2026-09-18T10:47Z (page last edited 24 January 2026). The wording binds , and and then uses an unbound and no ; is a fourth parameter, the number of edges, and is used only in the commentary's conjecture. With read as a parameter the question is well defined: since a hypergraph contains a member of as a subgraph exactly when some of its vertices span at least edges, is the largest number of edges of an -graph on vertices in which every vertices span fewer than edges. This is the function of Brown, Erdős and Sós ([BES73], p. 55): "we shall denote [sic; is meant] by . Thus denotes the smallest for which every contains at least one ", so the site's is their ; later papers write or with the vertex and edge counts in various orders, and this page keeps the site's letters ( the uniformity, vertices, edges, the exponent). The question is "Determine" and the site labels it OPEN, so the wording is a notation defect, not a degenerate statement, and the field describes the question as written. The 1999 booklet [Va99] states the same question as its item 3.64 in yet other letters (quoted below).
Status. Open. The problem is a whole family of Turán-type questions, and no cited source determines in general. What the cited sources prove: the general lower bound for and (the Theorem of Section 4 of [BES73], result page, which the authors remark, without proof, is sharp in the exponent when divides ); the Brown--Erdős--Sós conjecture, that once , proved for and every with a matching lower bound (Theorem 1 of [AlSh06], result page, extending the Ruzsa--Szemerédi -theorem and the Erdős--Frankl--Rödl case ) and, in its linear form, for every uniformity large enough in terms of the density (Theorem 3 of [KeLo20], result page); for 3-graphs and the approximate versions for (Sárközy and Selkow, quoted) and (Conlon, Gishboliner, Levanzov and Shapira, quoted), and the power saving for (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, for , is open for every , the 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.
Source. erdosproblems.com/1157, accessed 2026-09-18 at 10:47 UTC: the problem page (OPEN, with the site's note that no finite computation can settle it; last edited 24 January 2026; source keys [BES73], [Va99, 3.64]; commentary citing [1178], [716] and [1076]), its empty discussion thread and its empty proof-claim tab. Cite as: T. F. Bloom, Erdős Problem #1157, https://www.erdosproblems.com/1157, accessed 2026-09-18.
References.
- [BES73] Brown, W. G., Erdős, P. and Sós, V. T., Some extremal problems on -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_1973_extremal_problems_graphs.
- [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_some_pauls_favorite_problems (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_2006_extremal_hypergraph_problem_brown_erdos_sos.
- [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_2020_brown_erdos_sos_conjecture_hypergraphs_large.
- [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_2023_new_approach_brown_erdos_sos_problem.
- [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_power_saving_brown_erdos_sos_problem.
- [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: erdos_1974_extremal_problems_graphs_hypergraphs; 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 -problem papers named below are cited from their arXiv abstracts.
Formalization. Statement in
formal-conjectures,
file ErdosProblems/1157.lean, added on 2026-10-07 (no file existed on
2026-09-18; the tree's FormalConjectures/OEIS/1157.lean is an OEIS
sequence file, not this problem). At the pinned commit it declares erdos_1157 under category research open, AMS 5 with proof
sorry and no formal_proof attribute: for all and all ,
Hypergraph.configurationExtremalNumber n r k s equals an answer(sorry)
function of , , and ; its docstring binds , and ,
reading the site's unbound as the Formulation note does. The site's
indicator and the community database record a formalized statement since
2026-10-07 (on 2026-09-18 both recorded none), and the
database records the problem open (last update 23 January 2026), with no
formal proof and OEIS "possible".
Current assessment
The question (site formulation of 2026-09-18T10:47Z). The statement above; OPEN, with the site's note that no finite computation can settle it; last edited 24 January 2026. The site's commentary, in this page's words: the question is broad and hard, with many partial results, several of them in [BES73] itself; it displays that paper's lower bound , valid whenever and , and the Brown--Erdős--Sós conjecture that for all and the Turán number is whenever ; and it routes the case to Problem 1178, the case , to Problem 716, and the case , to Problem 1076. (The conjecture's display writes where the uniformity is ; the letters are read as in the Formulation note.) The thread and the proof-claim tab are empty. The cross-referenced pages are Problem 1178, Problem 716 and Problem 1076, whose accounts are their own. The question is read as the general determination of for all , and ; values for particular parameters, such as the limits for 3-graphs at recorded below or the graph values in Sections 2--3 of [BES73], are progress on the family and not partial claims here, and Problems 716 and 1076 carry the ones they ask for as claims.
The general lower bound. The Theorem of Section 4 of [BES73] (p. 59): "For integers and there exists a positive constant such that ", by the deletion method; the remark after it: "the exponent of in the above inequality is not always best possible. It can, however, be shown to be best possible when divides . For example, when and we know that , but here we obtain only ." This is the site's displayed bound. Read depth: claims checked for the theorem, the remark and the definitions (pp. 53--55, 59); the proof (pp. 59--61) is unchecked. The paper is a proceedings article; the Rényi archive copy is a typescript scan.
The conjecture and its proved cases. In the site's letters the conjecture asks for when , which [KeLo20] states as Conjecture 1 (p. 1): "For any and any -graph on vertices with no -configuration has edges" (their is the site's ). Against the lower bound above, whose exponent at is , the conjecture asks only for the upper bound ; for , Theorem 1 of [AlSh06] gives .
- , every : Theorem 1 of [AlSh06] (p. 2 of the preprint): "For any fixed we have, " (their is the site's , their the site's , three edges). It extends the Ruzsa--Szemerédi -theorem (, their (2)) and Erdős, Frankl and Rödl's for every (their (3), the case , of their (1), so vertices; the preprint's display prints the vertex count as , a misprint, since on vertices the statement fails for every ; [KeLo20], p. 2, states the same theorem as the case of -configurations); those two papers are not held and are cited second-hand from [AlSh06] and [KeLo20]. Acceptance evidence: Combinatorica 26 (2006), refereed. Read depth: claims checked for Theorem 1 in the authors' preprint; the journal text may differ from it; the proof (Sections 2--4) is unchecked.
- Large uniformity, : Theorem 3 of [KeLo20] (p. 2): "For any there is such that for all and for all there exists such that any linear -graph on vertices with no -configuration has ", where ; the paper says (p. 1) that Conjecture 1 "would follow from the case ", which reduces to this linear form, its Conjecture 2. Acceptance evidence: Proc. Amer. Math. Soc., refereed; cited from the arXiv v1, from which the journal text may differ; claims checked for the theorem and the conjectures, the bow-tie-graph proof unchecked. [GiSo26] (a 2026 preprint; Theorem 1.1 and Corollary 1.4, pp. 1--2) gives, by a counting argument, an explicit density threshold for linear -graphs and derives the large-uniformity theorem from it; a preprint, recorded as a lead.
- Approximate versions for 3-graphs (). Sárközy and Selkow, quoted as Theorem 1.2 of [JMMS25] (p. 2): for every ; Solymosi and Solymosi's and Conlon, Gishboliner, Levanzov and Shapira's (quoted on the same page; the last is arXiv:1912.08834), all by regularity, "barely below quadratic". Theorem 1.3 of [JMMS25] (p. 3): "For every , there exists some such that ", the first power saving near the Sárközy--Selkow threshold, toward the Gowers--Long conjecture ; the paper notes that an additive constant is unavoidable at because the Ruzsa--Szemerédi construction gives , and that and are also . Acceptance evidence: Discrete Analysis 2025:5, refereed; cited from the journal typesetting (arXiv v2); claims checked for the theorem and the introduction's account, the proof unchecked.
- Conditional: Theorem 1.4 of [ShTy23] (p. 3): "Conjecture 1.3 implies Conjecture 1.1", where Conjecture 1.1 asks for an absolute with -configurations in every 3-graph with edges and Conjecture 1.3 asks that every graph with edges contain some 2-degenerate graph on vertices with edges; a route, not a bound. Refereed (Israel J. Math. 267 (2025)); cited from the arXiv v1.
The quadratic regime (leads, from arXiv abstracts). For and , where [BES73] gives , the question becomes the value of , whose existence Brown, Erdős and Sós conjectured: Delcourt and Postle (arXiv:2210.01105) proved the limit exists for all , and Shangguan (arXiv:2210.11338, SIAM J. Discrete Math. 37 (2023) 1920--1929 per Crossref) extended this to every uniformity. For 3-graphs the limit is known for : is (Glock, Joos, Kim, Kühn, Lichev and Pikhurko, arXiv:2209.14177, ), and , and are due to Glock, Kim, Lichev, Pikhurko and Sun (arXiv:2403.04474). For , Pikhurko and Sun (arXiv:2506.01739) determine the limit for every uniformity at least 4 and give for 3-graphs only a lower bound they conjecture to be sharp. Letzter and Sgueglia (arXiv:2312.03856) and Wang and Zeng (arXiv:2603.19345) treat even at large uniformity (abstracts). This regime is Problem 1076's and is recorded here from the papers' abstracts. [SaTy25] proves the statement for linear triple systems of linear density above (abstract).
Erdős's statements. [Er74c], pp. 80--81, announces the two forthcoming papers with Brown and Sós as the beginning of an organized treatment of extremal questions for -graphs and singles out, as "the most attractive unsolved problem" (p. 80), the question (9) whether ; it records the authors' lower bound , their guess that the truth is below , which they could not prove even in the weaker form (9), and Szemerédi's then-recent announcement of a proof of (9). Then, for 3-graphs, ; display (10), ; display (11), , with the exact value of known to Erdős only for ; display (12), for every ; the guess (13) that for every ; and the "Theorem. Every contains either a or a " (p. 81). [Va99], item 3.64 (Section 3.5): "Find the maximum number of edges in a -uniform hypergraph in which every vertices span at most edges. This very difficult question contains the existence problem of block designs, the Ruzsa--Szemerédi Theorem etc." (the booklet's and are the site's and ).
Search scope. None of the routes below found a determination of in general, a proof of the conjecture for any at small uniformity, or a proof claim.
- The site: problem page, discussion thread and proof-claim tab, as accessed 2026-09-18; the formal-conjectures tree and the community database on 2026-09-18 and 2026-10-07 (the Formalization paragraph records what each held on each date).
- The primary sources, at the pages cited: [BES73] pp. 53--55 and 59, [Va99] item 3.64, [Er74c] pp. 80--81, [AlSh06] pp. 1--2, [KeLo20] pp. 1--2, [ShTy23] pp. 1--3, [JMMS25] pp. 1--3, [GiSo26] pp. 1--2.
- Crossref: the records of [JMMS25] (doi:10.19086/da.138191) and bibliographic queries for [AlSh06], [KeLo20], [ShTy23] and [BES73] (the last returned no record for the proceedings article).
- arXiv API: the records of 2007.14824, 2301.07758, 2311.12765, 2606.25931,
2508.09841, 1912.08834, 2210.11338, 2210.01105, 2209.14177, 2403.04474,
2506.01739, 2312.03856 and 2603.19345; the search
abs:"Brown-Erdős-Sós" OR abs:"Brown-Erdos-Sos" OR abs:"Brown, Erdős and Sós" OR abs:"Brown, Erdos and Sos"sorted by date (26 records: the papers named above, group-structure papers, coding-theory applications and a Ramsey variant; none claims the conjecture for at small uniformity). - Semantic Scholar: the citation lists of [AlSh06] by DOI (47 records) and of [KeLo20] and [JMMS25] by arXiv identifier (none indexed), by title.
Not searched: MathSciNet, zbMATH, Google Scholar, X. Cited second-hand: Ruzsa and Szemerédi 1978, Erdős, Frankl and Rödl 1986 and Sárközy and Selkow 2005, from the introductions of [AlSh06], [KeLo20] and [JMMS25]; the -problem papers, from their abstracts. [AlSh06], [KeLo20] and [ShTy23] are cited from the public preprints named in the References; their journal texts may differ.
Remaining gaps. (1) The Ruzsa--Szemerédi and Erdős--Frankl--Rödl theorems are cited second-hand from the introductions of [AlSh06] and [KeLo20]. (2) Proof coverage is statements only on every source; no proof is checked or reviewed. (3) [AlSh06], [KeLo20] and [ShTy23] are cited from the preprints; the journal texts may differ. (4) The quadratic regime and the dense-linear results are recorded from abstracts; the regime is Problem 1076's. (5) The site's notation defect is recorded above and not resolved with the site.
Known results
- Brown--Erdős--Sós, Theorem of Section 4 (1973): for , ; sharp in the exponent when , as the authors remark without proof.
- Alon--Shapira, Theorem 1 (2006): the conjecture for and every , with the matching lower bound.
- Keevash--Long, Theorem 3 (2020; PAMS 2021): the linear form for every .
- Janzer--Methuku--Milojević--Sudakov, Theorem 1.3 (2025): for ; Sárközy--Selkow's at quoted there.
- Shapira--Tyomkyn, Theorem 1.4 (2023; Israel J. Math. 2025): Conjecture 1.3 implies the constant-deficiency Conjecture 1.1.
- [Er74c] pp. 80--81 (1974): the program as Erdős stated it, displays (9)--(13).
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.
- alon_2006_extremal_hypergraph_problem_brown_erdos_sos
- alon_2006_extremal_hypergraph_problem_brown_erdos_sos / conjecture_1
- alon_2006_extremal_hypergraph_problem_brown_erdos_sos / proposition_5_1
- alon_2006_extremal_hypergraph_problem_brown_erdos_sos / proposition_5_2
- alon_2006_extremal_hypergraph_problem_brown_erdos_sos / theorem_1
- brown_1973_extremal_problems_graphs
- brown_1973_extremal_problems_graphs / conjecture_p62
- brown_1973_extremal_problems_graphs / theorem_p62
- brown_1973_extremal_problems_graphs / theorem_section_4
- erdos_1974_extremal_problems_graphs_hypergraphs
- janzer_2025_power_saving_brown_erdos_sos_problem
- janzer_2025_power_saving_brown_erdos_sos_problem / theorem_1_3
- keevash_2020_brown_erdos_sos_conjecture_hypergraphs_large
- keevash_2020_brown_erdos_sos_conjecture_hypergraphs_large / theorem_12
- keevash_2020_brown_erdos_sos_conjecture_hypergraphs_large / theorem_3
- shapira_2023_new_approach_brown_erdos_sos_problem
- shapira_2023_new_approach_brown_erdos_sos_problem / conjecture_1_1
- shapira_2023_new_approach_brown_erdos_sos_problem / theorem_1_4
- various_1999_some_pauls_favorite_problems