Gabow's sequential symmetric exchange conjecture for matroid bases

About 4 years old · traced to

Let MM be a matroid of rank rr, and let AA and BB be bases of MM. An ordering of a basis is a listing of its elements, so write

A=(a1,…,ar),B=(b1,…,br).A=(a_1,\dots,a_r),\qquad B=(b_1,\dots,b_r).

Gabow's conjecture. There are orderings A=(a1,…,ar)A=(a_1,\dots,a_r) and B=(b1,…,br)B=(b_1,\dots,b_r) such that

{a1,…,ai,bi+1,…,br}\{a_1,\dots,a_i,b_{i+1},\dots,b_r\}

and

{b1,…,bi,ai+1,…,ar}\{b_1,\dots,b_i,a_{i+1},\dots,a_r\}

are bases for every i=0,…,ri=0,\dots,r. This is the sequential symmetric exchange property, equivalently expressible through a cyclic ordering in which both bases form intervals and every rr cyclically consecutive elements form a basis. The conjecture concerns whether the extreme case of Gabow's symmetric-exchange decomposition can always be achieved.

References

Primary source

Kristóf Bérczi and Tamás Schwarcz, “Exchange distance of basis pairs in split matroids”, arXiv:2203.01779 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.