Belépés címtáras azonosítással
magyar nyelvű adatlap
angol nyelvű adatlap
Graphs, Capacities, Entropies: Introduction to Information Theoretic Combinatorics
A tantárgy neve magyarul / Name of the subject in Hungarian: Gráfok, kapacitások, entrópiák: Bevezetés az információelméleti kombinatorikába
Last updated: 2022. június 10.
Dr. Gábor Simonyi, Department of Computer Science and Information Theory
Basics of graph theory, linear algebra and probability theory
Should be taken after basic courses of graph theory, linear algebra and probability theory.
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.
4 lectures per week.
Imre Csiszár, János Körner: Information Theory. Coding Theorems for Discrete Memoryless Systems, Second Edition, Cambridge University Press, 2011
László Lovász: Graphs and Geometry, American Mathematical Society, 2019
Edward R. Scheinermann, Daniel H. Ullman: Fractional Graph Theory, Wiley, 1997
Internet sources