Growth rates for monotone subsequences

Authors:
A. del Junco and J. Michael Steele

Journal:
Proc. Amer. Math. Soc. **71** (1978), 179-182

MSC:
Primary 10K05

DOI:
https://doi.org/10.1090/S0002-9939-1978-0491571-6

MathSciNet review:
0491571

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The growth rate of the largest monotone subsequence of a uniformly distributed sequence is obtained. For with algebraic irrational the exponent of growth is found to be precisely the same as for a random sequence.

**[1]**P. Erdös and G. Szekeres,*A combinatorial problem in geometry*, Compositio Math.**2**(1935), 463–470. MR**1556929****[2]**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****[3]**A. Ya. Khinchin,*Continued fractions*, The University of Chicago Press, Chicago, Ill.-London, 1964. MR**0161833****[4]**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****[5]**L. Kuipers and H. Niederreiter,*Uniform distribution of sequences*, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. Pure and Applied Mathematics. MR**0419394****[6]**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**[7]**H. Niederreiter,*Metric theorems on the distribution of sequences*, Analytic number theory (Proc. Sympos. Pure Math., Vol. XXIV, St. Louis Univ., St. Louis, Mo., 1972) Amer. Math. Soc., Providence, R.I., 1973, pp. 195–212. MR**0337872**

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC:
10K05

Retrieve articles in all journals with MSC: 10K05

Additional Information

DOI:
https://doi.org/10.1090/S0002-9939-1978-0491571-6

Keywords:
Monotone subsequence,
uniform distribution,
algebraic irrationals,
discrepancy

Article copyright:
© Copyright 1978
American Mathematical Society