Families of sets with intersecting clusters

Abstract: A family of

k

-subsets

A_{1}, A_{2}, ..., A_{d}

on

[n] = 1, 2, ..., n

is called a

(d, c)

-cluster if the union

A_{1} c u p A_{2} c u p ... c u p A_{d}

contains at most

c k

elements with

c < d

. Let

m a t h c a l F

be a family of

k

-subsets of an

n

-element set. We show that for

k g e q 2

and

n g e q k + 2

, if every

(k, 2)

-cluster of

m a t h c a l F

is intersecting, then

m a t h c a l F

contains no

(k - 1)

-dimensional simplices. This leads to an affirmative answer to Mubayi's conjecture for

d = k

based on Chv'atal's simplex theorem. We also show that for any

d

satisfying

3 l e q d l e q k

and

n g e q f r a c d k d - 1

, if every

(d, d + 1 o v e r 2)

-cluster is intersecting, then

| m a t h c a l F | l e q n - 1 c h o o s e k - 1

with equality only when

m a t h c a l F

is a complete star. This result is an extension of both Frankl's theorem and Mubayi's theorem.

Recommendations

Cited in

(14)

This page was built for publication: Families of sets with intersecting clusters