Exchange distance of basis pairs in split matroids

Speaker: Kristóf Bérczi
Room 3.517 (EGRES seminar)

The basis exchange axiom has been a driving force in the development of matroid theory. While studying the structure of symmetric exchanges, Gabow proposed the problem that any pair of bases admits a sequence of symmetric exchanges. A different extension of the exchange axiom was proposed by White, who investigated the equivalence of compatible basis sequences. Farber studied the structure of basis pairs, and conjectured that the basis pair graph of any matroid is connected. These conjectures suggest that the family of bases of a matroid possesses much stronger structural properties than we are aware of. In this talk, we give an upper bound on the minimum number of exchanges needed to transform a basis pair into another for split matroids. As a corollary, we verify the above mentioned long-standing conjectures for this large class. Being a subclass of split matroids, our result settles the conjectures for paving matroids as well.

Joint work with Tamás Schwarcz.