Minimum saturated families of sets

• Published in: The Bulletin of the London Mathematical Society 2018-08, Vol.50 (4), p.725-732
• Main Authors: Bucić, Matija, Letzter, Shoham, Sudakov, Benny, Tran, Tuan
• Format: Article
• Language: English
• Subjects: 05D05 (primary); 60C05 (secondary)
• ISSN: 0024-6093; 1469-2120
• DOI: 10.1112/blms.12184

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))2n. It is easy to show that every s‐saturated family has size at least 12·2n, but, as was mentioned by Frankl and Tokushige, even obtaining a slightly better bound of (1/2+ε)2n, 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)2n. This lower bound is a consequence of a multipartite version of the problem, in which we seek a lower bound on |F1|+⋯+|Fs| where F1,…,Fs are families of subsets of [n], such that there are no s pairwise disjoint sets, one from each family Fi, and furthermore no set can be added to any of the families while preserving this property. We show that |F1|+⋯+|Fs|⩾(s−1)·2n, which is tight, for example, by taking F1 to be empty, and letting the remaining families be the families of all subsets of [n].