Maximum antichains in random subsets of a finite set
type: Item
instance of: scholarly article
title: Maximum antichains in random subsets of a finite set
zbMATH Open document ID: 0949.05084
author: Deryk Osthus
published in: Journal of Combinatorial Theory. Series A
publication date: 2000-11-29T00:00:00Z
review text: This nice paper investigates the maximum antichains in random subsets of a finite set, taking every subset independently with probability \(p.\) The main result states: if \(pn/\log n \rightarrow \infty\) then the analogue of the Sperner theorem holds, namely the biggest antichain out of those random subsets is formed almost surely by all chosen subsets of size \(\lfloor n/2\rfloor \). This is almost surely not the case if \(pn \not\rightarrow \infty.\)
Mathematics Subject Classification ID: 05D05
zbMATH DE Number: 1474639
zbMATH Keywords: Sperner theorem
zbMATH Keywords: random poset
zbMATH Keywords: chain covers
reviewed by: Péter L. Erdős
MaRDI profile type: Publication
full work available at URL: jcta.1999.3048
OpenAlex ID: W2003315074
cites work: Q4004078
cites work: Q3142411
cites work: Poisson approximation for large deviations
cites work: The width of random subsets of Boolean lattices
cites work: The length of random subsets of Boolean lattices
cites work: Small sublattices in random subsets of Boolean lattices
cites work: A short proof of Sperner's lemma
cites work: Q5511767
DOI: 10.1006/JCTA.1999.3048
description: scientific article; zbMATH DE number 1474639