Reduction of Rota's basis conjecture to a problem on three bases
Abstract
Description
Rota's basis conjecture, open since 1989, states that if B_1, B_2, ..., B_n are n bases of a vector space of rank n, then there is an nxn grid of vectors such that the vectors in the ith row are precisely the elements of B_i and such that every column is also a basis. It is shown that Rota's basis conjecture follows from a similar conjecture that involves only three bases instead of n bases: If M is a matroid of rank n that is a disjoint union of 3 bases, and I_1, ..., I_n are disjoint independent sets with |I_i| <= 3, then there exists an nx3 grid G that contains each element of M exactly once, with the elements of I_i appearing in row i, such that the three columns of G are bases of M.
Accepted version, SIAM J. Discrete Math.; minor errors in previous version corrected
Accepted version, SIAM J. Discrete Math.; minor errors in previous version corrected