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

    címtáras azonosítással

    vissza a tantárgylistához   nyomtatható verzió    

    Combinatorics and Graph Theory 2

    A tantárgy neve magyarul / Name of the subject in Hungarian: Kombinatorika és gráfelmélet 2

    Last updated: 2018. július 8.

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

    Mathematics BSc

    Theorethics Specialization 

    Course ID Semester Assessment Credit Tantárgyfélév
    VISZA026   2/2/0/v 4 5
    3. Course coordinator and department Dr. Fleiner Tamás,
    4. Instructors

    Tamás Fleiner

    Géza Tóth

    5. Required knowledge Basic graph theoretical notions and algorithms
    6. Pre-requisites
    Combinatorics and Graph Theory 1.        BMEVISZA025
    8. Synopsis

    Geometric and abstract duality, weak isomorphism (2-isomorphism) and the Whitney theorems.

    Vertex and edge coloring, Mycielsky's construction, Brooks' theorem. 5-colour theorem, Vizing's theorem, connection of edge-colouring to matchings, Petersen's theorem.

    List colouring of graphs, Galvin's theorem.

    Perfect graphs, interval graphs and the perfect graph theorem.

    Ramsey's theorem, Erdős-Szekeres theorem, Erdős' lower bound and the probabilistic method.

    Turán's theorem, Erdős-Stone theorem, Erdős-Simonovits theorem.

    Hypergraphs, Erdős-Ko-Rado theorem, Sperner's theorem and the LYM inequality.

    De Bruijn-Erdős theorem, finite planes, construction from finite field, and from difference sets.

    Generating functions, Fibonacci numbers, Catalan numbers. Posets, Dilworth's theorem.
    9. Method of instruction

    Two lectures and two  tutorials each week.

    10. Assessment

    In the semester: two midterm. The condition for the audit is that both midterms are succesful.

    In the exam season: oral exam for those that have a valid audit. The final grade is based 40% on the midterms, 10% on the homework assignments and 50% on the oral exam.

    11. Recaps According to the general rules: one midterm can be repeated.
    12. Consultations According to demand
    13. References, textbooks and resources

    R. Diestel: Graph Theory (online available)

    J.A. Bondy & U.S.R. Murty: Graph Theory with Applications

    14. Required learning hours and assignment
    Kontakt óra56
    Félévközi készülés órákra28
    Felkészülés zárthelyire8
    Házi feladat elkészítése 
    Kijelölt írásos tananyag elsajátítása 
    15. Syllabus prepared by Tamás Fleiner and Géza Tóth