|
|
Combinatorics, group theory, computational complexity & topology
Skotnica, Michael ; Tancer, Martin (vedoucí práce) ; Hachimori, Masahiro (oponent) ; Bauer, Ulrich (oponent)
V této práci prezentujeme nové výsledky týkající se kombinatorických vlastností topo- logických prostorů zadaných pomocí abstraktních simpliciálních komplexů, jejich vztahy a výpočetní složitost. Nejprve zobecníme Hachimoriho výsledek ohledně vztahů mezi shellovatelností a ko- labovatelností, což jsou důležité kombinatorické vlastnosti simpliciálních komplexů. Dále se zabýváme výpočetní složitostí PL geometrické kategorie dvourozměrných mno- hostěnů definované Borghinim. To je kombinatorický pojem, který zároveň dává přirozený horní odhad pro Lusternik-Schnirelmannovu kategorii. Pro dvourozměrné mnohostěny může být tato kategorie rovna 1, 2, nebo 3. Zatímco je snadné rozhodnout, zda je PL geometrická kategorie dvourozměrného mnohostěnu rovna 1, ukážeme, že rozhodnout, zda je tato kategorie nejvýše 2, je NP-těžké. Nakonec ukážeme, že počítání ranku vyšších homotopických grup 1-souvislého topolo- gického prostoru je #W[2]-těžké, pomocí problému zvaného VEST definovaného Anickem jakožto pomocného problému. Prezentujeme také výsledky pro rozhodovací verzi VEST a její varianty. U většiny z nich dokážeme W[1]- nebo W[2]-těžkost. 1
|
host ::
RSS.