The Erdos-Ko-Rado theorem tells us how large an intersecting family of r-sets from an n-set can be, while results due to Lovasz and Tuza give bounds on the number of singletons that can occur as pairwise intersections of sets from such a family.We consider a natural common generalization of these problems. Given an intersecting family of r-sets from an n-set and 1 less than or equal to k less than or equal to r, how many k-sets can occur as pairwise intersections of sets from the family? For k = r and I this reduces to the problems described above. We answer this question exactly for all values of k and r, when n is sufficiently large. Our result is in the form of a structure theorem characterizing the extremal families in terms of extremal families for the Lovasz-Tuza problem. (C) 2004 Elsevier Inc. All rights reserved.
展开▼
