BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Minimum saturated families Letzter, Shoham


A family $F$ of subsets of $[n]$ is called $s$-saturated if it contains no $s$ pairwise disjoint sets, and moreover, no set can be added to $F$ while preserving this property. Over 40 years ago, Erdos and Kleitman conjectured that an $s$-saturated family of subsets of $[n]$ has size at least $(1 - 2/(s-1))2n$. We show that every $s$-saturated family has size at least $(1 - 1/s)2n$, thus providing the first non-trivial progress on the conjecture.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International