Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 

 

The longest chain among random points in Euclidean space


Authors: Béla Bollobás and Peter Winkler
Journal: Proc. Amer. Math. Soc. 103 (1988), 347-353
MSC: Primary 60C05; Secondary 06A10, 11K99
DOI: https://doi.org/10.1090/S0002-9939-1988-0943043-6
MathSciNet review: 943043
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ n$ random points be chosen independently from the uniform distribution on the unit $ k$-cube $ {[0,1]^k}$. Order the points coordinate-wise and let $ {{\mathbf{H}}_k}\left( n \right)$ be the cardinality of the largest chain in the resulting partially ordered set.

We show that there are constants $ {c_1},{c_2}, \ldots $ such that $ {c_k} < e,\;{\lim _{k \to \infty }}{c_k} = e$, and $ {\lim _{n \to \infty }}{{\mathbf{H}}_k}\left( n \right)/{n^{1/k}} = {c_k}$ in probability. This generalizes results of Hammersley, Kingman and others on Ulam's ascending subsequence problem, and settles a conjecture of Steele.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 60C05, 06A10, 11K99

Retrieve articles in all journals with MSC: 60C05, 06A10, 11K99


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1988-0943043-6
Article copyright: © Copyright 1988 American Mathematical Society