= Degree-ordered independent-set entropy bound
{title2=$i(G)\leq\prod_i(2^{b_i+1}-1)^{1/d_i}$}
Order vertices by nonincreasing positive degrees $d_i$, and let $b_i$ count preceding neighbors. The <Madiman-Tetali inequality> applied to preceding-neighbor sets and $b_i$ copies of singleton $i$ bounds the entropy of a uniformly chosen <independent set>. In each local term, all-zero neighbor assignment permits two choices at $i$, while every other assignment permits at most one. The maximum-entropy bound gives $\log_2(2^{b_i+1}-1)$ for that term. Complete bipartite graphs $K_{d,d}$ attain equality when one part is ordered before the other.
Back to article page
