In the summer of 2012 Minah
Oh and I ran an REU
worked on a problem in combinatorial linear algebra known as Rota's
The students we worked with were: Stephanie Bittner (Virginia
Wesleyan College), Michael Cheung (Elizabethtown College), Xuyi Guo
(Stanford University), and Adam Zweber (Carleton College).
Everyone worked extremely hard and after eight weeks we were
to come up with some nice results.
Left to right: Minah, Adam, Stephanie, Mike, Xuyi, Josh
Before describing the
students' work, here is one statement of
Rota's Basis Conjecture. Suppose you are given n bases of an
n-dimensional vector space. Additionally suppose that each
is assigned a particular color: say the first basis is red,
second blue, etc. Then Rota's Basis Conjecture asserts that
can always repartition the multiset union of these bases into n
"rainbow" bases--that is, each new basis will contain exactly one
vector of each color. This innocent-looking conjecture has
open for over twenty years.
Both mathematics REU groups out for lunch (the other group was
supervised by Brant Jones
and Edwin O'Shea).
Adam, Stephanie, and Xuyi
defined and studied the "incidence
matrix of disjoint transversals." Specifically, suppose you
given n disjoint sets each of size n. Form a matrix with rows
columns indexed by the collection of transversals of these n sets.
Put a one in the (i,j)-entry if transversal i is disjoint
transversal j, otherwise put a zero. Aside from being an
interesting combinatorial object in its own right, this zero-one matrix
is very closely related to the n-dimensional case of Rota's Basis
Conjecture. The students managed to understand and
several numerical invariants of this matrix, in particular its
eigenvalues and Smith normal form. See their full report here. [Update: see our final paper.]
Mike took a different approach to the problem, and spent most of the
summer working on a computer program that can prove Rota's Basis
Conjecture for any dimension. Actually, Rota's Basis
can be generalized to an analagous statement about n bases in a rank n
matroid, and Mike works in this full generality. The
Rota's Basis Conjecture was previously known to be true only for the
case n=3, and this summer Mike managed to prove the case n=4.
his full report here.
The students presented their work to the Department of Mathematics and
Statistics at JMU, see the videos/slides below:
Part 1 - Stephanie
Part 2 - Mike
Part 3 - Questions
Part 4 - Adam and Xuyi
Back to my homepage