2024/07/11 by Ron Aharoni, Eli Berger, Aharoni, Ron +5 · 2 citations
Computer Science · #05B35 #05C10 #05C15 #05C70 #05C72 #52B40 #57M15 #90C27 #Advanced Algebra and Logic #Algebraic Topology (math.AT) #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2407.08789
openalex publication_date 2024/07/11 · openalex created_date 2024/07/16 · openalex updated_date 2026/07/28
It is known that in matroids the difference between the chromatic number and the fractional chromatic number is smaller than 1, and that 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. We study the relationship between three polytopes associated with k-sets of matroids, and connect them to bounds on the fractional chromatic number of the intersection of the members of the k-set. This also connects to bounds on the matroidal matching and covering number of the intersection of the members of the k-set. The tools used are in part topological.