|
|
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ý...
|
host ::
RSS.