Reconfiguring Ordered Bases of a Matroid

Publication date 3 December 2016

Combinatorial aspects of matroids and geometric lattices (05B35)

Abstract: For a matroid with an ordered (or "labelled") basis, a basis exchange step removes one element with label

l

and replaces it by a new element that results in a new basis, and with the new element assigned label

l

. We prove that one labelled basis can be reconfigured to another if and only if for every label, the initial and final elements with that label lie in the same connected component of the matroid. Furthermore, we prove that when the reconfiguration is possible, the number of basis exchange steps required is

O (r^{1.5})

for a rank

r

matroid. For a graphic matroid we improve the bound to

O (r l o g r)

.

This page was built for publication: Reconfiguring Ordered Bases of a Matroid

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6280440)