The honeycomb model of $GL_n(\mathbb C)$ tensor products I: Proof of the saturation conjecture

Authors:
Allen Knutson and Terence Tao

Journal:
J. Amer. Math. Soc. **12** (1999), 1055-1090

MSC (1991):
Primary 05E15, 22E46; Secondary 15A42

DOI:
https://doi.org/10.1090/S0894-0347-99-00299-4

Published electronically:
April 13, 1999

Part II:
J. Amer. Math. Soc. (2004), 19-48

MathSciNet review:
1671451

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Recently Klyachko has given linear inequalities on triples $(\lambda ,\mu ,\nu )$ of dominant weights of $GL_n(\mathbb {C})$ necessary for the corresponding Littlewood-Richardson coefficient $\dim (V_\lambda \otimes V_\mu \otimes V_\nu )^{GL_n(\mathbb {C})}$ to be positive. We show that these conditions are also sufficient, which was known as the saturation conjecture. In particular this proves Horn’s conjecture from 1962, giving a recursive system of inequalities. Our principal tool is a new model of the Berenstein-Zelevinsky cone for computing Littlewood-Richardson coefficients, the *honeycomb* model. The saturation conjecture is a corollary of our main result, which is the existence of a particularly well-behaved honeycomb associated to regular triples $(\lambda ,\mu ,\nu )$.

- A. Buch, The saturation conjecture (after A. Knutson and T. Tao), notes from a talk at Berkeley, September 1998.
- Louis J. Billera and Bernd Sturmfels,
*Fiber polytopes*, Ann. of Math. (2)**135**(1992), no. 3, 527–549. MR**1166643**, DOI https://doi.org/10.2307/2946575 - A. D. Berenstein and A. V. Zelevinsky,
*Triple multiplicities for ${\rm 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 https://doi.org/10.1023/A%3A1022429213282 - A. G. Èlashvili,
*Invariant algebras*, Lie groups, their discrete subgroups, and invariant theory, Adv. Soviet Math., vol. 8, Amer. Math. Soc., Providence, RI, 1992, pp. 57–64. MR**1155664** - W. Fulton, Eigenvalues of sums of Hermitian matrices (after A. Klyachko), Séminaire Bourbaki (1998).
- William Fulton and Joe Harris,
*Representation theory*, Graduate Texts in Mathematics, vol. 129, Springer-Verlag, New York, 1991. A first course; Readings in Mathematics. MR**1153249** - O. Gleizer, A. Postnikov, Littlewood-Richardson coefficients via Yang-Baxter equation, in preparation.
- V. Guillemin, C. Zara, Equivariant de Rham theory and graphs, arXiv:math.DG/9808135.
- Alfred Horn,
*Eigenvalues of sums of Hermitian matrices*, Pacific J. Math.**12**(1962), 225–241. MR**140521** - A. Knutson, T. Tao, C. Woodward, The honeycomb model of $\mathrm {GL}_n$ tensor products II: Facets of the L-R cone, in preparation.
- M. M. Kapranov, B. Sturmfels, and A. V. Zelevinsky,
*Quotients of toric varieties*, Math. Ann.**290**(1991), no. 4, 643–655. MR**1119943**, DOI https://doi.org/10.1007/BF01459264 - A.A. Klyachko, Stable vector bundles and Hermitian operators,
*IGM, University of Marne-la-Vallee preprint*(1994). - Shrawan Kumar,
*Proof of the Parthasarathy-Ranga Rao-Varadarajan conjecture*, Invent. Math.**93**(1988), no. 1, 117–130. MR**943925**, DOI https://doi.org/10.1007/BF01393689 - Greg Kuperberg,
*Spiders for rank $2$ Lie algebras*, Comm. Math. Phys.**180**(1996), no. 1, 109–151. MR**1403861** - D. Mumford, J. Fogarty, and F. Kirwan,
*Geometric invariant theory*, 3rd ed., Ergebnisse der Mathematik und ihrer Grenzgebiete (2) [Results in Mathematics and Related Areas (2)], vol. 34, Springer-Verlag, Berlin, 1994. MR**1304906** - A. Zelevinsky, Littlewood-Richardson semigroups, arXiv:math.CO/9704228.
- Günter M. Ziegler,
*Lectures on polytopes*, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995. MR**1311028**

Retrieve articles in *Journal of the American Mathematical Society*
with MSC (1991):
05E15,
22E46,
15A42

Retrieve articles in all journals with MSC (1991): 05E15, 22E46, 15A42

Additional Information

**Allen Knutson**

Affiliation:
Department of Mathematics, Brandeis University, Waltham, Massachusetts 02254

Address at time of publication:
Department of Mathematics, University of California Berkeley, Berkeley, California 94720-3840

Email:
allenk@alumni.caltech.edu

**Terence Tao**

Affiliation:
Department of Mathematics, University of California Los Angeles, Los Angeles, California 90095-1555

MR Author ID:
361755

ORCID:
0000-0002-0140-7641

Email:
tao@math.ucla.edu

Keywords:
Honeycombs,
Littlewood-Richardson coefficients,
Berenstein-Zelevinsky patterns,
Horn’s conjecture,
saturation,
Klyachko inequalities

Received by editor(s):
July 31, 1998

Received by editor(s) in revised form:
February 25, 1999

Published electronically:
April 13, 1999

Additional Notes:
The first author was supported by an NSF Postdoctoral Fellowship.

The second author was partially supported by NSF grant DMS-9706764.

Article copyright:
© Copyright 1999
American Mathematical Society