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