Algebraic Combinatorics Seminar
####
**
UNIVERSITY OF KENTUCKY **

ALGEBRAIC COMBINATORICS SEMINAR

845 PATTERSON OFFICE TOWER

SPRING 2006

####

###
COLLOQUIUM
###

##
"Polyhedral Techniques in Computational Representation Theory"

Tyrrell McAllister

University of California, Davis

###
Monday, April 24, 2006

4:00 pm, 243 White Classroom Building

####
Abstract:

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.