AN EXTREMAL SET-INTERSECTION THEOREM v. CHVATAL

Let S be a set with w elements and Fa set of fc-point subsets of S, n ^ k + 1 ^ 5. I f |F |> () \ k — 1 / then there is a subset G = {Xly X2,.-,Xk} of F such that, for each i, all the k — 1 sets in G—{Xt} have at least one element in common but all the k sets in G have no element in common. An («, k)-set is a set F of distinct subsets of a set S with |S | = n and \X \ = k for all l e F. A set F of sets is m-intersecting if Z x n X2n... c\Xm ^ 0 whenever Xu X2,..., Xm e F. (In particular, every set of non-empty sets is 1-intersecting.) An (n, k, m)-set is an (n, k)-set F such that every m-intersecting subset of F is necessarily (m + l)-intersecting. Finally, let f(n, k, m) denote the largest cardinality of an (n, k, m)-set. Erdos, Chao Ko and Rado [3] proved that /(«, k, 1) = I J whenever n ̂ 2k. Besides, they proved that if n> 2k and F is an («, k, l)-set with \F \ = I I then F = {X c S: \X \ = k, r e l} for some r e S. The number / ( « , 2, 2) is simply the largest number of edges in a graph with n vertices which contains no triangle; by Turan's theorem [4], this number is [\n2]. Erdos [2] conjectured that /< ». *. 2) = whenever k ^ 3 and n ^ f fc. The following result settles his conjecture for A: = 3. ( n — 1 \I. Moreover, if r is un yn, /v, «. — i; oei>riut ' f = {X<r |X | = S: k,r G X} for some r e S. Proof Let F be an («, k, A: — l)-set of subsets of S. A subset T of S will be called a lid if | T | = k +1 and all the A>point subsets of T are included in F. LEMMA 1. Let XeF be contained in no lid. Then there is asetZ = Zx such that Zcz X, \Z \ = k- \ andZ < = Y for no Ye F, Y # X