SubjectsSubjects(version: 964)
Course, academic year 2024/2025
   Login via CAS
Introduction to extremal graph theory - NDMI092
Title: Úvod do extremální teorie grafů
Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
Faculty: Faculty of Mathematics and Physics
Actual: from 2024
Semester: winter
E-Credits: 3
Hours per week, examination: winter s.:2/0, Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Guarantor: prof. Mgr. Zdeněk Dvořák, Ph.D.
Teacher(s): prof. Mgr. Zdeněk Dvořák, Ph.D.
doc. Mykhaylo Tyomkyn, Ph.D.
Annotation -
Extremal graph theory studies maximal or minimal graphs satisfying given conditions. The course covers the basic results (especially generalizations and refinements of Turan's theorem) and methods (usage of regularity lemma, probabilistic techniques, stability) of extremal graph theory. We will also mention newer results using flag algebras and graph limits.
Last update: IUUK (13.04.2016)
Aim of the course -

Students will gain an overview of the fundamental results and methods of the extremal graph theory.

Last update: IUUK (13.04.2016)
Course completion requirements -

Oral exam.

Last update: Pangrác Ondřej, RNDr., Ph.D. (07.06.2019)
Literature -

Béla Bollobás, Extremal graph theory

Stasys Jukna, Extremal Combinatorics. With applications in computer science

https://www.dpmms.cam.ac.uk/~dc340/Extremal-course.html

http://tartarus.org/gareth/maths/notes/iii/Extremal_Graph_Theory_2013.pdf

http://www.math.tau.ac.il/~asafico/ext-graph-theory/notes.pdf

http://orion.math.iastate.edu/rymartin/ISU608EGT/S12/EGTbook.pdf

Last update: IUUK (13.04.2016)
Requirements to the exam - Czech

Zkouška proběhne ústní formou, v rozsahu 2-3 otázek pokrytých látkou probranou na přednáškách.

Last update: Dvořák Zdeněk, prof. Mgr., Ph.D. (08.10.2018)
Syllabus -

Turan's theorem and its generalizations

applications of regularity lemma

probabilistic arguments, dependent random choice

containers

quasirandom graphs

flag algebras and graph limits

Last update: IUUK (13.04.2016)
 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html