Minimum saturated families of sets

Abstract

We call a family $\mathcal{F}$ of subsets of $[n]$ $s$-saturated if it contains no $s$ pairwise disjoint sets, and moreover no set can be added to $\mathcal{F}$ while preserving this property (here $[n]=\{1,\dots ,n\}$). More than 40 years ago, Erdő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 $\frac{1}{2}\cdot 2^n$, but, as was mentioned by Frankl and Tokushige, even obtaining a slightly better bound of $(1/2+\epsilon )2^n$, for some fixed $\epsilon >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 $|{\mathcal{F}}_1|+\dots +|{\mathcal{F}}_s|$ where ${\mathcal{F}}_1,\dots ,{\mathcal{F}}_s$ are families of subsets of $[n]$, such that there are no $s$ pairwise disjoint sets, one from each family ${\mathcal{F}}_i$, and furthermore no set can be added to any of the families while preserving this property. We show that $|{\mathcal{F}}_1|+\dots +|{\mathcal{F}}_s|\ge (s-1)\cdot 2^n$, which is tight e.g.\ by taking ${\mathcal{F}}_1$ to be empty, and letting the remaining families be the families of all subsets of $[n]$.

8 pages