| Full text | |
| Author(s): |
Kohayakawa‚ Y.
;
Kreuter‚ B.
;
Osthus‚ D.
Total Authors: 3
|
| Document type: | Journal article |
| Source: | RANDOM STRUCTURES & ALGORITHMS; v. 16, n. 2, p. 177-194, 2000. |
| Abstract | |
We form the random poset P(n, p) by including each subset of [n] = {1,...,n} with probability p and ordering the subsets by inclusion. We investigate the length of the longest chain contained in P(n,p). For p greater than or equal to e/n we obtain the limit distribution of this random variable. For smaller p we give thresholds for the existence of chains which imply that almost surely the length of P(n,p) is asymptotically n(log n - log log 1/p)/log 1/p. (C) 2000 John Wiley & Sons, Inc. (AU) | |
| FAPESP's process: | 96/04505-2 - Structural and algorithmic aspects of combinatorial objects |
| Grantee: | Yoshiharu Kohayakawa |
| Support Opportunities: | Research Projects - Thematic Grants |