Minimum saturated families of sets

Authors

Abstract: We call a family

m a t h c a l F

of subsets of

[n]

s

-saturated if it contains no

s

pairwise disjoint sets, and moreover no set can be added to

m a t h c a l F

while preserving this property (here

[n] = 1, l d o t s, n

). More than 40 years ago, ErdH{o}s and Kleitman conjectured that an

s

-saturated family of subsets of

[n]

has size at least

(1 - 2^{- (s - 1)}) 2^{n}

. It is easy to show that every

s

-saturated family has size at least

f r a c 12 c d o t 2^{n}

, but, as was mentioned by Frankl and Tokushige, even obtaining a slightly better bound of

(1 / 2 + v a r e p s i l o n) 2^{n}

, for some fixed

v a r e p s i l o n > 0

, seems difficult. In this note, we prove such a result, showing that every

s

-saturated family of subsets of

[n]

has size at least

(1 - 1 / s) 2^{n}

. This lower bound is a consequence of a multipartite version of the problem, in which we seek a lower bound on

| m a t h c a l F_{1} | + l d o t s + | m a t h c a l F_{s} |

where

m a t h c a l F_{1}, l d o t s, m a t h c a l F_{s}

are families of subsets of

[n]

, such that there are no

s

pairwise disjoint sets, one from each family

m a t h c a l F_{i}

, and furthermore no set can be added to any of the families while preserving this property. We show that

| m a t h c a l F_{1} | + l d o t s + | m a t h c a l F_{s} | g e (s - 1) c d o t 2^{n}

, which is tight e.g. by taking

m a t h c a l F_{1}

to be empty, and letting the remaining families be the families of all subsets of

[n]

.

Recommendations

Cited in

(9)

This page was built for publication: Minimum saturated families of sets