比利时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
****************************