PředmětyPředměty(verze: 901)
Předmět, akademický rok 2022/2023
  
Ú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 2022
Semestr: zimní
E-Kredity: 3
Rozsah, examinace: zimní s.:2/0 Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Virtuální mobilita / počet míst: ne
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Garant: prof. Mgr. Zdeněk Dvořák, Ph.D.
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
Anotace -
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.
Cíl předmětu -
Poslední úprava: IUUK (13.04.2016)

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

Podmínky zakončení předmětu -
Poslední úprava: RNDr. Ondřej Pangrác, Ph.D. (07.06.2019)

Ústní zkouška.

Literatura -
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 -
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

 
Univerzita Karlova | Informační systém UK