# 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ó

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 BScTheorethics 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 óra 56 Félévközi készülés órákra 28 Felkészülés zárthelyire 8 Házi feladat elkészítése Kijelölt írásos tananyag elsajátítása Vizsgafelkészülés 28 Összesen 120
15. Syllabus prepared by Tamás Fleiner and Géza Tóth