The honeycomb model of GL(n) 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. We give a complete determination of its facets, finishing a long story with recent highlights by [Helmke-Rosenthal, Klyachko, Belkale]. We introduce_puzzles_, which are new combinatorial gadgets to compute Grassmannian Schubert calculus, and will probably be the main point of interest for many readers. As the proofs 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 in [H,Kly,HR,Be]. 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,C) the irreducible representation V_\nu appears exactly once in V_\lambda tensor V_\mu, then for all N\in \naturals, V_{N\lambda} appears exactly once in V_{N\lambda} tensor V_{N\mu}.''