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