Témata bakalářských a diplomových prací

Jan Kynčl, KAM (kyncl zavináč kam.mff.cuni.cz)

Na této stránce jsou uvedeny příklady širších témat z diskrétní geometrie a kombinatoriky; pokud Vás nějaké zaujme, kontaktujte mě např. e-mailem a pokusíme se dohodnout na konkrétním zadání. Můžeme se dohodnout i na jiném tématu z oblasti.

Kreslení geometrických grafů na zadané množiny bodů

Je možné daný graf nakreslit v rovině tak, aby jeho vrcholy tvořily zadanou množinu bodů, hrany byly nakreslené jako úsečky, a přitom se nekřížily? Co když jsou navíc body v rovině i vrcholy grafu obarvené červeně a modře, a každý vrchol musí být nakreslen na bod své barvy? Co když navíc chceme, aby takové nakreslení existovalo pro každé kompatibilní obarvení zadaných bodů nebo vrcholů? O kolik víc bodů je potřeba, aby šel graf popsaným způsobem nakreslit? Místo obarvování bodů a vrcholů je také možné např. zorientovat hrany grafu a požadovat, aby při nakreslení všechny hrany směřovaly vzhůru.

Konkrétním problémem je např. případ cesty, jejíž vrcholy jsou střídavě obarveny červeně a modře. I když se omezíme na množiny bodů v konvexní poloze, není známé, jaký minimální počet bodů na nakreslení takové červeno-modré cesty stačí. Jádro tohoto problému tvoří kombinatorický problém hledání nejdelší společné podposloupnosti ve dvou posloupnostech nul a jedniček, kde se obě číslice vyskytují přibližně se stejnou frekvencí.

Euklidovská ramseyovská teorie

Euklidovská ramseyovská teorie se zabývá otázkami následujícího typu: je zadána konfigurace T sestávající z konečně mnoha bodů v rovině nebo v R^d; například množina vrcholů trojúhelníka nebo čtverce. Lze pak v každém obarvení prostoru R^n pomocí k barev najít jednobarevnou kopii T? Dají se zkoumat různé varianty problému, např. pro speciální typy obarvení, nebo hledat v různých barvách různé konfigurace.

Do této oblasti spadá i slavný Hadwigerův–Nelsonův problém o určení tzv. chromatického čísla roviny. Průlomového výsledku, vylepšujícího dolní odhad ze 4 na 5, se podařilo začátkem roku 2018, po více než 60 letech, docílit amatérskému matematikovi, který je jinak předním expertem na problém stárnutí. Následovalo založení polymath projektu zaměřeného na další vylepšování výsledku. Některé z navržených metod by mohly nalézt uplatnění i při řešení ostatních otázek.

Počítání Möbiovy funkce v kombinatorických částečných uspořádáních

Möbiova funkce pro částečně uspořádané množiny (posety) je užitečným nástrojem při počítání kombinatorických objektů. Z hodnot Möbiovy funkce pro uspořádání podmnožin inkluzí lze např. odvodit klasický princip inkluze a exkluze. Existuje také úzká souvislost Möbiovy funkce s Eulerovou charakteristikou, což je významný invariant geometrických a topologických objektů objevující se v různých oborech matematiky.

V kombinatorice byla Möbiova funkce počítána např. pro částečná uspořádání slov nebo permutací. Bylo by zajímavé pokusit se o podobné výsledky v dalších kombinatorických uspořádáních, např. grafů nebo některých jejich speciálních tříd.