Základy konečné a nekonečné kombinatoriky - ALGV19003

• Anglický název: Introduction to finite and infinite combinatorics
• Zajišťuje: Katedra logiky (21-KLOG)
• Fakulta: Filozofická fakulta
• Platnost: od 2024
• Semestr: zimní
• Body: 4
• E-Kredity: 4
• Způsob provedení zkoušky: zimní s.:
• Rozsah, examinace: zimní s.:2/0, Zk [HT]
• Počet míst: neomezen / neurčen (neurčen)
• 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
• Způsob výuky: prezenční
• Poznámka: předmět je možno zapsat mimo plán; povolen pro zápis po webu
• Garant: Mgr. Šárka Stejskalová, Ph.D.
• Vyučující: Mgr. Šárka Stejskalová, Ph.D.

Anotace

V předmětu se student seznamí se základními pojmy konečné a nekonečné kombinatoriky, jako jsou grafy, stromy, rozklady a s nimi související různé verze Ramseyho věty. Většinu pojmů a výsledků nejprve představíme na konečných množinách, kde jsou snáze pochopitelné, a potom některé zobecníme pro nekonečné množiny. Tím získáme lepší představu o podobnostech a odlišnostech konečné a nekonečné kombinatoriky.

Poslední úprava: Stejskalová Šárka, Mgr., Ph.D. (28.09.2020)

Literatura

J. Matoušek a J. Nešetřil, Kapitoly z diskrétní matematiky. Karolinum, Praha, 2002.

B. Balcar a P. Štěpánek, Teorie množin. Academia, Praha, 2000.

L. J. Halbeisen, Combinatorial Set Theory. Springer-Verlag, London, 2012.

Poslední úprava: Stejskalová Šárka, Mgr., Ph.D. (24.09.2020)

Sylabus

Grafy: isomorfismus grafů, podgrafy, souvislost, sled v grafu, cesta v grafu, klika a nezávislá množina, skóre grafu, eulerovské grafy, rovinné grafy, obarvení grafu.

Stromy: isomorfismus stromů, kostra grafu, Königovo lemma, stromy na vyších kardinálech (Aronszajnův strom, Suslinův strom, Kurepův strom).

Rozklady: homogení množina, konečná a nekonečná verze Ramseyho věty a její důsledky.

Poslední úprava: Stejskalová Šárka, Mgr., Ph.D. (04.10.2022)