• 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