TY - JOUR

T1 - A probabilistic variant of Sperner ’s theorem and of maximal r-cover free families

AU - Alon, Noga

AU - Gilboa, Shoni

AU - Gueron, Shay

N1 - Funding Information:
This research was partially supported by National Science Foundation, USA Grant DMS-1855464 , U.S.-Israel Binational Science Foundation, USA Grant 2018267 , the Simons Foundation, USA , a Google Research Award, NSF-BSF, USA Grant 2018640 , the Israel Science Foundation Grant 1018/16 , and the Center for Cyber Law and Policy at the University of Haifa, Israel , in conjunction with the Israel National Cyber Bureau in the Prime Minister’s Office.
Funding Information:
This research was partially supported by National Science Foundation, USA Grant DMS-1855464, U.S.-Israel Binational Science Foundation, USA Grant 2018267, the Simons Foundation, USA, a Google Research Award, NSF-BSF, USA Grant 2018640, the Israel Science Foundation Grant 1018/16, and the Center for Cyber Law and Policy at the University of Haifa, Israel, in conjunction with the Israel National Cyber Bureau in the Prime Minister's Office.
Publisher Copyright:
© 2020 Elsevier B.V.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020/10

Y1 - 2020/10

N2 - A family of sets is called r-cover free if no set in the family is contained in the union of r (or less) other sets in the family. A 1-cover free family is simply an antichain with respect to set inclusion. Thus, Sperner's classical result determines the maximal cardinality of a 1-cover free family of subsets of an n-element set. Estimating the maximal cardinality of an r-cover free family of subsets of an n-element set for r>1 was also studied. In this note we are interested in the following probabilistic variant of this problem. Let S0,S1,…,Sr be independent and identically distributed random subsets of an n-element set. Which distribution minimizes the probability that S0⊆⋃i=1rSi? A natural candidate is the uniform distribution on an r-cover-free family of maximal cardinality. We show that for r=1 such distribution is indeed best possible. In a complete contrast, we also show that this is far from being true for every r>1 and n large enough.

AB - A family of sets is called r-cover free if no set in the family is contained in the union of r (or less) other sets in the family. A 1-cover free family is simply an antichain with respect to set inclusion. Thus, Sperner's classical result determines the maximal cardinality of a 1-cover free family of subsets of an n-element set. Estimating the maximal cardinality of an r-cover free family of subsets of an n-element set for r>1 was also studied. In this note we are interested in the following probabilistic variant of this problem. Let S0,S1,…,Sr be independent and identically distributed random subsets of an n-element set. Which distribution minimizes the probability that S0⊆⋃i=1rSi? A natural candidate is the uniform distribution on an r-cover-free family of maximal cardinality. We show that for r=1 such distribution is indeed best possible. In a complete contrast, we also show that this is far from being true for every r>1 and n large enough.

KW - Cover free families

KW - Sperner's theorem

UR - http://www.scopus.com/inward/record.url?scp=85086116340&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85086116340&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2020.112027

DO - 10.1016/j.disc.2020.112027

M3 - Article

AN - SCOPUS:85086116340

VL - 343

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 10

M1 - 112027

ER -