On a Turán-type hypergraph problem of Brown, Erdős and T. Sós

We let G(r)(n,m) denote the set of r-uniform hypergraphs with n vertices and m edges, and f(r)(n,p,s) is the smallest m such that every member of G(r)(n,m) contains a member of G(r)(p,s). In this paper we are interested in the growth of f(r)(n,p,s) for fixed values r,p and s. Brown, Erdős and Sós [Some external problems on r-graphs, in: New Directions in the Theory of Graphs, Proceedings of the Third Annual Arbor Conference on Graph Theory, Academic Press, New York, 1973, pp. 55-63] proved that for r>k⩾2 and s⩾3 we have f(r)(n,s(r-k)+k,s)=Θ(nk). This suggests the difficult question whether f(r)(n,s(r-k)+k+1,s)=o(nk). This was first established for r=s=3 and k=2 by Ruzsa and Szemerédi [Trible systems with no six points carrying three triangles, in: Combinatorics (Keszthely, 1976), Colloquia Mathematics Societies Janos Bolyai, vols. II, 18, 1976, pp. 939-945]. Then for s=3 and k=2 Erdős et al. [Graphs Combin. 2 (1986) 113-121] extended this result for any r, and they conjectured that it also holds for k=2 and any s. In this note we show that it holds with ⌊log2s⌋ in place of 1, i.e.,f(r)(n,s(r-k)+k+⌊log2s⌋,s)=o(nk)forallr>k⩾2ands⩾3.In addition we show that the conjecture holds for r>k⩾3 and s=4, i.e.,f(r)(n,4(r-k)+k+1,4)=o(nk).