Minimum saturated families of sets. Issue 4 (15th July 2018)

• Record Type: Journal Article
• Authors: Bucić, Matija; Letzter, Shoham; Sudakov, Benny; Tran, Tuan
• Is Part Of: Bulletin of the London Mathematical Society. Volume 50:Issue 4(2018)
• Page Start: 725
• Page End: 732
• Publication Date: 2018-07-15
• Subjects: 05D05 (primary) -- 60C05 (secondary); Mathematics -- Periodicals; 510
• DOI: 10.1112/blms.12184
• Languages: English
• ISSNs: 0024-6093

Abstract

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 ] .