This post tentatively kicks off Polymath 12 on Rota’s basis conjecture.
I proposed Rota’s basis conjecture as a possible Polymath project on MathOverflow last year. If you have not read my proposal, I strongly recommend that you read it now, because in it, I sketched some reasons why I thought this would make a good Polymath project, as well as some known partial results and potential avenues for progress.
Recently, I emailed several likely participants, and a number of them responded enthusiastically, enough in my opinion to warrant an attempt to start a Polymath project. I have discussed the possibility with the polymath blog admins and since I do not have a blog of my own, they have generously agreed to host the project here on the polymath blog itself. This means that you should comment freely in the comments section below.
Rota’s basis conjecture states 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 this project gets enough momentum to be formally declared “Polymath 12” then it will be important to give a thorough summary of what is already known, and to lay out in some detail all the promising directions. However, at this early stage, I think that it is important to have some “quick wins” to get things moving, so I would like to present a couple of new ideas that I think could lead to some new partial results quickly, and also invite others to present their own ideas.
Idea 1
The first idea is to extend an old result of Aharoni and Berger that I think has not received too much attention from others. Suppose we have two matroids on the same ground set E. By definition, a common independent set is a subset of E that is independent in both matroids. We can try to partition E into a disjoint union of common independent sets, and can ask the question, what is the smallest number β of common independent sets that we need?
Here is the relation to Rota’s basis conjecture. The ground set E has n2 elements, and one of the matroids is defined by the given set of n2 vectors (here, if the same vector appears in more than one basis, we treat the different occurrences as being distinct). The second matroid is the so-called transversal matroid whose independent sets are precisely those subsets of E that contain at most one element from each Bi. From this point of view, Rota’s basis conjecture says that β = n, i.e., that E may be partitioned into n disjoint common independent sets (each necessarily of size n).
Aharoni and Berger have proved a general theorem about matroids that implies, in the specific case of Rota’s basis conjecture, that β ≤ 2n. They also have a very general conjecture on matroids that would imply that β ≤ n + 1 for Rota’s basis conjecture.
Let me now make the simple observation that it is easy to prove directly that β ≤ 2n – 1 for Rota’s basis conjecture. We begin with a lemma. Suppose we have a matroid and suppose that I1, …, In are independent sets with |Ii| = i for all i. Call this a triangular system. Then I claim that there exists a way of choosing a vi from each Ii in such a way that J1 := {vi} is independent. The proof is easy: We start with the forced choice v1 ∈ I1, and then note that by the independent set axiom, since |I2| = 2, there must exist some v2 ∈ I2 that can be added to v1 to produce an independent set of size 2. Similarly, once v1 and v2 are chosen, it follows directly from the independent set axiom that we can add some v3 ∈ I3, and so on. This proves the lemma. Now, once J1 has been constructed, we can imagine removing the elements of J1 from the original triangular system to obtain a smaller triangular system. We can then repeat the argument on this smaller system to form an independent set J2 that contains exactly one element from each Ii for i = 2, 3, …, n. This shows that the original triangular system can be partitioned into (at most) n common independent sets (where as before, the second matroid is the natural transversal matroid).
Returning to the setup for Rota’s basis conjecture, we can write out the n2 given vectors in a grid with the elements of Bi in row i (not worrying about whether the columns are bases) and draw a diagonal to split the bases into two disjoint triangular systems, one of size n and one of size n – 1. So we can partition the vectors into at most n + (n – 1) = 2n – 1 common independent sets, Q.E.D.
So the first question, which I don’t think has been looked at much and which hopefully should not be too hard, is:
Can we show that β ≤ 2n – 2?
Idea 2
In one of my papers I introduced the idea of looking for certain kinds of obstructions to an inductive proof of the conjecture. Specifically, suppose that instead of n bases, we are given n independent sets I1, …, In, each of size k < n. Suppose further that these nk vectors (counted with multiplicity) can be partitioned into k bases somehow (but not necessarily bases that contain exactly one vector from each row). Then we can ask if there exists an n × k grid whose ith row comprises the elements of Ii and whose columns are all bases. In general, the answer will be no, but it is not so easy to come up with counterexamples. I came up with two counterexamples with k = 2, but I think it would be worth doing a computational search for more examples. Even k = 2 and n = 5 has not been checked, as far as I know. If there are not many counterexamples then there is some hope that we could classify them all, and I think that this would be a big step towards proving the full conjecture. Note: one family of counterexamples has been identified by Harvey, Kiraly, and Lau.
Idea 3
The last idea I want to present here is very vague. It is inspired by a paper by Ellenberg and Erman that I recently learned about. The result of the paper itself isn’t relevant, but I thought that the method might be. Roughly speaking, they reduce a certain combinatorial problem involving points and lines in a vector space to a “degenerate” case that is more tractable. Since various “degenerate” cases of Rota’s basis conjecture are known, perhaps the same idea could be applied to extend those degenerate cases to more cases.
As an example of a known degenerate case, let us first generalize Rota’s basis conjecture slightly as follows. Let us allow the vector space V to have some dimension d > n, and instead of n bases, let us take any n independent sets I1, …, In, each of size n. Then we ask for the usual n × n grid except now we only require the columns to be independent and not necessarily bases. As far as I know, there is no known counterexample to this stronger conjecture. Moreover, this stronger conjecture is known to be true if we fix a single, standard basis B of V and insist that every Ii be a subset of B. Two proofs of this fact may be found in Section 2 of this paper.
Let me end this initial blog post here, with just one further comment that a couple of people that I have communicated with recently have some other concrete ideas that we can sink our teeth into immediately. I am going to invite them to explain those ideas in the comments to this blog post.