A random version of Sperner's theorem

DOI10.1016/J.JCTA.2014.08.003zbMATH Open1301.05347arXiv1404.5079OpenAlexW2111375633MaRDI QIDQ458289FDOQ458289

Authors: József Balogh, Richard Mycroft, Andrew Treglown 

Publication date: 7 October 2014

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: Let $mathcalP(n)$ denote the power set of $[n]$, ordered by inclusion, and let $mathcalP(n,p)$ be obtained from $mathcalP(n)$ by selecting elements from $mathcalP(n)$ independently at random with probability $p$. A classical result of Sperner asserts that every antichain in $mathcalP(n)$ has size at most that of the middle layer, $$. In this note we prove an analogous result for $mathcalP(n,p)$: If $pnightarrowinfty$ then, with high probability, the size of the largest antichain in $mathcalP(n,p)$ is at most $$. This solves a conjecture of Osthus who proved the result in the case when $pn/lognightarrowinfty$. Our condition on $p$ is best-possible. In fact, we prove a more general result giving an upper bound on the size of the largest antichain for a wider range of values of $p$.

Full work available at URL: https://arxiv.org/abs/1404.5079

Recommendations

• Maximum antichains in random subsets of a finite set
• Maximum-size antichains in random set-systems
• The width of random subsets of Boolean lattices
• scientific article; zbMATH DE number 937456
• On a continuous analog of Sperner's problem

zbMATH Keywords

antichaincontainer methodBoolean lattice

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Extremal set theory (05D05)

Cites Work

• Hypergraph containers
• Maximum-size antichains in random set-systems
• The height of a random partial order: Concentration of measure
• Maximum antichains in random subsets of a finite set
• The width of random subsets of Boolean lattices
• Small sublattices in random subsets of Boolean lattices
• The length of random subsets of Boolean lattices
• Sperner's Theorem and a Problem of Erdős, Katona and Kleitman
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (22)

• Applications of graph containers in the Boolean lattice
• On the number of points in general position in the plane
• Random Lochs’ Theorem
• Existence thresholds and Ramsey properties of random posets
• Title not available (Why is that?)
• On the random version of Ważewski theorem
• A Random Version of Shepp's Urn Scheme
• On Erdős–Ko–Rado for Random Hypergraphs II
• Online containers for hypergraphs, with applications to linear equations
• Uniform chain decompositions and applications
• Supersaturation, counting, and randomness in forbidden subposet problems
• Supersaturation in posets and applications involving the container method
• Maximum antichains in random subsets of a finite set
• Multicolor chain avoidance in the Boolean lattice
• The width of random subsets of Boolean lattices
• Maximum-size antichains in random set-systems
• On some extremal and probabilistic questions for tree posets
• On a continuous analog of Sperner's problem
• The random version of the Kirzbraun-Valentine extension theorem
• Improved bounds for cross-Sperner systems
• A Note on Infinite Antichain Density
• Supersaturation, counting, and randomness in forbidden subposet problems

This page was built for publication: A random version of Sperner's theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q458289)