TY - JOUR
T1 - Minimum saturated families of sets
AU - Bucić, Matija
AU - Letzter, Shoham
AU - Sudakov, Benny
AU - Tran, Tuan
N1 - Funding Information:
Received 22 January 2018; revised 24 April 2018; published online 15 July 2018. 2010 Mathematics Subject Classification 05D05 (primary), 60C05 (secondary). The second-named author was supported by Dr. Max Rossler, the Walter Haefner Foundation and the ETH Zurich Foundation. The third and the fourth authors were supported by SNSF grant 200021-175573 and Humboldt Research Foundation, respectively.
Publisher Copyright:
© 2018 London Mathematical Society
PY - 2018/8
Y1 - 2018/8
N2 - 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 1/2.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].
AB - 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 1/2.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].
KW - 05D05 (primary)
KW - 60C05 (secondary)
UR - http://www.scopus.com/inward/record.url?scp=85050642201&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85050642201&partnerID=8YFLogxK
U2 - 10.1112/blms.12184
DO - 10.1112/blms.12184
M3 - Article
AN - SCOPUS:85050642201
SN - 0024-6093
VL - 50
SP - 725
EP - 732
JO - Bulletin of the London Mathematical Society
JF - Bulletin of the London Mathematical Society
IS - 4
ER -