Fractional coloring via entropy

Abstract

In recent work, Martinsson and Steiner proved that triangle-free $d$-degenerate graphs have fractional chromatic number ${\chi }_f(G)=O\left(\frac{d}{\log d}\right)$. Here, we introduce an alternate proof of the bound rooted in the analysis of the entropy of certain random variables. Beyond simplifying the original argument, our technique naturally generalizes to broader settings. In this paper, we focus on two extensions of the result. First, we consider locally $r$-colorable graphs $G$, where $\chi (G[N(v)])\le r$ for every vertex $v$. We show that $d$-degenerate locally $r$-colorable graphs 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$ with girth at least $4$, showing that ${\chi }_f(H)\le c_r{\left(\frac{d}{\log d}\right)}^{\frac{1}{r-1}}$ for a constant $c_r>0$. This yields a strict generalization of a seminal result of Ajtai, Komlós, Pintz, Spencer, and Szemerédi (1982) on the independence number of uncrowded hypergraphs. Via random sampling as introduced by Duke, Lefmann, and Rödl (1995), we obtain the same asymptotic bound for $d$-degenerate linear hypergraphs. As a corollary, we establish a recent conjecture of Verstraëte and Wilson (2026) on the independence number of linear hypergraphs. Our arguments generalize to the setting of fractional colorings with local demands, introduced by Kelly and Postle (2024). This yields previously unknown degree-sequence lower bounds on the independence number across each setting considered. Furthermore, our approach is constructive, yielding efficient randomized algorithms for sampling independent sets in these contexts.

22 pages plus references