Combinatorics, group theory, computational complexity & topology

Abstract

In this thesis, we present new results related to combinatorial properties of topo- logical spaces given by abstract simplicial complexes, their relations and computational complexity. First, we generalize a result of Hachimori on relations between shellability and col- lapsibility which are important combinatorial properties of simplicial complexes. Next, we study the computational complexity of the PL geometric category of 2- dimensional polyhedra introduced by Borghini which is a combinatorial notion providing a natural upper bound for the Lusternik-Schnirelmann category. For 2-dimensional poly- hedra it can be equal to 1, 2 or 3. While it is easy to decide whether the PL geometric category of a 2-dimensional polyhedron is equal 1, we show that it is NP-hard to decide whether this category is at most 2. Finally, we show that computing the rank of higher homotopy groups of a simply connected topological space is #W[2]-hard using a problem called VEST, given by Anick, as an intermediate problem. We also establish results for the decision version of VEST and for its variants as self-contained problems. For most of them we show W[1]- or W[2]-hardness. 1

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