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?)

  • [1] R. M. Baer and P. Brock, Natural sorting over permutation spaces, Math. Comp. 22 (1968), 385-510. MR 0228216 (37:3800)
  • [2] P. Erdös and Gy. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463-470. MR 1556929
  • [3] J. M. Hammersley, A few seedlings of research, Proc. Sixth Berkeley Sympos. Math. Stat. Prob., Univ. of California Press, Berkeley, Calif., 1972, pp. 345-394. MR 0405665 (53:9457)
  • [4] -, Postulates for subadditive processes, Ann. Probab. 2 (1974), 652-680. MR 0370721 (51:6947)
  • [5] H. Kesten, Comment on J. F. C. Kingman's article, Ann. Probab. 1 (1973), p. 903. MR 0356192 (50:8663)
  • [6] J. F. C. Kingman, Subadditive ergodic theory, Ann. Probab. 1 (1973), 883-909. MR 0356192 (50:8663)
  • [7] B. F. Logan and L. A. Shepp, A variational problem for random Young tableaux, Adv. in Math. 26 (1977), 206-222. MR 1417317 (98e:05108)
  • [8] S. Pilpel, Descending subsequences of random permutations, IBM Research Report #52283, 1986.
  • [9] C. Schensted, Longest increasing and decreasing subsequences, Canad. J. Math. 13 (1961), 179-191. MR 0121305 (22:12047)
  • [10] S. M. Samuels and J. M. Steele, Optimal sequential selection of a monotone sequence from a random sample, Ann. Probab. 9 (1981), 937-947. MR 632967 (83c:60069)
  • [11] J. M. Steele, Limit properties of random variables associated with a partial ordering of $ {R^d}$, Ann. Probab. 5 (1977), 395-403. MR 0438421 (55:11334)
  • [12] S. M. Ulam, Monte Carlo calculations in problems of mathematical physics, Modern Mathematics for the Engineer (E. F. Beckenbach, Ed.), McGraw-Hill, New York, 1961. MR 0129165 (23:B2202)
  • [13] A. M. Veršik and S. V. Kerov, Asymptotics of the Plancherel measure of the symmetric group and the limiting form of Young tableaux, Dokl. Akad. Nauk SSSR 233 (1977), 1024-1028. MR 0480398 (58:562)
  • [14] P. Winkler, Random orders, Order 1 (1985), 317-331. MR 787544 (86j:06004)
  • [15] -, Connectedness and diameter for random orders of fixed dimension, Order 2 (1985), 165-171. MR 815862 (87h:06004)

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

American Mathematical Society