A random version of Sperner's theorem

DOI10.1016/J.JCTA.2014.08.003MaRDI QIDQ458289zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

antichaincontainer methodBoolean lattice

Mathematics Subject Classification ID

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

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$.

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

Cites work

• scientific article; zbMATH DE number 3223273 (Why is no real title available?)
• scientific article; zbMATH DE number 3256524 (Why is no real title available?)
• Hypergraph containers
• Maximum antichains in random subsets of a finite set
• Maximum-size antichains in random set-systems
• Small sublattices in random subsets of Boolean lattices
• Sperner's theorem and a problem of Erdős, Katona and Kleitman
• The height of a random partial order: Concentration of measure
• The length of random subsets of Boolean lattices
• The width of random subsets of Boolean lattices

Cited in

(24)

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

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)