← All problems

Gabow's cyclic basis conjecture

16 years old · traced to

Let M\mathcal{M} be a matroid and let

B1={b1,…,br},B2={b1′,…,br′}B_1=\{b_1,\ldots,b_r\},\qquad B_2=\{b'_1,\ldots,b'_r\}

be two bases. Gabow's conjecture. There exist permutations σ\sigma and σ′\sigma' such that in the sequence

(bσ(1),…,bσ(r),bσ′(1)′,…,bσ′(r)′),(b_{\sigma(1)},\ldots,b_{\sigma(r)},b'_{\sigma'(1)},\ldots,b'_{\sigma'(r)}),

every set of rr 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 rr-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

Refreshed
Open

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 rr 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 44 or 55 (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 gcd⁡(∣E∣,r(M))=1\gcd(|E|,r(M))=1: ∣A∣/r(A)≤∣E(M)∣/r(M)|A|/r(A)\leq |E(M)|/r(M) for every nonempty A⊆E(M)A\subseteq E(M) (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 (B1,B2)(B_1,B_2) to (B2,B1)(B_2,B_1). 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.

Sources

Solutions 0

No solutions have been posted yet.