Ú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 2024
• 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: vyuč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.
• Vyučující: prof. Mgr. Zdeněk Dvořák, Ph.D.; Mykhaylo Tyomkyn, Ph.D.

Anotace

čeština

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.

Poslední úprava: IUUK (13.04.2016)

angličtina

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.

Poslední úprava: IUUK (13.04.2016)

Cíl předmětu

čeština

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

Poslední úprava: IUUK (13.04.2016)

angličtina

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

Poslední úprava: IUUK (13.04.2016)

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

čeština

Ústní zkouška.

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

angličtina

Oral exam.

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

Literatura

čeština

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

Poslední úprava: IUUK (13.04.2016)

Požadavky ke zkoušce

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

Poslední úprava: Dvořák Zdeněk, prof. Mgr., Ph.D. (08.10.2018)

Sylabus

čeština

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

Poslední úprava: IUUK (13.04.2016)

angličtina

Turan's theorem and its generalizations

applications of regularity lemma

probabilistic arguments, dependent random choice

containers

quasirandom graphs

flag algebras and graph limits

Poslední úprava: IUUK (13.04.2016)