Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269 - Combinatorics Seminar

Dr. He Guo

Umea University

Coloring and list coloring in intersections of matroids

Abstract:

It is known that in matroids the list chromatic number is equal to the chromatic number. We investigate the gap within these pairs of parameters for hypergraphs that are the intersection of a given number $k$ of matroids. We prove that in such hypergraphs the list chromatic number is at most $k$ times the chromatic number and at most $2k-1$ times the maximum chromatic number among the $k$ matroids. This solves a conjecture posed by Kiraly and also by Berczi, Schwarcz, and Yamaguchi. We also prove 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. The tools used are in part topological (but for the talk we do not assume background knowledge of matroid theory or algebraic topology).

Based on joint works with Ron Aharoni, Eli Berger, and Dani Kotlar, see arXiv:2407.08789. 

Host: Lutz Warnke

May 27, 2025

2:00 PM

APM 7321

Research Areas

Combinatorics Geometry and Topology

****************************