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

Abstract | References | Similar Articles | Additional Information

Abstract: Let random points be chosen independently from the uniform distribution on the unit -cube . Order the points coordinate-wise and let be the cardinality of the largest chain in the resulting partially ordered set.

We show that there are constants such that , and in probability. This generalizes results of Hammersley, Kingman and others on Ulam's ascending subsequence problem, and settles a conjecture of Steele.

**[1]**R. M. Baer and P. Brock,*Natural sorting over permutation spaces*, Math. Comp.**22**(1968), 385–410. MR**0228216**, https://doi.org/10.1090/S0025-5718-1968-0228216-8**[2]**P. Erdös and G. Szekeres,*A combinatorial problem in geometry*, Compositio Math.**2**(1935), 463–470. MR**1556929****[3]**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****[4]**J. M. Hammersley,*Postulates for subadditive processes*, Ann. Probability**2**(1974), 652–680. MR**0370721****[5]**J. F. C. Kingman,*Subadditive ergodic theory*, Ann. Probability**1**(1973), 883–909. With discussion by D. L. Burkholder, Daryl Daley, H. Kesten, P. Ney, Frank Spitzer and J. M. Hammersley, and a reply by the author. MR**0356192****[6]**J. F. C. Kingman,*Subadditive ergodic theory*, Ann. Probability**1**(1973), 883–909. With discussion by D. L. Burkholder, Daryl Daley, H. Kesten, P. Ney, Frank Spitzer and J. M. Hammersley, and a reply by the author. MR**0356192****[7]**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**, https://doi.org/10.1016/0001-8708(77)90030-5**[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**, https://doi.org/10.4153/CJM-1961-015-3**[10]**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****[11]**J. Michael Steele,*Limit properties of random variables associated with a partial ordering of 𝑅^{𝑑}*, Ann. Probability**5**(1977), no. 3, 395–403. MR**0438421****[12]**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****[13]**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****[14]**Peter Winkler,*Random orders*, Order**1**(1985), no. 4, 317–331. MR**787544**, https://doi.org/10.1007/BF00582738**[15]**Peter Winkler,*Connectedness and diameter for random orders of fixed dimension*, Order**2**(1985), no. 2, 165–171. MR**815862**, https://doi.org/10.1007/BF00334854

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