Gabow's cyclic basis conjecture
Let be a matroid and let
be two bases. Gabow's conjecture. There exist permutations and such that in the sequence
every set of cyclically consecutive elements forms a basis. The conjecture strengthens the two-base case of White's basis sequence exchange problem by requiring a cyclic ordering with all consecutive -element windows independent as bases.
References
6 papers in this index state this conjecture (2010–2025). The statement above is taken from the most recent of them; the others are arXiv:2411.01061, arXiv:2302.01445, arXiv:1601.03526, arXiv:1110.1826, arXiv:1011.1010.
Source: Hannaneh Akrami, Siyue Liu, Roshan Raj and László A. Végh, “Matroids are Equitable”, arXiv:2507.12100 (2025).
Progress summary
The general conjecture remains open, although it is proved for several important classes of matroids.
Gabow’s 1976 conjecture asks whether any two bases can be arranged around a circle so that every block of consecutive elements is again a basis. It is equivalent to a sequential symmetric-exchange formulation.
Known results
- The conjecture is known for graphic, sparse paving, split, and regular matroids, and for matroids of rank at most or (2024).
- For split matroids whose ground set decomposes into pairwise disjoint bases, cyclic orderability is proved algorithmically (2024).
- For whole-ground-set cyclic orderings, a characterization is known when : for every nonempty (2009).
July 2025 update
The preprint Matroids are Equitable explicitly states that Gabow’s conjecture remains open even for two bases, including the case of swapping to . No proof or counterexample was found in the retrieved material.
Current status (as of October 2026): Special classes and related whole-ground-set cases are settled, but Gabow’s conjecture for arbitrary pairs of bases remains open.
Solutions 0
No solutions have been posted yet.