Fractional coloring via entropy

In recent work, Martinsson and Steiner showed that every $K_3$-free $d$-degenerate graph $G$ has fractional chromatic number ${\chi }_f(G)=O\left(\frac{d}{\log d}\right)$. In this paper, we extend the result in two ways, 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. First, we consider locally $r$-colorable graphs $G$, i.e., where $\chi (G[N(v)])\le r$ for each vertex $v$. We show that $d$-degenerate locally $r$-colorable graphs $G$ satisfy ${\chi }_f(G)=O\left(\frac{d\log (2r)}{\log d}\right)$, strengthening a result of Alon (1996) on the independence number of such graphs. Second, we extend Martinsson and Steiner’s result to $r$-uniform $d$-degenerate hypergraphs $H$ of girth at least $4$. We show that such hypergraphs satisfy ${\chi }_f(H)\le c_r{\left(\frac{d}{\log d}\right)}^{\frac{1}{r-1}}$, implying a strict generalization of a seminal result of Ajtai, Komlós, Pintz, Spencer, and Szemerédi (1982) on the independence number of uncrowded hypergraphs. As a corollary, we obtain the same growth rate for the fractional chromatic number of $d$-degenerate linear hypergraphs. Our approach is constructive, yielding efficient algorithms to sample independent sets in each of the settings we consider.