= Entropy weight of a graph cover
{title2=$\sum_iw(G_i)\geq n\log_2(n/\alpha)$}
If graphs $G_i$ cover the edges of an $n$-vertex graph with <independence number> at most $\alpha$, their coloring entropy weights satisfy the displayed bound. A random vertex's color is recorded in every covering graph containing it; independent dummy colors with matching marginal laws fill the other positions. Conditional on all recorded colors, compatible vertices form an <independent set>, leaving conditional entropy at most $\log_2\alpha$. The <mutual information> carried by the colors is at most $n^{-1}\sum_iw(G_i)$, proving the bound.
Back to article page
