UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Minimum saturated families of sets

Bucić, M; Letzter, S; Sudakov, B; Tran, T; (2018) Minimum saturated families of sets. Bulletin of the London Mathematical Society , 50 (4) pp. 725-732. 10.1112/blms.12184. Green open access

[thumbnail of saturated-revision.pdf]
Preview
Text
saturated-revision.pdf - Accepted Version

Download (267kB) | Preview

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˝os 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 1 2 · 2 n, 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) · 2 n, which is tight e.g. by taking F1 to be empty, and letting the remaining families be the families of all subsets of [n].

Type: Article
Title: Minimum saturated families of sets
Open access status: An open access version is available from UCL Discovery
DOI: 10.1112/blms.12184
Publisher version: http://dx.doi.org/10.1112/blms.12184
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
UCL classification: UCL
UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics
URI: https://discovery.ucl.ac.uk/id/eprint/10107224
Downloads since deposit
88Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item