Seminar in Discrete Mathematics - He Guo

The seminars in Discrete Mathematics are aimed at researchers, employees, and students.

This week's seminar is given by He Guo, Umeå University.

Title: Intersections of matroids

Abstract: We study simplicial complexes (hypergraphs closed under taking subsets) that are the intersection of a given number k of matroids. We prove bounds on their chromatic numbers (the minimum number of edges required to cover the ground set) and their list chromatic numbers. Settling a conjecture of Kiraly and Berczi--Schwarcz--Yamaguchi, we prove that the list chromatic number is at most k times the chromatic number. The tools used are in part topological.

If time permits, I will also discuss

• a result proving that the list chromatic number of the intersection of two generalized partition matroids equals its chromatic number, which extends a famous theorem of Galvin and proves conjectures by Kiraly, Berczi et. al., and Aharoni—Berger in this case​.
• a result proving that the list chromatic number of the intersection of two matroids is at most the sum of the chromatic numbers of each matroid, improving a result by Aharoni and Berger from 2006.
• a result regarding three polytopes associated with k-tuples of matroids and bounds on the distances between them, following the footsteps of Edmonds, who considered the case k=2.

The talk is based on works joint with Ron Aharoni, Eli Berger, and Daniel Kotlar. 

In this talk, there is no assumption about background knowledge of matroid theory or algebraic topology.