Seminar Details
2025-12-09 (14:00) : Matroids are equitable
At EULER (room A.002)
Organized by Mathematical Engineering
Speaker :
László Végh (University of Bonn)
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.