The Balister-Bollobas inequality says that if is the coordinate multiplicity in a multiset , and , then . More generally, each union-intersection compression decreases the entropy sum, by entropy submodularity.
For an exact -cover define and . Compressing the family of gives the nested family of all together with full sets. Rearranging the resulting bound gives the upper Madiman-Tetali inequality. Conversely, compressing the family of all together with full sets gives the nested family of , yielding the lower bound. In conditional-entropy notation these areThe coordinate multiplicities agree in each compression, because is an exact -cover. An equivalent proof expands the chain rule for information entropy contributions and uses conditioning reduces entropy. It also gives the upper inequality for arbitrary fractional covers and the lower inequality for fractional packings.
Choose an independent set uniformly and let indicate whether it contains vertex . Then . Put and . Form a multiset containing every nonempty and copies of singleton . Each coordinate occurs exactly times: in later-neighbor sets and in singleton copies.
For a set in this multiset, weight it by . These weights form a fractional cover, since each of the occurrences of has weight at least . Apply the upper Madiman-Tetali inequality. Since every precedes , one has ; enlarging that set's weight to and removing conditioning only enlarges its nonnegative contribution. For singleton terms retain the useful conditioning on . ThusFor , let . Every nonzero neighbor assignment forces , while the all-zero assignment allows at most two values. The maximum entropy on a finite alphabet givesThe last inequality is the binary entropy maximization formula, or the log-sum inequality, with group sizes and . If the whole term is zero, also agreeing with the formula. Exponentiating proves the degree-ordered independent-set entropy bound
Take for any , ordering one part before the other. Every degree is ; the first vertices have , the last have . The bound is therefore . An independent set lies entirely in one part, giving possibilities after subtracting the twice-counted empty set. Hence equality holds. Disjoint unions of such ordered components give further equality examples.
Articles by others on the same topic
There are currently no matching articles.