𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Maximum Antichains in Random Subsets of a Finite Set

✍ Scribed by Deryk Osthus

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
125 KB
Volume
90
Category
Article
ISSN
0097-3165

No coin nor oath required. For personal study only.

✦ Synopsis

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 wnΓ‚2x. This is almost surely not the case if pn Γ„ % .

πŸ“œ SIMILAR VOLUMES

Analysis of parallel algorithms for find
Analysis of parallel algorithms for finding a maximal independent set in a random hypergraph
✍ H. Chen; A. M. Frieze πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 726 KB

It is well known [9] that finding a maximal independent set in a graph is in class J%, and [lo] that finding a maximal independent set in a hypergraph with fixed dimension is in %JV"%' . It is not known whether this latter problem remains in A% when the dimension is part of the input. We will study

On the Maximum Number of Touching Pairs
On the Maximum Number of Touching Pairs in a Finite Packing of Translates of a Convex Body
✍ KΓ‘roly Bezdek πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 102 KB

Minkowski space M d =(R d , || ||) is just R d with distances measured using a norm || ||. A norm || || is completely determined by its unit ball {x Β₯ R d | ||x|| [ 1} which is a centrally symmetric convex body of the d-dimensional Euclidean space E d . In this note we give upper bounds for the maxi

A Method to Count the Positive 3-Subsets
A Method to Count the Positive 3-Subsets in a Set of Real Numbers with Non-Negative Sum
✍ Giuseppe Marino; Giampiero Chiaselotti πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 99 KB

Let a 1 , . . . , a n be n real numbers with non-negative sum. We show that if n β‰₯ 12 there exist at least n-1 2 subsets of {a 1 , . . . , a n } with three elements which have non-negative sum.