Pokrovskiy’s startling morning rainbow
Rota’s Basis Conjecture holds asymptotically, by Alexey Pokrovskiy
Abstract: Rota’s Basis Conjecture is a well known problem from matroid theory, that states that for any collection of n bases in a rank n matroid, it is possible to decompose all the elements into n disjoint rainbow bases. Here an asymptotic version of this is proved. We show that it is possible to find n − o(n) disjoint rainbow independent sets of size n − o(n).
A rainbow basis is a basis with one element from each collection.
(I thank Nati Linial for telling me about it.)
Another way to formulate Rota’s basis conjecture (for representable matroids) is that if B1, B2, …, Bn are n bases of an n-dimensional vector space V (not necessarily distinct or disjoint), then there exists an n × n grid of vectors (vij) such that
1. the n vectors in row i are the members of the ith basis Bi (in some order), and
2. in each column of the matrix, the n vectors in that column form a basis of V.
If all the bases are the standard basis then this reduces to the existence of Latin squares.
Unrelated trivia question: AGC-GTC-TGC-GTC-TGC-GAC-GATC-? what comes next in the sequence?
We mentioned Rota’s basis conjecture in various earlier posts. A classic paper on the subject is the 1989 paper by Rosa Huang and Gian Carlo-Rota. Three and a half years ago Timothy Chow lunched a polymath project (Polymath 12) to solve it. (Here is my post on the project with various variants of the conjecture, the first post on the polymath blog, and the wiki). See this post for several famous conjectures by Rota, and this post about the related Alon-Tarsi conjecture.