Research Technology Master Calendar

Speaker: Abhishek Dhawan (UIUC)

Title: Fractional coloring d-degenerate hypergraphs

Abstract: In recent work, Martinsson and Steiner showed that every K_3-free d-degenerate graph G has fractional chromatic number \chi_f(G) = O(d/\log d). In this work, we extend the result to hypergraphs of girth at least 4, employing an approach rooted in the analysis of the entropy of certain probability distributions. Our argument provides a template to tackle other problems, so it is of independent interest. We show that r-uniform d-degenerate hypergraphs of girth at least 4 have fractional chromatic number at most c_r(d/\log d)^{1/(r-1)} for some c_r > 0. As a corollary, we obtain the same growth rate for the fractional chromatic number of d-degenerate linear hypergraphs for r \geq 3.