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

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.

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.