Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

    Belépés
    címtáras azonosítással

    vissza a tantárgylistához   nyomtatható verzió    

    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.

    Budapest University of Technology and Economics
    Faculty of Electrical Engineering and Informatics
    PhD course
    Course ID Semester Assessment Credit Tantárgyfélév
    VISZD306   4/0/0/v 5  
    3. Course coordinator and department Dr. Simonyi Gábor,
    4. Instructors

    Dr. Gábor Simonyi, Department of Computer Science and Information Theory

    5. Required knowledge

    Basics of graph theory, linear algebra and probability theory

    6. Pre-requisites
    Ajánlott:

    Should be taken after basic courses of graph theory, linear algebra and probability theory.

    7. Objectives, learning outcomes and obtained knowledge Illustrating the fruitful influence of information theoretic problems and tools in combinatorics and graph theory. Showing basic results connected to this area and further developing discrete mathematical thinking within this framework. 
    8. Synopsis

    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. 

    9. Method of instruction

    4 lectures per week.

    10. Assessment oral exam
    12. Consultations By appointment, on office hours.
    13. References, textbooks and resources

    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

    14. Required learning hours and assignment
    Kontakt óra56
    Félévközi készülés órákra28
    Felkészülés zárthelyire
    Házi feladat elkészítése14
    Kijelölt írásos tananyag elsajátítása14
    Vizsgafelkészülés38
    Összesen150
    15. Syllabus prepared by

    Dr. Gábor Simonyi, Department of Computer Science and Information Theory