The longest chain among random points in Euclidean space
HTML articles powered by AMS MathViewer
- by Béla Bollobás and Peter Winkler PDF
- Proc. Amer. Math. Soc. 103 (1988), 347-353 Request permission
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
- R. M. Baer and P. Brock, Natural sorting over permutation spaces, Math. Comp. 22 (1968), 385–410. MR 228216, DOI 10.1090/S0025-5718-1968-0228216-8
- P. Erdös and G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463–470. MR 1556929
- J. M. Hammersley, A few seedlings of research, Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability (Univ. California, Berkeley, Calif., 1970/1971) Univ. California Press, Berkeley, Calif., 1972, pp. 345–394. MR 0405665
- J. M. Hammersley, Postulates for subadditive processes, Ann. Probability 2 (1974), 652–680. MR 370721, DOI 10.1214/aop/1176996611
- J. F. C. Kingman, Subadditive ergodic theory, Ann. Probability 1 (1973), 883–909. MR 356192, DOI 10.1214/aop/1176996798
- J. F. C. Kingman, Subadditive ergodic theory, Ann. Probability 1 (1973), 883–909. MR 356192, DOI 10.1214/aop/1176996798
- B. F. Logan and L. A. Shepp, A variational problem for random Young tableaux, Advances in Math. 26 (1977), no. 2, 206–222. MR 1417317, DOI 10.1016/0001-8708(77)90030-5 S. Pilpel, Descending subsequences of random permutations, IBM Research Report #52283, 1986.
- C. Schensted, Longest increasing and decreasing subsequences, Canadian J. Math. 13 (1961), 179–191. MR 121305, DOI 10.4153/CJM-1961-015-3
- Stephen M. Samuels and J. Michael Steele, Optimal sequential selection of a monotone sequence from a random sample, Ann. Probab. 9 (1981), no. 6, 937–947. MR 632967
- J. Michael Steele, Limit properties of random variables associated with a partial ordering of $R^{d}$, Ann. Probability 5 (1977), no. 3, 395–403. MR 438421, DOI 10.1214/aop/1176995800
- Stanislaw M. Ulam, Monte Carlo calculations in problems of mathematical physics, Modern mathematics for the engineer: Second series, McGraw-Hill, New York, 1961, pp. 261–281. MR 0129165
- A. M. Veršik and S. V. Kerov, Asymptotic behavior of the Plancherel measure of the symmetric group and the limit form of Young tableaux, Dokl. Akad. Nauk SSSR 233 (1977), no. 6, 1024–1027 (Russian). MR 0480398
- Peter Winkler, Random orders, Order 1 (1985), no. 4, 317–331. MR 787544, DOI 10.1007/BF00582738
- Peter Winkler, Connectedness and diameter for random orders of fixed dimension, Order 2 (1985), no. 2, 165–171. MR 815862, DOI 10.1007/BF00334854
Additional Information
- © Copyright 1988 American Mathematical Society
- 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