Applications of polyhedral geometry to computational representation theory.

摘要

We investigate the consequences of applying the theoretical and algorithmic tools of polyhedral geometry to computational representation theory. The central problem motivating our study is that of computing tensor product multiplicities, also known as Clebsch-Gordan coefficients, for finite-dimensional complex semisimple Lie algebras.;We show that, when the rank of the Lie algebra is fixed, there is a polynomial time algorithm for computing Clebsch-Gordan (CB) coefficients. Moreover, we show that, for type-A Lie algebras, there is an algorithm to decide when the coefficients are nonzero in polynomial time for arbitrary rank. Both algorithms depend upon the encoding due to Berenstein and Zelevinsky (2001) of CB-coefficients as the number of lattice points in polytopes. Using this algorithm, we provide experimental evidence for two conjectured generalizations of the saturation theorem of Knutson and Tao (1999), one of which applies to all of the classical root systems.;In pursuit of a proof of these conjectures, we study stretched CB-coefficients in the special case of stretched Kostka coefficients for type-A Lie algebras via Gelfand-Tsetlin (GT) polytopes, which encode the weight-space multiplicities of glnC . We present a combinatorial structure on GT-patterns, which we call a tiling, that encodes both the combinatorics of the polytope and the geometry of its embedding with respect to the integer lattice.;We use tilings of GT-patterns to give a combinatorial characterization of the vertices of GT-polytopes and a method to calculate the dimension of the minimal face containing a given GT-pattern. Applying the tiling machinery, we give a negative solution to a conjecture of Berenstein and Kirillov (1995) that the vertices of GT-polytopes are integral, and we derive a bound on the denominators for the non-integral vertices when n is fixed. In addition, we study the stretched Kostka coefficient n Knlambda,nbeta. Kirillov and Reshetikhin (1986) have shown that stretched Kostka coefficients are polynomial functions of n. We prove the values conjectured by King, Tollu, and Toumazet (2005) for the degrees of these polynomials.