Skip to main content
To KTH's start page To KTH's start page

Kristof Bérczi : Exchange distance in split matroids

Time: Wed 2022-04-13 10.15 - 11.15

Location: Zoom meeting ID: 654 5562 3260

Participating: Kristof Bérczi (Eötvös Loránd University)

Export to calendar

Abstract: A nice feature of split matroids is that they generalize paving
matroids, while being closed under duality and taking minors. In this
talk, we introduce the notion of elementary split matroids, a subclass
that contains all connected split matroids. We give a hypergraph
characterization of elementary split matroids in terms of independent
sets. Based on this characterization, 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 conjectures of
Gabow, White, and Farber 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 Király, Tamás Schwarcz, Yutaro Yamaguchi and Yu Yokoi.

Zoom meeting ID: 654 5562 3260

Zoom link: