Limit shapes for random square Young tableaux. (English) Zbl 1122.60009
Summary: Our main result is a limit shape theorem for the two-dimensional surface defined by a uniform random \(n\times \)n square Young tableau. The analysis leads to a calculus of variations minimization problem that resembles the minimization problems studied by B. F. Logan and L. A. Shepp [Adv. Math. 26, 206–222 (1977; Zbl 0363.62068)], A. M. Vershik and S. V. Kerov [Sov. Math., Dokl. 18, 527–531 (1977); translation from Dokl. Akad. Nauk SSSR 233, 1024–1027 (1977; Zbl 0406.05008)], and H. Cohn, M. Larsen and J. Propp [New York J. Math. 4, 137–165, electronic only (1998; Zbl 0908.60083)]. We solve this problem by developing a general technique for solving variational problems of this kind. An extension to rectangular Young tableaux is also given. We also apply the main result to show that the location of a particular entry in the tableau is in the limit governed by a semicircle distribution, and to the study of extremal Erdős-Szekeres permutations, namely, permutations of the numbers \(1,2,\dots ,n^{2}\) whose longest monotone subsequence is of length \(n\).
MSC:
| 60C05 | Combinatorial probability |
| 05E10 | Combinatorial aspects of representation theory |
| 60F10 | Large deviations |
References:
| [1] | Aldous, D.; Diaconis, P., Longest increasing subsequences: From patience sorting to the Baik-Deift-Johansson theorem, Bull. Amer. Math. Soc., 36, 413-432 (1999) · Zbl 0937.60001 |
| [2] | Apostol, T. M., Introduction to Analytic Number Theory (1976), Springer · Zbl 0335.10001 |
| [3] | Baik, J.; Deift, P.; Johansson, K., On the distribution of the length of the longest increasing subsequence of random permutations, J. Amer. Math. Soc., 12, 1119-1178 (1999) · Zbl 0932.05001 |
| [4] | Baik, J.; Deift, P.; Johansson, K., On the distribution of the length of the second row of a Young diagram under Plancherel measure, Geom. Funct. Anal., 10, 1606-1607 (2000) · Zbl 0971.05110 |
| [5] | Borodin, A.; Okounkov, A.; Olshanski, G., Asymptotics of Plancherel measures for symmetric groups, J. Amer. Math. Soc., 13, 481-515 (2000) · Zbl 0938.05061 |
| [6] | Cohn, H.; Larsen, M.; Propp, J., The shape of a typical boxed plane partition, New York J. Math., 4, 137-165 (1998) · Zbl 0908.60083 |
| [7] | Estrada, R.; Kanwal, R. P., Singular Integral Equations (2000), Birkhäuser · Zbl 0575.45008 |
| [8] | Frame, J. S.; de B. Robinson, G.; Thrall, R. M., The hook graphs of the symmetric groups, Canad. J. Math., 6, 316-324 (1954) · Zbl 0055.25404 |
| [9] | Greene, C.; Nijenhuis, A.; Wilf, H., A probabilistic proof of a formula for the number of Young tableaux of a given shape, Adv. Math., 31, 104-109 (1979) · Zbl 0398.05008 |
| [10] | Hardy, G. H.; Littlewood, J. E.; Pólya, G., Inequalities (1952), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0047.05302 |
| [11] | Ivanov, V.; Olshanski, G., Kerov’s central limit theorem for the Plancherel measure on Young diagrams, (Fomin, S., Symmetric Functions 2001: Surveys of Developments and Perspectives. Symmetric Functions 2001: Surveys of Developments and Perspectives, Proc. NATO Advanced Study Institute (2002), Kluwer) · Zbl 1016.05073 |
| [12] | Johansson, K., Discrete orthogonal polynomial ensembles and the Plancherel measure, Ann. of Math., 153, 259-296 (2001) · Zbl 0984.15020 |
| [13] | Knuth, D. E., The Art of Computer Programming, vol. 3: Sorting and Searching (1998), Addison-Wesley · Zbl 0895.65001 |
| [14] | Logan, B. F.; Shepp, L. A., A variational problem for random Young tableaux, Adv. Math., 26, 206-222 (1977) · Zbl 0363.62068 |
| [15] | Porter, D.; Stirling, D. S.G., Integral Equations (1990), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0908.45001 |
| [16] | Romik, D., Explicit formulas for hook walks on continual Young diagrams, Adv. in Appl. Math., 32, 625-654 (2004) · Zbl 1051.05080 |
| [17] | Schensted, C., Longest increasing and decreasing subsequences, Canad. J. Math., 13, 179-191 (1961) · Zbl 0097.25202 |
| [18] | Titchmarsh, E. C., Introduction to the Theory of Fourier Integrals (1937), Oxford Univ. Press: Oxford Univ. Press Oxford · Zbl 0017.40404 |
| [19] | Vershik, A. M.; Kerov, S. V., Asymptotics of the Plancherel measure of the symmetric group and the limiting shape of Young tableaux, Soviet Math. Dokl., 18, 527-531 (1977) · Zbl 0406.05008 |
| [20] | Vershik, A. M.; Kerov, S. V., The asymptotics of maximal and typical dimensions of irreducible representations of the symmetric group, Funct. Anal. Appl., 19, 21-31 (1985) · Zbl 0592.20015 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
