A Sharp Threshold for a Random Version of Sperner's Theorem

József Balogh, Robert A. Krueger

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Article numbere21259
JournalRandom Structures and Algorithms
Volume66
Issue number1
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'A Sharp Threshold for a Random Version of Sperner's Theorem'. Together they form a unique fingerprint.

Cite this