Úvod do extremální teorie grafů - NDMI092

• Anglický název: Introduction to extremal graph theory
• Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2023
• Semestr: zimní
• E-Kredity: 3
• Rozsah, examinace: zimní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: nevyučován
• Jazyk výuky: čeština, angličtina
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Garant: prof. Mgr. Zdeněk Dvořák, Ph.D.

Anotace

čeština

Poslední úprava: IUUK (13.04.2016)

Extremální teorie grafů studuje maximální či minimální grafy splňující dané podmínky. V této úvodní přednášce probereme základní výsledky (zejména zobecnění a zjemnění Turánovy věty) a metody (použití regularity lemmatu, pravděpodobnostní metoda, stabilita) extremální teorie grafů, a zmíníme některé novější výsledky, zejména využití flag algeber a grafových limit.

angličtina

Poslední úprava: 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.

Cíl předmětu

čeština

Poslední úprava: IUUK (13.04.2016)

Studenti získají základní přehled o extremální teorii grafů a jejích metodách.

angličtina

Poslední úprava: IUUK (13.04.2016)

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

Podmínky zakončení předmětu

čeština

Poslední úprava: RNDr. Ondřej Pangrác, Ph.D. (07.06.2019)

Ústní zkouška.

angličtina

Poslední úprava: RNDr. Ondřej Pangrác, Ph.D. (07.06.2019)

Oral exam.

Literatura

čeština

Poslední úprava: 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

Požadavky ke zkoušce

Poslední úprava: 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.

Sylabus

čeština

Poslední úprava: IUUK (13.04.2016)

Turánova věta a její zobecnění

aplikace regularity lemmatu

pravděpodobnostní metody, dependent random choice

kontejnéry

quasináhodné grafy

flag algebry a grafové limity

angličtina

Poslední úprava: 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