09/12/2025 - 14:00 - EPL, Bâtiment Euleur, A.002

Laszlo Végh

University of Bonn

Matroids are equitable

Abstract :

We show that if the ground set of a matroid can be partitioned into k≥2 bases, then for any given subset S of the ground set, there is a partition into k bases such that the sizes of the intersections of the bases with S may differ by at most one, settling a conjecture by Fekete and Szabó from 2011. 

In the talk, I will present the surprisingly simple proof, as well as some extensions and applicaitons in fair division. I will also give an overview of related questions on matroid basis exchanges. This is based on joint work with Hannaneh Akrami, Roshan Raj, and Siyue Liu.