printable pdf
比利时vs摩洛哥足彩 ,
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

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