Graphs, Capacities, Entropies: Introduction to Information Theoretic Combinatorics

1. Shannon capacity of graphs, the simplest bounds of this parameter (clique number and chromatic number), the pentagon problem, the influence of this problem area to graph theory: introduction of perfect graphs.

2. Perfectness of some basic graph classes, Perfect Graph Theorem and Strong Perfect Graph Theorem, Substitution Lemma.

3. Further interesting graph families: Kneser graphs, Mycielski graphs, normal graphs, perfectness of normal graphs.

4. Fractional chromatic number, its connection to linear programming, the gap between chromatic number and fractional chromatic number, fractional chromatic number of vertex-transitive graphs. Graph homomorphisms, coloring parameters viewed via graph homomorphisms.

5. Zero-erro capacity of a channel with feedback, its relation to fractional chromatic number, Lovász’s theorem about the possible ratio of fractional and usual chromatic number, McEliece-Posner theorem. 

6. Lovász theta number of a graph, solution of the pentagon problem.

7. Bohman-Holzman theorem about the Shannon capacity of odd cycles, connection between Shannon capacity and Ramsey numbers.

8. Witsenhausen rate of graphs, its relation to Shannon capacity.

9. Sperner capacity of directed graphs and its bounds.

10. Capacity of graph families, information theoretic interpretation for undirected and directed graphs. Connection to extremal set theory.

11. Probabilistic refinement of capacity parameters, Gargano-Körner-Vaccaro theorem.

12. Graph entropy and its information theoretic interpretation, basic properties, applications of its sub-additivity.

13. Additivity problems, characterization of perfect graphs in terms of graph entropy.  

14. Kahn and Kim’s algorithm for extending a partial order to a complete order using graph entropy.