Rota's Basis Conjecture

Rota’s Rainbow-Basis Conjecture

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

A matroid of rank $n$ has a collection of independent subsets satisfying heredity and augmentation, with every basis of size $n$. Regard the supplied $n$ bases as disjoint labelled copies when an element appears in more than one. Seek a partition of their $n^2$ occurrences into $n$ bases, each taking exactly one occurrence from each original basis. This is a rainbow decomposition, not merely one rainbow basis. [S1] [S2]

Statement recorded in the supplied source.

Given n bases of an n-dimensional matroid, can we find n disjoint rainbow bases? [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Prove the rainbow-basis decomposition universally or find a counterexample. [S1]

Short English statement

Can n bases of a rank-n matroid be rearranged into n new bases, each containing one element from every original basis?

Research attempt: the rank-two case, a partition-matroid construction, and a greedy obstruction

Status and source correction. The conjecture is not proved in general. The inspected arXiv record [S2] lists Alexey Pokrovskiy as its sole author; its abstract proves an asymptotic statement with both the number and sizes of the independent sets equal to $n-o(n)$, not an exact decomposition. We prove the following exact subcases independently.

1. Two bases of a rank-two matroid

Write the bases as labelled occurrences $\{a,b\}$ and $\{c,d\}$. None is a loop. Among nonloops in a rank-two matroid, dependence of a pair is exactly membership in the same parallel class, and parallelism is an equivalence relation. If both $\{a,c\}$ and $\{b,d\}$ are independent, they are the desired rainbow bases. Otherwise, after interchanging names within the rows if needed, assume $a,c$ are parallel. Since $c,d$ is independent, $a,d$ is independent. Since $a,b$ is independent, $b,c$ is independent. Therefore the other pairing $\{a,d\},\{b,c\}$ works. This also handles repeated underlying elements, because their separate occurrences are parallel.

2. A cyclic construction for partition matroids

Consider a rank-$n$ partition matroid with $n$ nonempty classes and capacity one in each class. Every basis contains one element of each class. Label rows by $i\in\mathbb Z/n\mathbb Z$, and within row $i$ denote its occurrence from class $j$ by $b_{ij}$. For column $k$, take \[C_k=\{b_{i,i+k}:i\in\mathbb Z/n\mathbb Z\}. \] Each column has one occurrence from each row. Its class labels $i+k$ run through all classes, so it is a basis. For fixed $i$, as $k$ varies every $b_{ij}$ appears exactly once; hence the columns partition all occurrences. This proves the exact conjecture for every such partition matroid, including the repeated-identical-basis configuration.

3. One good transversal need not leave a solvable remainder

Already over $\mathbb Q^2$, take rows \[B_1=\{e_1,e_2\},\qquad B_2=\{e_1+e_2,e_2\}. \] Choosing $\{e_1,e_1+e_2\}$ gives a perfectly valid rainbow basis, but the remaining pair consists of two labelled copies of $e_2$ and is dependent. The alternative first choice $\{e_1,e_2\}$ using the second-row $e_2$ leaves $\{e_2,e_1+e_2\}$, also a basis. Thus an existence theorem for a single rainbow basis cannot simply be iterated with arbitrary choices.

The obstruction is structural: after removing one transversal, each row has $n-1$ elements but need not be a basis of one common rank-$(n-1)$ matroid obtained by a shared contraction. Contracting different selected elements separately in different rows does not define a single residual matroid on all occurrences. A proof using induction must preserve a common independence structure, not just the right number of elements in each row.

4. Verification and exact remaining gap

The diagnostic checks the two rank-two pairings for all pairs of bases represented by nonzero vectors in $\mathbb F_p^2$ for $p=2,3,5$, computes the displayed rational determinants, and checks every row and class count in the cyclic construction through $n=20$. The rank-two proof rests on parallel-class equivalence, which does not characterize dependence in higher rank: three vectors can be dependent while every pair is independent. The partition construction similarly assumes independence depends only on class multiplicities. A mechanism handling higher-order dependencies while choosing all $n$ transversals simultaneously remains missing. The verified subcases and the greedy counterexample are partial work, not an exact solution inferred from an asymptotic theorem.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1457 (ALG-012), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 A. Pokrovskiy, Rota's Basis Conjecture holds asymptotically, arXiv:2008.06045. https://arxiv.org/abs/2008.06045. Bibliographic information from the supplied record.