## Abstract

We call a family F of subsets of [n] s-saturated if it contains no s pairwise disjoint sets, and moreover no set can be added to F while preserving this property (here [n] = {1, . . . , 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 1/2.2^{n}, but, as was mentioned by Frankl and Tokushige, even obtaining a slightly better bound of (1/2 + ε)2^{n}, for some fixed ε > 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 |F_{1}| + · · · + |F_{s}| where F_{1}, . . . ,F_{s} are families of subsets of [n], such that there are no s pairwise disjoint sets, one from each family F_{i}, and furthermore no set can be added to any of the families while preserving this property. We show that |F_{1}| + · · · + |F_{s}| ≥ (s − 1) · 2^{n}, which is tight, for example, by taking F_{1} to be empty, and letting the remaining families be the families of all subsets of [n].

Original language | English (US) |
---|---|

Pages (from-to) | 725-732 |

Number of pages | 8 |

Journal | Bulletin of the London Mathematical Society |

Volume | 50 |

Issue number | 4 |

DOIs | |

State | Published - Aug 2018 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- General Mathematics

## Keywords

- 05D05 (primary)
- 60C05 (secondary)