Wiki
Wiki

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

Updated


Claim. For all r,e≥3r,e\ge3, an rr-uniform hypergraph on nn vertices in which no (r−2)e+2+⌊log⁡2e⌋(r-2)e+2+\lfloor\log_2e\rfloor vertices span ee edges has o(n2)o(n^2) edges, so the problem's dr(e)d_r(e) is at most (r−2)e+2+⌊log⁡2e⌋(r-2)e+2+\lfloor\log_2e\rfloor. The result is the main theorem of G. N. Sárközy and S. Selkow, An extension of the Ruzsa–Szemerédi theorem, Combinatorica 25 (2005), no. 1, 77--84. With fr(n,v,e)f_r(n,v,e) the largest number of edges of an rr-graph on nn vertices containing no ee edges spanned by vv vertices, Alon and Shapira record it as fr(n,e(r−k)+k+⌊log⁡2e⌋,e)=o(nk)f_r(n,e(r-k)+k+\lfloor\log_2e\rfloor,e)=o(n^k) (their display (4), p. 2, on the card alon_2006_extremal_hypergraph_problem_brown_erdos_sos); the case k=2k=2 is the bound above. Janzer, Methuku, Milojević and Sudakov quote the 33-uniform case, f(n,e+⌊log⁡2e⌋+2,e)=o(n2)f(n,e+\lfloor\log_2e\rfloor+2,e)=o(n^2) for every e≥3e\ge3, as their Theorem 1.2 (p. 2, on the card janzer_2025_power_saving_brown_erdos_sos_problem). The statement is recorded from these two citing papers.

Covers. The case e=3e=3 of Problem 1178 for every r≥3r\ge3: there ⌊log⁡23⌋=1\lfloor\log_2 3\rfloor=1, the bound equals 3r−33r-3, and the Brown–Erdős–Sós lower bound gives dr(3)=3r−3d_r(3)=3r-3, the case Erdős, Frankl and Rödl settled first (their claim page). For e≥4e\ge4 the bound exceeds the conjectured value and settles nothing.

Depends on. The Brown–Erdős–Sós lower bound, which supplies the matching lower half dr(3)≥3r−3d_r(3)\ge3r-3.

Acceptance. Refereed publication in Combinatorica (the publisher's record: volume 25, issue 1, pp. 77--84, issued December 2004 with no day recorded; this page is dated the issue's first day). The site labels the problem OPEN, so its commentary crediting the bound is not listed as reviewed evidence. This claim is partial, so the problem stays open.