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 k ≥ 2 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 3 ≤ d ≤ k and n ≥ AMS Classification: 05D05 Keywords: Clusters of subsets, Chvatal's simplex theorem, d-simplex, Erdös- Ko-Rado Theorem, Mubayi's conjecture Download: PDF |