Book contents
- Frontmatter
- Contents
- Preface
- 0 A few things you need to know
- 1 Longest increasing subsequences in random permutations
- 2 The Baik–Deift–Johansson theorem
- 3 Erdős–Szekeres permutations and square Young tableaux
- 4 The corner growth process: limit shapes
- 5 The corner growth process: distributional results
- Appendix Kingman's subadditive ergodic theorem
- Notes
- References
- Index
- References
References
Published online by Cambridge University Press: 05 October 2014
Book contents
- Frontmatter
- Contents
- Preface
- 0 A few things you need to know
- 1 Longest increasing subsequences in random permutations
- 2 The Baik–Deift–Johansson theorem
- 3 Erdős–Szekeres permutations and square Young tableaux
- 4 The corner growth process: limit shapes
- 5 The corner growth process: distributional results
- Appendix Kingman's subadditive ergodic theorem
- Notes
- References
- Index
- References
Summary
A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.
- Type
- Chapter
- Information
- The Surprising Mathematics of Longest Increasing Subsequences , pp. 340 - 347Publisher: Cambridge University PressPrint publication year: 2015
References
[1] 1943. The monomial expansion of determinantal symmetric functions. Proc. Royal Soc. Edinburgh (A), 61, 300–310.Google Scholar
[2] , and 1995. Hammersley's interacting particle process and longest increasing subsequences. Probab. Theory Related Fields, 103, 199–213.CrossRefGoogle Scholar
[3] , and 1999. Longest increasing subsequences: from patience sorting to the Baik–Deift–Johansson theorem. Bull. Amer. Math. Soc., 36, 413–432.CrossRefGoogle Scholar
[8] 1990. Modular Forms and Dirichlet Series in Number Theory. 2nd edition. Springer.CrossRefGoogle Scholar
[10] , and 1968. Natural sorting over permutation spaces. Math. Comp., 22, 385–410.CrossRefGoogle Scholar
[11] , , and 1999a. On the distribution of the length of the longest increasing subsequence of random permutations. J. Amer. Math. Soc., 12, 1119–1178.CrossRefGoogle Scholar
[12] , , and 1999b. On the distribution of the length of the second row of a Young diagram under Plancherel measure. Geom. Funct. Anal, 10, 702–731.Google Scholar
[13] , , and 2006. Cube root fluctuations for the corner growth model associated to the exclusion process. Electron. J. Probab., 11, 1094–1132.CrossRefGoogle Scholar
[14] , , , and 1954. Characters of the symmetric groups of degree 15 and 16. Math. Comp., 8, 212–216.CrossRefGoogle Scholar
[15] First passage percolation and competition models. Preprint, arXiv:1005.0649, 2010.
[16] , and 1992. The height of a random partial order: concentration of measure. Ann. Appl. Probab., 2, 1009–1018.CrossRefGoogle Scholar
[17] , and 1988. The longest chain among random points in Euclidean space. Proc. Amer. Math. Soc., 103, 347–353.CrossRefGoogle Scholar
[18] 2010. On the numerical evaluation of distributions in random matrix theory: A review. Markov Process. Related Fields, 16, 803–866.Google Scholar
[19] , , and 2000. Asymptotics of Plancherel measures for symmetric groups. J. Amer. Math. Soc., 13, 491–515.CrossRefGoogle Scholar
[20] , , and 2004. Concentration inequalities. Pages 208–240 of: , , and (eds), Advanced Lectures in Machine Learning. Springer.Google Scholar
[21] 1999. Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture. Cambridge University Press.CrossRefGoogle Scholar
[22] , and 2006. Fourier Series and Boundary Value Problems. 7th edition. McGraw-Hill.Google Scholar
[23] 2012. On the Vershik-Kerov conjecture concerning the Shannon-McMillan-Breiman theorem for the Plancherel family of measures on the space of Young diagrams. Geom. Funct. Anal., 22, 938–975.CrossRefGoogle Scholar
[24] , , and 2010. Representation Theory of the Symmetric Groups: The Okounkov-Vershik Approach, Character Formulas, and Partition Algebras. Cambridge University Press.CrossRefGoogle Scholar
[25] , , and 1951. On recursions connected with symmetric groups I. Canad. J. Math., 3, 328–334.CrossRefGoogle Scholar
[26] , and 1988. A connection formula for the second Painlevé transcendent. Arch. Rat. Mech. Anal., 103, 97–138.CrossRefGoogle Scholar
[27] , , and 1996. Local statistics for random domino tilings of the Aztec diamond. Duke Math. J., 85, 117–166.Google Scholar
[28] , , and 1998. The shape of a typical boxed plane partition. New York J. Math., 4, 137–165.Google Scholar
[29] , and 2003. An Introduction to the Theory of Point Processes, Vol. I: Elementary Theory and Methods. 2nd edition. Springer.Google Scholar
[30] 2000. Orthogonal Polynomials and Random Matrices: A Riemann-Hilbert Approach. American Mathematical Society.Google Scholar
[31] , and 1998. Large Deviations Techniques and Applications. 2nd edition. Springer.CrossRefGoogle Scholar
[32] , and 1999. On increasing subsequences of I.I.D. samples. Combin. Probab. Comput., 8, 247–263.CrossRefGoogle Scholar
[33] 2010. Probability: Theory and Examples. 4th edition. Cambridge University Press.CrossRefGoogle Scholar
[37] , , , and 1992. Alternating sign matrices and domino tilings. J. Algebraic Combin., 1, 111–132; 219–234.Google Scholar
[39] 1953. The degree formula for the skew-representations of the symmetric group. Proc. Amer. Math. Soc., 4, 740–744.CrossRefGoogle Scholar
[40] 1967. A direct proof of Stirling's formula. Amer. Math. Monthly, 74, 1223–1225.CrossRefGoogle Scholar
[41] 1968. An Introduction to Probability Theory and its Applications, Vol. 1. 3rd edition. Wiley.Google Scholar
[43] , , and 1954. The hook graphs of the symmetric group. Canad. J. Math., 6, 316–324.CrossRefGoogle Scholar
[44] , and 1982. A bijective proof of the hook-length formula. J. Algorithms, 3, 317–343.CrossRefGoogle Scholar
[45] 1991. On the length of the longest monotone subsequence in a random permutation. Ann. Appl. Probab., 1, 301–305.CrossRefGoogle Scholar
[46] 1993. The structure of random partitions of large integers. Trans. Amer. Math. Soc., 337, 703–735.CrossRefGoogle Scholar
[47] 1990. Symmetric functions and P-recursiveness. J. Combin. Theory Ser. A, 53, 257–285.CrossRefGoogle Scholar
[48] 1963. Statistical analysis based on a certain multivariate complex gaussian distribution (an introduction). Ann. Math. Statist., 34, 152–177.CrossRefGoogle Scholar
[50] , , and 1979. A probabilistic proof of a formula for the number of Young tableaux of a given shape. Adv. Math., 31, 104–109.CrossRefGoogle Scholar
[51] , , and 1984. Another probabilistic method in the theory of Young tableaux. J. Comb. Theory Ser. A, 37, 127–135.CrossRefGoogle Scholar
[52] 2002. Hydrodynamical methods for analyzing longest increasing subsequences. J. Comp. Appl. Math., 142, 83–105.CrossRefGoogle Scholar
[53] 1989. On mixed insertion, symmetry, and shifted Young tableaux. J. Comb. Theory Ser. A, 50, 196–225.CrossRefGoogle Scholar
[54] 1972. A few seedlings of research. Pages 345–394 of: , , and (eds), Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Theory of Statistics. University of California Press.Google Scholar
[55] 1980. The unreasonable effectiveness of mathematics. Amer. Math. Monthly, 87, 81–90.CrossRefGoogle Scholar
[56] , and 1918. Asymptotic formulae in combinatory analysis. Proc. London Math. Soc., s2-17, 75–115.CrossRefGoogle Scholar
[57] , and 1980. A boundary value problem associated with the second Painlevé transcendent and the Korteweg-de Vries equation. Arch. Rational Mech. Anal., 73, 35–51.CrossRefGoogle Scholar
[58] , and 2000. The Semicircle Law, Free Random Variables and Entropy. American Mathematical Society.Google Scholar
[59] , , , and 2009. Zeros of Gaussian Analytic Functions and Determinantal Point Processes. American Mathematical Society.CrossRefGoogle Scholar
[60] , , and Domino tilings and the arctic circle theorem. Preprint, arXiv:math/9801068, 1998.
[61] 1998. The longest increasing subsequence in a random permutation and a unitary random matrix model. Math. Res. Letters, 5, 63–82.CrossRefGoogle Scholar
[62] 2000. Shape fluctuations and random matrices. Commun. Math. Phys., 209, 437–476.CrossRefGoogle Scholar
[63] 2001. Discrete orthogonal polynomial ensembles and the Plancherel measure. Ann. Math., 153, 259–296.CrossRefGoogle Scholar
[64] 2002. Non-intersecting paths, random tilings and random matrices. Probab. Theory Related Fields, 123, 225–280.CrossRefGoogle Scholar
[65] 2001. On the distribution of the largest eigenvalue in principal components analysis. Ann. Stat., 29, 295–327.Google Scholar
[66] 1998. A differential model of growth of Young diagrams. Pages 111–130 of: (ed), Proceedings of the St Petersburg Mathematical Society Volume IV. American Mathematical Society.Google Scholar
[67] 1996. On increasing subsequences of random permutations. J. Comb. Theory Ser. A, 76, 148–155.CrossRefGoogle Scholar
[69] 1968. The ergodic theory of subadditive processes. J. Roy. Stat. Soc. B, 30, 499–510.Google Scholar
[70] 1970. Permutations, matrices, and generalized Young tableaux. Pacific J. Math., 34, 316–380.CrossRefGoogle Scholar
[71] 1998. The Art of Computer Programming, Vol. 3: Sorting and Searching. 2nd edition. Addison-Wesley.Google Scholar
[72] 2005. Orthogonal polynomial ensembles in probability theory. Probab. Surv., 2, 385–447.CrossRefGoogle Scholar
[75] , and 1981. The number of increasing subsequences of the random permutation. J. Comb. Theory Ser. A, 31, 1–20.CrossRefGoogle Scholar
[76] 1985a. An improved subadditive ergodic theorem. Ann. Probab., 13, 1279–1285.CrossRefGoogle Scholar
[78] 1999. Stochastic Interacting Systems: Contact, Voter and Exclusion Processes. Springer.CrossRefGoogle Scholar
[79] , and 1977. A variational problem for random Young tableaux. Adv. Math., 26, 206–222.CrossRefGoogle Scholar
[80] 2003. Determinantal probability measures. Publ. Math. Inst. Hautes Études Sci., 98, 167–212.CrossRefGoogle Scholar
[81] 2014. Determinantal probability: basic properties and conjectures. To appear in Proc. International Congress of Mathematicians, Seoul, Korea.Google Scholar
[82] , and 2003. Stationary determinantal processes: phase multiplicity, Bernoullicity, entropy, and domination. Duke Math. J., 120, 515–575.Google Scholar
[83] 1975. The coincidence approach to stochastic point processes. Adv. Appl. Prob., 7, 83–122.CrossRefGoogle Scholar
[86] 2006. Last-passage percolation with general weight distribution. Markov Process. Related Fields, 273–299.Google Scholar
[87] 1976. The largest degrees of irreducible characters of the symmetric group. Math. Comp., 30, 624–631.CrossRefGoogle Scholar
[89] , and 1993. An Introduction to the Fractional Calculus and Fractional Differential Equations. Wiley-Interscience.Google Scholar
[90] , and 2005. The motion of a second class particle for the tasep starting from a decreasing shock profile. Ann. Appl. Probab., 15, 1227–1259.CrossRefGoogle Scholar
[92] , , and 1997. A direct bijective proof of the hook-length formula. Discr. Math. Theor. Comp. Sci., 1, 53–67.Google Scholar
[93] 1995. Asymptotic enumeration methods. Pages 1063–1229 of: , , and (eds), Handbook of Combinatorics, Vol. 2. Elsevier.Google Scholar
[94] , and 2000. On longest increasing subsequences in random permutations. Pages 439–451 of: , , , , and (eds), Analysis, Geometry, Number Theory: The Mathematics of Leon Ehrenpreis. American Mathematical Society.Google Scholar
[95] 2000. Random matrices and random permutations. Int. Math. Res. Notices, 2000, 1043–1095.CrossRefGoogle Scholar
[96] 2001. Hook length formula and geometric combinatorics. Sém. Lothar. Combin., 46, Article B46f.Google Scholar
[97] 2009. Universality results for the largest eigenvalues of some sample covariance matrix ensembles. Probab. Theory Related Fields, 143, 481–516.CrossRefGoogle Scholar
[98] , and 2005. An arctic circle theorem for Groves. J. Combin. Theory Ser. A, 111, 137–164.CrossRefGoogle Scholar
[99] , and Universality of covariance matrices. Preprint, arXiv:1110.2501, 2011.
[100] , and Limit shapes for random square Young tableaux and plane partitions. Preprint, arXiv:math/0405190v1, 2004.
[101] , and 2007. Limit shapes for random square Young tableaux. Adv. Appl. Math, 38, 164–209.CrossRefGoogle Scholar
[102] , and 2004. Exact scaling functions for one-dimensional stationary KPZ growth. J. Stat. Phys., 115, 255–279. Numerical tables available at http://www-m5.ma.tum.de/KPZ.CrossRefGoogle Scholar
[103] 2005. Note on the expected number of Yang-Baxter moves applicable to reduced decompositions. Eur. J. Combin., 26, 1019–1021.CrossRefGoogle Scholar
[104] 1938. On the representations of the symmetric group. Amer. J. Math., 60, 745–760.Google Scholar
[106] 2000. Stirling's approximation for n!: the ultimate short proof?Amer. Math. Monthly, 107, 556–557.CrossRefGoogle Scholar
[107] 2005. The number of steps in the Robinson-Schensted algorithm. Funct. Anal. Appl., 39, 152–155.CrossRefGoogle Scholar
[108] 2006. Permutations with short monotone subsequences. Adv. Appl. Math., 37, 501–510.CrossRefGoogle Scholar
[109] 2012. Arctic circles, domino tilings and square Young tableaux. Ann. Probab., 40, 611–647.CrossRefGoogle Scholar
[110] 1981. Nonequilibrium behaviour of a many particle process: density profile and local equilibria. Z. Wahrsch. Verw. Gebiete, 58, 41–53.CrossRefGoogle Scholar
[112] 2001. The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions. Springer.CrossRefGoogle Scholar
[113] 1961. Longest increasing and decreasing subsequences. Canad. J. Math., 13, 179–191.CrossRefGoogle Scholar
[114] 1963. Quelques remarques sur une construction de Schensted. Math. Scand., 12, 117–128.CrossRefGoogle Scholar
[115] Lecture notes on the corner growth model. Unpublished notes (2009), available at http://www.math.wisc.edu/~seppalai/cornergrowth-book/ajo.pdf.
[116] 1996. A microscopic model for the Burgers equation and longest increasing subsequences. Electron. J. Probab., 1-5, 1–51.Google Scholar
[117] 1998a. Hydrodynamic scaling, convex duality and asymptotic shapes of growth models. Markov Process. Related Fields, 4, 1–26.Google Scholar
[118] 1998b. Large deviations for increasing sequences on the plane. Probab. Theory Related Fields, 112, 221–244.Google Scholar
[119] 1977. Notes on infinite determinants of Hilbert space operators. Adv. Math., 24, 244–273.Google Scholar
[120] 2005. Trace Ideals and Their Applications. 2nd edition. American Mathematical Society.Google Scholar
[121] 2000. Determinantal random point fields. Russian Math. Surveys, 55, 923–975.CrossRefGoogle Scholar
[122] 2002. A note on universality of the distribution of the largest eigenvalues in certain sample covariance matrices. J. Stat. Phys., 108, 1033–1056.CrossRefGoogle Scholar
[124] 1984. On the number of reduced decompositions of elements of Coxeter groups. Eur. J. Combin., 5, 359–372.CrossRefGoogle Scholar
[126] 2007. Increasing and decreasing subsequences and their variants. Pages 545–579 of: , , , and (eds), Proceedings of the International Congress of Mathematicians, Madrid 2006. American Mathematical Society.
[127] 2011. Enumerative Combinatorics, Vol. 1. 2nd edition. Cambridge University Press.CrossRefGoogle Scholar
[128] 1986. An Efron-Stein inequality for nonsymmetric statistics. Ann. Stat., 14, 753–758.Google Scholar
[129] 1995. Variations on the monotone subsequence theme of Erdős and Szekeres. Pages 111–131 of: , , , and (eds), Discrete Probability and Algorithms. Springer.Google Scholar
[130] , and 1977. On some problems of statistical theory of partitions. I. Acta Math. Acad. Sci. Hungr., 29, 361–379.Google Scholar
[132] 1995. Concentration of measure and isoperimetric inequalities in product spaces. Publ. Math. Inst. Hautes Etud. Sci., 81, 73–205.Google Scholar
[133] 1952. Statistical mechanics and the partition of numbers. The form of the crystal surfaces. Proc. Camb. Philos. Soc., 48, 683–697.CrossRefGoogle Scholar
[135] 1948. Introduction to the Theory of Fourier Integrals. 2nd edition. Clarendon Press.Google Scholar
[136] , and 1994. Level-spacing distributions and the Airy kernel. Commun. Math. Phys., 159, 151–174.CrossRefGoogle Scholar
[137] , and 2009. Asymptotics in ASEP with step initial condition. Commun. Math. Physics, 290, 129–154.CrossRefGoogle Scholar
[138] 1961. Monte Carlo calculations in problems of mathematical physics. Pages 261–281 of: (ed), Modern Mathematics For the Engineer, Second Series. McGraw-Hill.Google Scholar
[140] , and 2009. Numerical experiments in problems of asymptotic representation theory. Zap. Nauchn. Sem., 373, 77–93. Translated in J. Math. Sci., 168:351–361, 2010.Google Scholar
[141] 1996. Statistical mechanics of combinatorial partitions and their limit shapes. Funct. Anal. Appl., 30, 90–105.CrossRefGoogle Scholar
[142] , and 1977. Asymptotics of the Plancherel measure of the symmetric group and the limiting shape of Young tableaux. Soviet Math. Dokl., 18, 527–531.Google Scholar
[143] , and 1985. The asymptotics of maximal and typical dimensions irreducible representations of the symmetric group. Funct. Anal. Appl., 19, 21–31.CrossRefGoogle Scholar
[144] 2012. Random covariance matrices: universality of local statistics of eigenvalues up to the edge. Random Matrices: Theory Appl., 1, 1150005.CrossRefGoogle Scholar
[145] 1995. A Treatise on the Theory of Bessel Functions. 2nd edition. Cambridge University Press.Google Scholar
[146] 1960. The unreasonable effectiveness of mathematics in the natural sciences. Comm. Pure Appl. Math., 13, 1–14.Google Scholar
[147] 1928. The generalised product moment distribution in samples from a normal multivariate population. Biometrika, 20A, 32–53.CrossRefGoogle Scholar