Combinatorics and Graph Theory 3 - NDMI073

• Title: Kombinatorika a grafy 3
• Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2022
• Semester: winter
• E-Credits: 5
• Hours per week, examination: winter s.:2/2, C+Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: taught
• Language: English, Czech
• Teaching methods: full-time
• Additional information: https://iuuk.mff.cuni.cz/~rakdver/index.php?which=uceni&subject=kg3
• Guarantor: prof. Mgr. Zdeněk Dvořák, Ph.D.; doc. RNDr. Vít Jelínek, Ph.D.
• Teacher(s): prof. Mgr. Zdeněk Dvořák, Ph.D.; Michal Seweryn, Ph.D.
• Class: Informatika Mgr. - Diskrétní modely a algoritmy; M Mgr. MSTR; M Mgr. MSTR > Povinně volitelné
• Classification: Informatics > Discrete Mathematics
• Is incompatible with: NDMX073
• Is interchangeable with: NDMX073

Annotation

English

The lecture extends NDMI012. An overview lecture on new trends in combinatorics and graph theory. The lecture is intended for master students or the first year PhD students.

Last update: T_KAM (20.04.2008)

Czech

Přehledová přednáška o nových trendech v kombinatorice a teorii grafů. Přednáška je určena primárně pro studenty magisterského stupně, popř. studenty prvního ročníku doktorského studia. Přednáška navazuje na předmět NDMI012 Kombinatorika a grafy II a rozšiřuje ho, k jejímu absolvování jsou nutné znalosti na úrovni tohoto předmětu.

Last update: G_I (17.03.2011)

Course completion requirements

English

Passing grade for tutorials (zápočet) is obtained on the basis of active participation, or homework. The nature of these requirements precludes retakes. Passing grade for tutorials is required before taking the exam, this can be relaxed at the discretion of the lecturer in exceptional cases (early exam dates).

Last update: Jelínek Vít, doc. RNDr., Ph.D. (07.10.2021)

Czech

Předmět je zakončen zápočtem a zkouškou. Zápočet bude získán za aktivní účast na cvičeních, případně za řešení domácích úkolů. Povaha kontroly předmětu vylučuje opravné termíny. Získání zápočtu je podmínkou pro konání zkoušky, kromě výjimek (předtermíny) stanovených vyučujícím.

Last update: Jelínek Vít, doc. RNDr., Ph.D. (07.10.2021)

Literature

English

R. Diestel, Graph theory, 3rd edition, Springer, 2005.

S. Jukna, Extremal combinatorics with application in computer science, Springer, 2001.

Last update: T_KAM (20.04.2008)

Requirements to the exam

English

Oral exam consisting of 2-3 questions on subjects covered by the lectures.

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

Czech

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

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

Syllabus

English

New trends in graph theory (graph minors, Szemeredi Regularity Lemma, Removal Lemma), advanced results from extremal combinatorics (theorems of Hales-Jewett and Gallai-Witt).

Last update: Šámal Robert, doc. Mgr., Ph.D. (08.10.2018)

Czech

Nové trendy v teorii grafů (grafové minory, Szemeredi Regularity Lemma, Removal Lemma), pokročilé výsledky z extremální kombinatoriky (Hales-Jewettova věta, Gallai-Wittova věta).

Last update: Šámal Robert, doc. Mgr., Ph.D. (08.10.2018)