Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

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 2023 to 2023
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:	not taught
Language:	Czech, English
Teaching methods:	full-time
Teaching methods:	full-time

Guarantor:	prof. Mgr. Zdeněk Dvořák, Ph.D.

Opinion survey results Examination dates Schedule Noticeboard

Annotation -

Last update: IUUK (13.04.2016)

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.

Aim of the course -

Last update: IUUK (13.04.2016)

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

Course completion requirements -

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

Oral exam.

Literature -

Last update: IUUK (13.04.2016)

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

Requirements to the exam - Czech

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

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

Syllabus -

Last update: IUUK (13.04.2016)

Turan's theorem and its generalizations

applications of regularity lemma

probabilistic arguments, dependent random choice

containers

quasirandom graphs

flag algebras and graph limits