zbMATH — the first resource for mathematics

An extension of the Ruzsa-Szemerédi theorem. (English) Zbl 1065.05068
Summary: 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 fixed values \(r\), \(p\) and \(s\) for which \(f^{(r)}(n,p,s)\) grows quadratically with \(n\). A probabilistic construction of W. G. Brown, P. Erdős and V. T. Sós [Some extremal problems on \(r\)-graps, in New directions in the theory of graphs, Proc. 3rd Ann Arbor Conference on Graph Theory, Univ. Michigan 1971, 55–63 (1973; Zbl 0258.05132)] implies that \(f^{(r)}(n,s(r-2)+2,s)=\Omega(n^2)\). In the other direction the most interesting question they could not settle was whether \(f^{(3)}(n,6, 3)=o(n 2)\). This was proved by I. Z. Ruzsa and E. Szemerédi [Triple systems with no six points carrying three triangles, in Combinatorics, Keszthely, Colloq. Math. János Bolyai 18, 939–945 (1976; Zbl 0393.05031)]. Then P. Erdős, P. Frankl and V. Rödl [Graphs Comb. 2, 113–121 (1986; Zbl 0593.05038)] extended this result to any \(r\): \(f^{(r)}(n, 3(r-2)+3, 3)=o(n^2)\), and they conjectured that the bound of Brown, Erdős and T. Sós [loc. cit.] is best possible in the sense that \(f^{(r)}(n,s(r-2)+3,s)=o(n^2)\).
In this paper by giving an extension of the Erdős-Frankl-Rödl theorem (and thus the Ruzsa-Szemerédi theorem) we show that indeed the Brown-Erdős-Sós theorem is not far from being best possible. Our main result is \[ f^{(r)}(n,s(r-2)+2+\lfloor \log_2 s\rfloor,s)=o(n^2). \]

05C65 Hypergraphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: DOI