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

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 )$.