Extremal problems on set systems

For a family \documentclass{article}\pagestyle{empty}\begin{document}$\boldmath{F}(k) = \{{\mathcal F}_1^{(k)}, {\mathcal F}_2^{(k)},\ldots,{\mathcal F}_t^{(k)}\}$\end{document} of k ‐uniform hypergraphs let ex ( n , F ( k )) denote the maximum number of k ‐tuples which a k ‐uniform hypergraph on n vertices may have, while not containing any member of F ( k ). Let r k ( n ) denote the maximum cardinality of a set of integers Z ⊂[ n ], where Z contains no arithmetic progression of length k . For any k ≥3 we introduce families \documentclass{article}\pagestyle{empty}\begin{document}$\boldmath{F}(k) = \{{\mathcal F}_1^{(k)},{\mathcal F}_2^{(k)}\}$\end{document} and prove thatn k −2 r k ( n )≤ex ( n k 2 , F ( k ))≤ c k n k −1holds. We conjecture that ex( n , F ( k ))= o ( n k −1 ) holds. If true, this would imply a celebrated result of Szemerédi stating that r k ( n )= o ( n ). By an earlier result o Ruzsa and Szemerédi, our conjecture is known to be true for k =3. The main objective of this article is to verify the conjecture for k =4. We also consider some related problems. © 2002 Wiley Periodicals, Inc. Random Struct. Alg. 20: 131–164, 2002.