Gabow's sequential symmetric exchange conjecture for matroid bases

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.

Sources & referencesView supporting material

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.