Avoiding triple systems

A hypergraph \( H\) consists of a vertex set \( V\) together with a family \( E\) of subsets of \( V\), which are called the edges of \( H\). A \( r\)-uniform hypergraph, or \( r\)-graph, for short, is a hypergraph whose edge set consists of \( r\)-subsets of \( V\). A graph is just a special case of an \( r\)-graph with \( r=2\).

For a finite family \( \mathcal F\) of \( r\)-graphs, one can define the Turán number \( t_r(n,{\mathcal F})\) to be the largest integer \( t\) such that there is an \( r\)-graph on \( n\) vertices with \( t\) edges which does not contain any \( F \in {\mathcal F}\) as a subgraph. One family \( \mathcal F\) which has received considerable attention is the family \( F_3(k,s)\), consisting of all \( 3\)-graphs on \( k\) vertices with at least \( s\) edges.

The following conjecture was proposed by Brown, Erdös and Sós ([3], [4]).

A conjecture for triple systems [3]

Prove that \[ t(n, F_3(k,k-3))=o(n^2). \]

The case of \( k=6\) is a celebrated result of Ruzsa and Szemerédi [5], which has many applications (e.g., Füredi[1], and Frankl and Graham, and Rödl [2]).

Bibliography
1 Z. Füredi, Turán type problems, Surveys in Combinatorics, 1991 (Guildford, 1991), London Math. Soc. Lecture Notes Series 166, 253-300, Cambridge Univ. Press, Cambridge, 1991.

2 P. Frankl and R. L. Graham, and V. Rödl. On subsets of abelian groups with no \( 3\)-term arithmetic progression. J. Comb. Theory A 45 (1987), 157-161.

3 W. G. Brown, P. Erdös and V. T. Sós, On the existence of triangulated spheres in 3-graphs, and related problems, Period. Math. Hungar. 3 (1973), 221-228.

4 P. Erdös, Problems and results on graphs and hypergraphs: similarities and differences, Mathematics of Ramsey theory, Algorithms Combin., 5, (J. Nešetril and V. Rödl, eds.), 12-28, Springer, Berlin, 1990.

5 I. Z. Ruzsa and E. Szemerédi, Triple systems with no six points carrying three triangles, Combinatorics, Proc. Fifth Hungarian Colloq. Keszthely 1976, Vol. II, 939-945, Colloq. Math. Soc. János Bolyai 18, North Holland, Amsterdam-New York, 1978.