The honeycomb model of $GL_n({\mathbb C})$ tensor products II: Puzzles determine facets of the Littlewood-Richardson cone

The set of possible spectra $(\lambda ,\mu ,\nu )$ of zero-sum triples of Hermitian matrices forms a polyhedral cone, whose facets have been already studied by Knutson and Tao, Helmke and Rosenthal, Totaro, and Belkale in terms of Schubert calculus on Grassmannians. We give a complete determination of these facets; there is one for each triple of Grassmannian Schubert cycles intersecting in a unique point. In particular, the list of inequalities determined by Belkale to be sufficient is in fact minimal. We introduce puzzles, which are new combinatorial gadgets to compute Grassmannian Schubert calculus, and seem to have much interest in their own right. As the proofs herein indicate, the Hermitian sum problem is very naturally studied using puzzles directly, and their connection to Schubert calculus is quite incidental to our approach. In particular, we get new, puzzle-theoretic, proofs of the results of Horn, Klyachko, Helmke and Rosenthal, Totaro, and Belkale. Along the way we give a characterization of “rigid” puzzles, which we use to prove a conjecture of W. Fulton: “if for a triple of dominant weights $\lambda ,\mu ,\nu$ of $GL_n({\mathbb C})$ the irreducible representation $V_\nu$ appears exactly once in $V_\lambda \otimes V_\mu$, then for all $N\in {\mathbb N}$, $V_{N\lambda }$ appears exactly once in $V_{N\lambda }\otimes V_{N\mu }$.”