Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269 - Combinatorics

Allen Knutson

UCSD

Shifting, matroids, and Littlewood-Richardson

Abstract:

To prove the Erd\H os-Ko-Rado theorem about extremal collections of subsets of $1,\ldots,n$, they invented the {\em shifting} technique, which preserves the number of subsets in a collection but simplifies (in some senses) the collection. After a finite number of shifts, one's collection becomes invariant under shifting, and easily studied. Given a finite set of $n$ vectors in a $k$-dimensional vector space, the collection of subsets that form bases of the vector space satisfies some combinatorial properties. Abstracting them, Whitney defined {\em matroids}. The matroids that are invariant under shifting have been classified, and correspond to partitions inside a $k \times (n-k)$ rectangle. The shift of a matroid usually is not a matroid. I'll present a new version of the Littlewood-Richardson rule, that starts with a certain matroid, and alternately shifts it (breaking matroidness) and decomposes as a union of maximal submatroids. The leaves of the tree so constructed are labeled with fully shifted matroids, hence partitions. To actually carry out such a calculation in practice requires some new algorithms. Unlike all other known Littlewood-Richardson rules, this matroid shifting rule has an easy generalization to multiplication of Schubert (not just Schur) polynomials, where it is still a conjecture. This work is joint with Ravi Vakil.

March 13, 2007

4:00 PM

AP&M 7141

****************************