|
|
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
|
|
|
Balanced and almost balanced group presentations from algorithmic viewpoint
Skotnica, Michael ; Tancer, Martin (vedoucí práce) ; Paták, Pavel (oponent)
V této práci se zabýváme algoritmickými vlastnostmi prezentací grup, což jsou konečné prezentace, kde počet generátorů a počet relací je stejný. Hlavní motivací je, že rozhodnutelnost některých problémů, např. zjistiť, zdali pre- zentace je prezentací triviální grupy (triviality problem), je pro balancované prezentace otevřená. Nejprve shrneme známé výsledky o rozhodovacích problémech pro ko- nečné prezentace a poté ukážeme dvě vlastnosti, které jsou nerozhodnutelné i pro balancované prezentace. Jedná se o vlastnosti "býti volnou grupou" a "mít prezentaci i na 12 generátorech". Dále ukážeme převody některých grafových problémů na triviality pro- blem. Např. rozhodování, zdali je graf souvislý, k-souvislý nebo souvislý ne- bipartitní. Také ukážeme převod rozhodování, zdali je graf se stejným po- čtem vrcholů a hran kružnice, na triviality problém pro balancované prezen- tace. Zamyslíme se také nad limity převodů na triviality problem pro balan- cované prezentace. Konkrétně ukážeme, že neexistuje balancovaná prezen- tace na dvou generátorech ⟨a, b|ap(m) bq(m) , ar(m) bs(m) ⟩, kde p(m), q(m), r(m), s(m) ∈ Z[m], která by popisovala triviální grupu právě tehdy, když m je liché. V poslední části této práce shrneme, jak prezentace grup souvisí s topo- logií. Doplněk k práci je také jednoduchý program, který...
|
|
|
Maximální množiny bodů na diskrétní torické mřížce bez trojic bodů ležících na stejné přímce
Skotnica, Michael ; Tancer, Martin (vedoucí práce) ; Kala, Vítězslav (oponent)
Označme τ(Tm×n) maximální počet bodů na diskrétní torické mřížce o roz- měrech m × n bez trojic bodů ležících na jedné přímce. Práce se zabývá otázkou, jaká je hodnota τ(Tm×n) pro různá m, n. Jedná se o variantu problému, který je znám jako no-three-in-line-problem. Nejdříve uvádíme některé poznatky z článků, které se touto otázkou již zabývaly. Některé z nich jsou zde zobecněny. Dále nově vylepšujeme horní a dolní odhady pro případy, které v předchozích článcích ne- byly vyřešeny, zejména pro případy, kdy rozměry mřížky jsou mocniny prvočísla. Nakonec definujeme posloupnost (τ(Tm×n))n∈N, o které dokážeme, že je periodická pro libovolné pevné m. 1
|
host ::
RSS.