PředmětyPředměty(verze: 837)
Předmět, akademický rok 2018/2019
   Přihlásit přes CAS
Ú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 2018
Semestr: zimní
E-Kredity: 3
Rozsah, examinace: zimní s.:2/0 Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Garant: doc. Mgr. Zdeněk Dvořák, Ph.D.
Anotace -
Poslední úprava: (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.
Cíl předmětu -
Poslední úprava: (13.04.2016)

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

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

 
Univerzita Karlova | Informační systém UK