[Math] What’s the motivation of entropy as a combinatorical tool? What problems is it able to solve

co.combinatoricsentropy

I am interested in using Shannon's entropy in combinatorics. It is often presented with a motivation of how much information can be passed, but assume I am not interested in that, I want to understand why it is useful as a tool to bound objects (with examples now).

Several examples that demonstrate that very nontrivial results follow from relatively entropy arguments are:

  1. Bregman's inequality about permanents.
  2. Whiteny's inequality about volume and its projections.
  3. Shearer's lemma and numerous consequences; bounds on the number of independent sets in bipartite d-regular graph, number of homomorphisms to graph…
  4. The largest size of an intersection unique family (see https://link.springer.com/article/10.1007/BF02579460 ).

If you could help me with the following I'd be very happy;

  1. How would someone just interested in counting and bounding combinatorics arrive at entropy?

  2. A common theme (noted by my proffessor when teaching about it) to some of the results are that original proofs used convexity arguments, how healthy is it to be think of entropy in combinatorics as a clean way to state convexity arguments and deriving nontrivial results by assigning weights to objects and bounding sums?

  3. When can proofs be translated to entropy proofs? For instance I find it strange there is the $k-intersection$ proof with entropy, while I'm not aware of an entropy proof for sperner's theorem about antichains.

  4. When are problems suspectible to entropy methods?

Cheers.

Best Answer

I'll only attempt to answer question 1.

Let's say you have 10 objects, divided into three blocks of respective sizes 2, 5 and 3. What's the probability that a random endomorphism of your set of objects preserves the blocks, i.e. sends each element of the set to an element of the same block? It's

$$ \frac{\text{number of block-preserving endos}}{\text{number of endos}} = \frac{2^2 5^5 3^3}{10^{10}} = \biggl(\frac{2}{10}\biggr)^2 \biggl(\frac{5}{10}\biggr)^5 \biggl(\frac{3}{10}\biggr)^3 $$

Now, the entropy of a finite probability distribution $p = (p_1, \ldots, p_n)$ is, by definition,

$$ H(p) = -\log\bigl(p_1^{p_1} \cdots p_n^{p_n}\bigr). $$

Associated with our set-up is the probability distribution $p = (2/10, 5/10, 3/10)$. The probability that a random endomorphism of our set preserves the blocks is, then, simply

$$ e^{-10H(p)}. $$

In particular, the answer only depends on the number of elements in the set and the entropy of $p$ — not on the block sizes themselves.

This is one way in which entropy arises naturally in elementary counting problems. It also shows that sometimes, it's the exponential of entropy that plays the more fundamental role.

Related Question