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

Noga Alon, Shoni Gilboa, Shay Gueron

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

תקציר

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.

שפה מקוריתאנגלית
מספר המאמר112027
כתב עתDiscrete Mathematics
כרך343
מספר גיליון10
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - אוק׳ 2020

הערה ביבליוגרפית

Publisher Copyright:
© 2020 Elsevier B.V.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'A probabilistic variant of Sperner ’s theorem and of maximal r-cover free families'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי