Information Theory in Combinatorics I

on YouTube ↗01h 14m

" summary

Entropy methods give concrete counting bounds via Shearer's Lemma: if each variable appears in at least k subsets then k·H(all) ≤ sum H(on subsets). Applications: a 3D set with n-point projections has size ≤ N^{3/2}; number of graph homomorphisms ≤ (2·|E(G)|)^{α(T)} where fractional cover number α(T)=3/2 for triangle; maximum independent sets in d-regular graphs come from disjoint K_{d,d} copies; a trace inequality trace(ABC)^2 ≤ trace(AA^T)trace(BB^T)trace(CC^T) follows from a weighted version. Bregman and Spencer results are next.

AI-written summary · about

" chapters (9)

1. 0:00Introduction to entropy
2. 5:41Overview of Shears Lemma
3. 8:58Proving Shears Lemma
4. 15:10Applications to projections
5. 20:02Counting graph homomorphisms
6. 29:01Formalizing the homomorphism bound
7. 39:33Counting independent sets
8. 44:42Entropy bounds for independent sets
9. 1:00:17Weighted Shears Lemma and traces