2006/05/07 by William Y. C. Chen, Chen, William Y. C., Jiuqiang Liu +3
Mathematics · #05D05 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05D05
paper · pdf · doi:10.48550/arxiv.math/0605171
14 pages; Final version, to appear in SIAM J. Discrete Math
arxiv created 2009/04/24 · arxiv updated 2009/12/01
A family of k-subsets A1, A2, ..., Ad on [n]=\1,2,..., n\ is called a (d, c)-cluster if the union A1∪ A2 ∪ ... ∪ 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 Chvátal's simplex theorem. We also show that for any d satisfying 3 ≤ d ≤ k and n ≥ (dk)/(d-1), if every (d, d+1\over 2)-cluster is intersecting, then |F|≤ n-1 \choose k-1 with equality only when F is a complete star. This result is an extension of both Frankl's theorem and Mubayi's theorem.