2003/06/06 by John Talbot, Talbot, John
Mathematics · #05D05 #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Point processes and geometric inequalities #math.CO #msc:05D05
paper · pdf · doi:10.48550/arxiv.math/0306119
10 pages, 1 figure
arxiv created 2003/06/06 · openalex publication_date 2003/06/06 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 generalization of these problems. Given an intersecting family of r-sets from an n-set and 1≤ k ≤ r, how many k-sets can occur as pairwise intersections of sets from the family? For k=r and k=1 this reduces to the problems described above. We answer this question exactly for all values of k and r, when n is sufficiently large. We also characterize the extremal families.