## Recent progress in algebraic combinatorics

HTML articles powered by AMS MathViewer

- by Richard P. Stanley PDF
- Bull. Amer. Math. Soc.
**40**(2003), 55-68 Request permission

## Abstract:

We survey three recent breakthroughs in algebraic combinatorics. The first is the proof by Knutson and Tao, and later Derksen and Weyman, of the saturation conjecture for Littlewood-Richardson coefficients. The second is the proof of the $n!$ and $(n+1)^{n-1}$ conjectures by Haiman. The final breakthrough is the determination by Baik, Deift, and Johansson of the limiting behavior of the length of the longest increasing subsequence of a random permutation.## References

- Jinho Baik, Percy Deift, and Kurt Johansson,
*On the distribution of the length of the longest increasing subsequence of random permutations*, J. Amer. Math. Soc.**12**(1999), no. 4, 1119–1178. MR**1682248**, DOI 10.1090/S0894-0347-99-00307-0 - A. D. Berenstein and A. V. Zelevinsky,
*Triple multiplicities for $\textrm {sl}(r+1)$ and the spectrum of the exterior algebra of the adjoint representation*, J. Algebraic Combin.**1**(1992), no. 1, 7–22. MR**1162639**, DOI 10.1023/A:1022429213282 - François Bergeron, Adriano Garsia, and Glenn Tesler,
*Multiple left regular representations generated by alternants*, J. Combin. Theory Ser. A**91**(2000), no. 1-2, 49–83. In memory of Gian-Carlo Rota. MR**1779775**, DOI 10.1006/jcta.2000.3089 - Alexei Borodin, Andrei Okounkov, and Grigori Olshanski,
*Asymptotics of Plancherel measures for symmetric groups*, J. Amer. Math. Soc.**13**(2000), no. 3, 481–515. MR**1758751**, DOI 10.1090/S0894-0347-00-00337-4 - Anders Skovsted Buch,
*The saturation conjecture (after A. Knutson and T. Tao)*, Enseign. Math. (2)**46**(2000), no. 1-2, 43–60. With an appendix by William Fulton. MR**1769536** - Percy Deift,
*Integrable systems and combinatorial theory*, Notices Amer. Math. Soc.**47**(2000), no. 6, 631–640. MR**1764262** - Harm Derksen and Jerzy Weyman,
*Semi-invariants of quivers and saturation for Littlewood-Richardson coefficients*, J. Amer. Math. Soc.**13**(2000), no. 3, 467–479. MR**1758750**, DOI 10.1090/S0894-0347-00-00331-3 - William Fulton,
*Young tableaux*, London Mathematical Society Student Texts, vol. 35, Cambridge University Press, Cambridge, 1997. With applications to representation theory and geometry. MR**1464693** - William Fulton,
*Eigenvalues, invariant factors, highest weights, and Schubert calculus*, Bull. Amer. Math. Soc. (N.S.)**37**(2000), no. 3, 209–249. MR**1754641**, DOI 10.1090/S0273-0979-00-00865-X
g-hag A. M. Garsia and J. Haglund, A proof of the $q,t$-Catalan positivity conjecture, - A. M. Garsia and M. Haiman,
*A remarkable $q,t$-Catalan sequence and $q$-Lagrange inversion*, J. Algebraic Combin.**5**(1996), no. 3, 191–244. MR**1394305**, DOI 10.1023/A:1022476211638 - Adriano M. Garsia and Mark Haiman,
*A graded representation model for Macdonald’s polynomials*, Proc. Nat. Acad. Sci. U.S.A.**90**(1993), no. 8, 3607–3610. MR**1214091**, DOI 10.1073/pnas.90.8.3607 - A. M. Garsia and M. Haiman,
*Some natural bigraded $S_n$-modules and $q,t$-Kostka coefficients*, Electron. J. Combin.**3**(1996), no. 2, Research Paper 24, approx. 60. The Foata Festschrift. MR**1392509**, DOI 10.37236/1282 - Ira M. Gessel,
*Symmetric functions and P-recursiveness*, J. Combin. Theory Ser. A**53**(1990), no. 2, 257–285. MR**1041448**, DOI 10.1016/0097-3165(90)90060-A - Curtis Greene,
*An extension of Schensted’s theorem*, Advances in Math.**14**(1974), 254–265. MR**354395**, DOI 10.1016/0001-8708(74)90031-0
hag J. Haglund, Conjectured statistics for the $q,t$-Catalan numbers, - Mark Haiman,
*Macdonald polynomials and geometry*, New perspectives in algebraic combinatorics (Berkeley, CA, 1996–97) Math. Sci. Res. Inst. Publ., vol. 38, Cambridge Univ. Press, Cambridge, 1999, pp. 207–254. MR**1731818** - Mark Haiman,
*Hilbert schemes, polygraphs and the Macdonald positivity conjecture*, J. Amer. Math. Soc.**14**(2001), no. 4, 941–1006. MR**1839919**, DOI 10.1090/S0894-0347-01-00373-3
hai:npo M. Haiman, Vanishing theorems and character formulas for the Hilbert scheme of points in the plane, preliminary draft, www/math.berkeley.edu/$\sim$mhaiman; abbreviated version in - 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** - G. J. Heckman,
*Projections of orbits and asymptotic behavior of multiplicities for compact connected Lie groups*, Invent. Math.**67**(1982), no. 2, 333–356. MR**665160**, DOI 10.1007/BF01393821 - Kurt Johansson,
*Discrete orthogonal polynomial ensembles and the Plancherel measure*, Ann. of Math. (2)**153**(2001), no. 1, 259–296. MR**1826414**, DOI 10.2307/2661375 - Alexander A. Klyachko,
*Stable bundles, representation theory and Hermitian operators*, Selecta Math. (N.S.)**4**(1998), no. 3, 419–445. MR**1654578**, DOI 10.1007/s000290050037 - Donald E. Knuth,
*The art of computer programming. Volume 3*, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. Sorting and searching. MR**0445948** - Allen Knutson and Terence Tao,
*The honeycomb model of $\textrm {GL}_n(\textbf {C})$ tensor products. I. Proof of the saturation conjecture*, J. Amer. Math. Soc.**12**(1999), no. 4, 1055–1090. MR**1671451**, DOI 10.1090/S0894-0347-99-00299-4 - Allen Knutson and Terence Tao,
*Honeycombs and sums of Hermitian matrices*, Notices Amer. Math. Soc.**48**(2001), no. 2, 175–186. MR**1811121** - 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
macdsf I. G. Macdonald, A new class of symmetric functions, - I. G. Macdonald,
*Symmetric functions and Hall polynomials*, 2nd ed., Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1995. With contributions by A. Zelevinsky; Oxford Science Publications. MR**1354144** - F. Miller Maley,
*The Hall polynomial revisited*, J. Algebra**184**(1996), no. 2, 363–371. MR**1409218**, DOI 10.1006/jabr.1996.0264 - Andrei Okounkov,
*Random matrices and random permutations*, Internat. Math. Res. Notices**20**(2000), 1043–1095. MR**1802530**, DOI 10.1155/S1073792800000532 - Doron Rotem,
*On a correspondence between binary trees and a certain type of permutation*, Information Processing Lett.**4**(1975/76), no. 3, 58–61. MR**388841**, DOI 10.1016/0020-0190(75)90002-2 - C. Schensted,
*Longest increasing and decreasing subsequences*, Canadian J. Math.**13**(1961), 179–191. MR**121305**, DOI 10.4153/CJM-1961-015-3 - Larry Smith,
*Polynomial invariants of finite groups*, Research Notes in Mathematics, vol. 6, A K Peters, Ltd., Wellesley, MA, 1995. MR**1328644**, DOI 10.1201/9781439864470 - Richard P. Stanley,
*Invariants of finite groups and their applications to combinatorics*, Bull. Amer. Math. Soc. (N.S.)**1**(1979), no. 3, 475–511. MR**526968**, DOI 10.1090/S0273-0979-1979-14597-X - Richard P. Stanley,
*Enumerative combinatorics. Vol. 2*, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. MR**1676282**, DOI 10.1017/CBO9780511609589
tesler G. Tesler, Semi-primary lattices and tableaux algorithms, Ph.D. thesis, M.I.T., 1995.
- Craig A. Tracy and Harold Widom,
*Level-spacing distributions and the Airy kernel*, Comm. Math. Phys.**159**(1994), no. 1, 151–174. MR**1257246**, DOI 10.1007/BF02100489 - 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** - Andrei Zelevinsky,
*Littlewood-Richardson semigroups*, New perspectives in algebraic combinatorics (Berkeley, CA, 1996–97) Math. Sci. Res. Inst. Publ., vol. 38, Cambridge Univ. Press, Cambridge, 1999, pp. 337–345. MR**1731821**

*Discrete Math.*, to appear, www.math.upenn.edu/$\sim$jhaglund.

*Advances in Math.*, to appear, www.math.upenn.edu/$\sim$jhaglund.

*Physics and Combinatorics*(A. N. Kirillov and N. Liskova, eds.), World Scientific, London, 2001, pp. 1–21. hall P. Hall, The algebra of partitions, in

*Proc. 4th Canadian Math. Congress (Banff)*, 1959, pp. 147–159.

*Actes 20$^\mathrm {e}$ Séminaire Lotharingien*, Publ. I.R.M.A., Strasbourg, 1992, pp. 5–39.

## Additional Information

**Richard P. Stanley**- Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
- MR Author ID: 166285
- Email: rstan@math.mit.edu
- Received by editor(s): October 23, 2000
- Received by editor(s) in revised form: January 4, 2002
- Published electronically: October 11, 2002
- Additional Notes: Partially supported by NSF grant #DMS-9988459
- © Copyright 2002 American Mathematical Society
- Journal: Bull. Amer. Math. Soc.
**40**(2003), 55-68 - MSC (2000): Primary 05E99; Secondary 05E05, 14C05, 15A18, 60C05
- DOI: https://doi.org/10.1090/S0273-0979-02-00966-7
- MathSciNet review: 1943133