MA026 Advanced Combinatorics

Fakulta informatiky
jaro 2024
Rozsah
2/1/0. 3 kr. (plus ukončení). Ukončení: zk.
Vyučováno prezenčně.
Vyučující
Igor Balla, PhD (přednášející)
prof. RNDr. Petr Hliněný, Ph.D. (přednášející)
Garance
prof. RNDr. Petr Hliněný, Ph.D.
Katedra teorie programování – Fakulta informatiky
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Rozvrh
St 8:00–9:50 B411
  • Rozvrh seminárních/paralelních skupin:
MA026/01: každé sudé pondělí 10:00–11:50 B204, P. Hliněný
Předpoklady
MA010 Graph Theory
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Předmět si smí zapsat nejvýše 25 stud.
Momentální stav registrace a zápisu: zapsáno: 10/25, pouze zareg.: 0/25, pouze zareg. s předností (mateřské obory): 0/25
Mateřské obory/plány
předmět má 37 mateřských oborů, zobrazit
Osnova
  • Advanced structural graph theory: graph minors and well-quasi-ordering, width parameters, matching in general graphs, list coloring, intersection graphs
  • Topological graph theory: planarity testing and SPQR trees, MAXCUT algorithm in planar graphs, graphs on surfaces of higher genus, crossing numbers
  • Probabilistic method: review of tools - linearity of expectation and concentration bounds, lower bounds on Ramsey number, crossing number, and list chromatic number, Lovász Local Lemma
  • Regularity method: regularity decompositions, removal lemma, property testing algorithms
  • Extremal Combinatorics: Hales-Jewett Theorem, Van der Waerden Theorem, Gallai-Witt Theorem
Literatura
    doporučená literatura
  • DIESTEL, Reinhard. Graph theory. 4th ed. Heidelberg: Springer, 2010, xviii, 436. ISBN 9783642142789. info
    neurčeno
  • ALON, Noga a Joel H. SPENCER. The probabilistic method. 3rd ed. Hoboken, N.J.: Wiley, 2008, xv, 352. ISBN 9780470170205. info
  • MOHAR, Bojan a Carsten THOMASSEN. Graphs on surfaces. Baltimore: The Johns Hopkins University Press, 2001, xi, 291. ISBN 0801866898. info
Výukové metody
Weekly lectures, bi-weekly tutorials, individual homework projects
Metody hodnocení
individual homework project 30%, oral exam 70%
Vyučovací jazyk
Angličtina
Další komentáře
Studijní materiály
Předmět je vyučován každoročně.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/fi/jaro2024/MA026