Extremal problems on set systems

For a family $boldmath{F}(k) = {{mathcal F}_1^{(k)}, {mathcal F}_2^{(k)},ldots,{mathcal F}_t^{(k)}}$ 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 $boldmath{F}(k) = {{mathcal F}_1^{(k)},{mathcal F}_2^{(k)}}$ and prove that n^k?2r_k(n)≤ex (n_k², F (k))≤c_kn^k?1 holds. 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.