Families of Sets with Intersecting Clusters

William Y. C. Chen, Jiuqiang Liu, and Larry X.W. Wang

  Abstract:  A collection of k-subsets A1, A2,... , Ad on [n] = {1, 2,... , n}, not necessarily distinct, is called a (d, c)-cluster if the union A1 A2 ∪... âˆ?em> Ad contains at most ck elements with c < d. Let F be a family of k-subsets of an n-element set. We show that for k2 and n k + 2, if every (k, 2)-cluster of F is intersecting, then F contains no (k âˆ?1)-dimensional simplices. This leads to an affirmative answer to Mubayi's conjecture for d = k based on Chvatal's simplex theorem. We also show that for any d with 3d k and n , if every (d, d+1/2 )-cluster is intersecting, then |F| ≤ with equality only when F is a star. This result contains Frankl's theorem for d â‰?2 and Mubayi's theorem for d = 3 as special cases.

  AMS Classification:  05D05

  Keywords:  Clusters of subsets, Chvatal's simplex theorem, d-simplex, Erdös- Ko-Rado Theorem, Mubayi's conjecture

  Download:   PDF   

Return