Abstract
The Boolean lattice (Formula presented.) consists of all subsets of (Formula presented.) partially ordered under the containment relation. Sperner's Theorem states that the largest antichain of the Boolean lattice is given by a middle layer: the collection of all sets of size (Formula presented.), or also, if (Formula presented.) is odd, the collection of all sets of size (Formula presented.). Given (Formula presented.), choose each subset of (Formula presented.) with probability (Formula presented.) independently. We show that for every constant (Formula presented.), the largest antichain among these subsets is also given by a middle layer, with probability tending to 1 as (Formula presented.) tends to infinity. This (Formula presented.) is best possible, and we also characterize the largest antichains for every constant (Formula presented.). Our proof is based on some new variations of Sapozhenko's graph container method.
Original language | English (US) |
---|---|
Article number | e21259 |
Journal | Random Structures and Algorithms |
Volume | 66 |
Issue number | 1 |
DOIs | |
State | Published - Jan 2025 |
Keywords
- graph container method
- random poset
- Sperner's theorem
ASJC Scopus subject areas
- Software
- General Mathematics
- Computer Graphics and Computer-Aided Design
- Applied Mathematics