| Texto completo | |
| Autor(es): |
Kohayakawa‚ Y.
;
Kreuter‚ B.
;
Osthus‚ D.
Número total de Autores: 3
|
| Tipo de documento: | Artigo Científico |
| Fonte: | RANDOM STRUCTURES & ALGORITHMS; v. 16, n. 2, p. 177-194, 2000. |
| Resumo | |
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) | |
| Processo FAPESP: | 96/04505-2 - Aspectos estruturais e algorítmicos de objetos combinatórios |
| Beneficiário: | Yoshiharu Kohayakawa |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |