# 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).$

##### MSC:
 05C65 Hypergraphs 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
##### Keywords:
uniform hypergraph
Full Text: