Rota’s basis conjecture

Two nonparallel arrows in a plane form a basis: weighted combinations of them can reach any point, with neither arrow redundant. Put two such bases in two rows. If each row lists right then up, the first column contains two parallel right arrows and the second two parallel up arrows. Swap the order in the second row, and each column becomes a basis. Rota’s conjecture asks whether this rearrangement is always possible for n bases in n dimensions: reorder within each row so every column is also a basis.[1]

A basis is a complete independent selection: for vectors it spans the space with no redundant vector. For vectors in $n$ dimensions, can $n$ given bases be rearranged into $n$ new bases, each taking one element from every original? The same rearrangement question applies to abstract independence systems, defined below. With $e_1=(1,0)$, $e_2=(0,1)$, the two rows $(e_1,e_2)$, $(e_1,e_2)$ initially give dependent columns. Reversing the second row gives columns $(e_1,e_2)$ and $(e_2,e_1)$, both bases; their two-by-two determinants are 1 and −1. Copies from different rows are labelled separately, so each occurrence is used once. This checks the example, not the general conjecture.

A finite matroid specifies independent subsets: the empty set is independent, every subset of an independent set is independent, and a smaller independent set can be enlarged by some element of a larger independent set. Its rank is the maximum independent-set size, and a basis has that size. A transversal basis takes exactly one element from each of the given rows. The enlargement rule guarantees that one can be selected greedily. Rota’s conjecture asks for all $n$ such bases simultaneously, disjoint in their labelled occurrences.[1]

The two-row example works, but the guarantee must cover every collection in every dimension. Finding almost all the required columns can still leave a remainder that cannot yet be arranged. The conjecture also extends to abstract independence systems called matroids, which include both independent vectors and cycle-free selections of graph edges.[1]

Montgomery and Sauermann’s 2025 preprint proves that for each fixed $\varepsilon>0$, all sufficiently large $n$ admit at least $(1-\varepsilon)n$ disjoint transversal bases, and that at most $(1+\varepsilon)n$ transversal bases suffice to cover all the given elements. The covering bases need not be disjoint. These estimates approach the target in proportion, while leaving the exact requirement of $n$ disjoint full bases unresolved. Random-input and specially structured cases have narrower quantifiers than every rank-$n$ matroid and every collection of bases.[1]

A basis is a complete collection without internal redundancy. The question asks whether several such collections can be mixed into new complete collections while sharing the original inputs fairly. In graphs this becomes a question about combining differently coloured connecting trees, with one edge of each colour in every new tree.[1]

For the graph version, take $n$ spanning trees on $n+1$ vertices and give each tree its own colour. Their edges, including separately labelled copies of any shared edge, should be partitionable into new spanning trees with exactly one edge of each colour. Each new tree must connect all vertices without a cycle. The task combines balance among colours with the structural requirement of independence. This shows why finding one balanced tree is less demanding than rearranging every edge into balanced trees at once, and why the conjecture is about how complete independent structures coexist.[1]