On a Turán-type hypergraph problem of Brown, Erdős and T. Sós (Q2566157): Difference between revisions

\(f^{(r)}(n,p,s)\) is the smallest \(m\) such that every \(r\)-uniform hypergraph with \(n\) vertices and \(m\) edges contains a \(p\)-uniform hypergraph with \(s\) edges. Generalizing to hypergraphs a graph problem of \textit{P. Erdős} [Theory Graphs Appl., Proc. Symp. Smolenice 1963, 29--36 (1964; Zbl 0161.20501)], \textit{V. T. Sós, P. Erdős} and the reviewer [Period. Math. Hung. 3, 221--228 (1973; Zbl 0269.05111), New Direct. Theory Graphs, Proc. Third Ann Arbor Conf., Univ.\ Michigan 1971, 53--63 (1973; Zbl 0258.05132)] proved that, for any \(k>r\), \(s>1\) there exist positive constants \(c_{k,r}\), \(c_k\) such that \(f^{(r)}(n,k,s)>c_{k,s}n^{\frac{rs-k}{s-1}}\), and also that \(f^{(3)}(n,k,k-2)\leq c_kn^2\). These results motivate Conjecture 1: \(f^{(r)}(n,s(r-k)+k+1,s)=\text{o}(n^k)\). In Theorem 1: For all integers \(r>k\geq2\), \(s\geq3\), \(f^{(r)}(n,s(r-k)+k+\left\lfloor\log s\right\rfloor,s)=\text{o}(n^k)\), the authors generalize their earlier result for \(k=2\) [Combinatorica 25, 77--84 (2005; Zbl 1065.05068)], and results of \textit{I. Z. Ruzsa} and \textit{E. Szemerédi}, [Combinatorics, Keszthely 1976, Colloq. Math. János Bolyai 18, 939--945 (1978; Zbl 0393.05031)] and \textit{P. Erdős, P. Frankl} and \textit{V. Rödl} [Graphs Comb. 2, 113--121 (1986; Zbl 0593.05038)]. A result of \textit{P. Frankl} and \textit{V. Rödl} [Random Struct. Algorithms 20, 131--164 (2002; Zbl 0995.05141)] is applied to prove Theorem 2: For all integers \(r>k\geq3\), \(f^{(r)}(n,4(r-k)+k+1,4)=\text{o}(n^k)\).