Title of article
Maximum Antichains in Random Subsets of a Finite Set
Author/Authors
Osthus، نويسنده , , Deryk، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2000
Pages
11
From page
336
To page
346
Abstract
We consider the random poset P(n, p) which is generated by first selecting each subset of [n]={1, …, n} with probability p and then ordering the selected subsets by inclusion. We give asymptotic estimates of the size of the maximum antichain for arbitrary p=p(n). In particular, we prove that if pn/log n→∞, an analogue of Spernerʹs theorem holds: almost surely the maximum antichain is (to first order) no larger than the antichain which is obtained by selecting all elements of P(n, p) with cardinality ⌊n/2⌋. This is almost surely not the case if pn=↛∞.
Keywords
random partial order , Sperner property
Journal title
Journal of Combinatorial Theory Series A
Serial Year
2000
Journal title
Journal of Combinatorial Theory Series A
Record number
1530484
Link To Document