Algebraic Combinatorics Seminar



"Polyhedral Techniques in Computational Representation Theory"

Tyrrell McAllister
University of California, Davis

Monday, April 24, 2006
4:00 pm, 243 White Classroom Building


Techniques from polyhedral geometry have long provided insights into the representation theory of Lie algebras. Recent results include the encoding of tensor product multiplicities as the number of integer lattice points in special families of polyhedra. These results have theoretical implications as well as concrete computational applications. We discuss the following results and their applications to theoretical computer science.

In 1999, Knutson and Tao proved the saturation theorem, which states that, given dominant weights l, m, and n for sl_r(C), the Littlewood--Richardson coefficient c_{l,m}^n is nonzero if and only if c_{Nl, Nm}^{Nn} is nonzero for some positive integer N. In one of their proofs of this result, Knutson and Tao use the encoding of Littlewood--Richardson coefficients as the number of integer lattice points in so-called hive polytopes. In this setting, the saturation theorem becomes the statement that every nonempty hive polytope contains an integer lattice point. A similar result holds for Kostka coefficients K_{l,m}, which had been shown in 1950 to be represented by the lattice points in so-called Gelfand--Tsetlin polytopes.

In 2004, King, Tollu, and Toumazet conjectured a generalization of these results to so-called stretched Littlewood--Richardson and Kostka coefficients. From the polyhedral interpretation of these numbers, it follows that c_{Nl, Nm}^{Nn} and K_{Nl, Nm} are quasi-polynomials in N. Abundant computational evidence supports the conjecture that these quasi-polynomials have positive coefficients, a result which would imply the saturation theorem in type A. Moreover, this positivity conjecture appears to apply to all of the classical root systems (unlike the original saturation theorem).

We present the polyhedral algorithms that provide the evidence for these conjectures, and we present a combinatorial structure on the points in Gelfand--Tsetlin polytopes that yields new results about the behavior of the functions c_{Nl, Nm}^{Nn} and K_{Nl, Nm} and the combinatorics of the associated polytopes. In particular, we compute the degrees of the polynomials K_{Nl, Nm}, and we study their factorizations, making advances towards proving the general positivity conjecture.