Combinatorics, group theory, computational complexity & topology
Kombinatorika, teorie grup, výpočetní složitost a topologie
dissertation thesis (DEFENDED)
![Document thumbnail](/bitstream/handle/20.500.11956/188902/thumbnail.png?sequence=8&isAllowed=y)
View/ Open
Permanent link
http://hdl.handle.net/20.500.11956/188902Identifiers
Study Information System: 201521
Collections
- Kvalifikační práce [10925]
Author
Advisor
Referee
Hachimori, Masahiro
Bauer, Ulrich
Faculty / Institute
Faculty of Mathematics and Physics
Discipline
Computer Science - Theory of Computing, Discrete Models and Optimization
Department
Department of Applied Mathematics
Date of defense
25. 3. 2024
Publisher
Univerzita Karlova, Matematicko-fyzikální fakultaLanguage
English
Grade
Pass
Keywords (Czech)
simpliciální komplex|kolabovatelnost|shellovatelnost|výpočetní složitost|homotopické grupyKeywords (English)
simplicial complex|collapsibility|shellability|computational complexity|homotopy groupsV 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
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