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: 2023. május 30.

    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
    Ajánlott:
    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ákra14
    Felkészülés zárthelyire8
    Házi feladat elkészítése14 
    Kijelölt írásos tananyag elsajátítása 
    Vizsgafelkészülés28
    Összesen120
    15. Syllabus prepared by Tamás Fleiner and Géza Tóth