|
|
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
|
|
|
Algebraic Tools in Combinatorial Geometry and Topology
Bulavka, Denys ; Tancer, Martin (vedoucí práce) ; Benedetti, Bruno (oponent) ; Holmsen, Andreas (oponent)
V této práci se zabýváme kombinatorickými problémy optikou Grassmanovy alge- bry. Tato algebra je přirozenou matematickou strukturou pro modelování množinových systémů i simpliciálních komplexů. Umožňuje navíc převést operace z kombinatorických struktur do Grassmanovy algebry. Například operace jako množinový průnik nebo stan- dardní hraniční operátor z topologie. To nám často umožňují převést kombinatorický problém na problém týkající se dimenze určitého vektorového prostoru, což se může uká- zat jako jednodušší přístup, protože poté můžeme zkoumat dimenzi vektorového prostoru pomocí lineárních zobrazení. Takový přístup uplatňujeme i v této práci. V první části zkoumáme problém slabé saturace, který zavedl Bollobás v 60. letech. Jedná se o následující problém. Pro zadaný "hostitelský" graf F a "vzorový" graf H je potřeba určit minimální počet "nakažených" hran grafu F, se kterými je třeba začít, aby se infekce rozšířila na celý hostitelský graf F podle vzorového grafu H. Konkrétně nás zajímá případ, kdy hostitelské i vzorové grafy jsou úplné uniformní multipartitní hypergrafy. Dále se zabýváme zobecněním Hellyho věty, která se týká průsečíkových struktur kon- vexních množin. Konkrétně se ptáme na následující otázku. Je-li zadán konečný systém konvexních množin v Rd rozdělených do d+1 tříd barev tak, že...
|
|
|
Věty Hellyho typu a zlomkového Hellyho typu
Tancer, Martin ; Matoušek, Jiří (vedoucí práce) ; Kaiser, Tomáš (oponent)
Simpliciální komplex je d-reprezentovatelný, pokud je nervem souboru konvexních množin v Rd. Klasická Hellyho věta říká, že pokud d-reprezentovatelný komplex obsahuje všechny možné stěny dimenze d, potom se už nutně jedná o plný simplex. Hellyho věta má mnoho zobecnění; uvedeme stručný přehled některých z nich. Třída d-reprezentovatelných komplexů je podtřídou d-kolabovatelných komplexů, a ta je podtřídou d-Lerayových komplexů. Pro d 1 uvedeme příklad komplexů, které jsou 2d-Lerayovy, ale nejsou (3d 1)-kolabovatelné. Pro d 2 uvedeme příklad komplexů, které jsou d-Lerayovy, ale nejsou (2d 2)-reprezentovateln'e. Navíc pro d 3 dokážeme, že naposledy zmiňované komplexy jsou také d-kolabovatelné. Na závěr reprezentujeme jednoduchý důkaz kombinatorické Alexandrovy duality. Ta je totiž užitečným topologickým nástrojem pro kombinatoriku, například pro topologické verze Hellyho věty.
|
|
|
Metric and analytic methods
Kaluža, Vojtěch ; Tancer, Martin (vedoucí práce) ; Kleiner, Bruce (oponent) ; Fulek, Radoslav (oponent)
Předložená práce se zabývá dvěma nezávislými problémy. V první části uka- zujeme, že nelze libovolnou n2 -prvkovou množinu zobrazit prostě na pravidelnou mřížku n × n bodů v Z2 pouze s použitím zobrazení, která mohou zvětšovat vzdálenosti faktorem omezeným shora nezávisle na n. Tento výsledek dává zá- pornou odpověď na otázku Uriela Feigeho z roku 2002. Náš přístup vychází z práce Buraga a Kleinera a McMullena o bilipschitzovsky nerealizovatelných hus- totách a bilipschitzovsky neekvivalentních separovaných sítích z roku 1998. Popí- šeme postup, který zakóduje danou kladnou, měřitelnou funkci do posloupnosti diskrétních množin. Pak ukážeme, že pokud je tento postup aplikován na typic- kou spojitou funkci definovanou na jednotkovém čtverci, je získaná posloupnost diskrétních množin protipříkladem na Feigeho otázku. Dále také podáváme nový důkaz výsledku Bonka a Kleinera z roku 2002 o bilipschitzovské dekompozici lipschitzovsky regulárních zobrazení. Ve druhé části představíme konstruktivní důkaz silné Hanani-Tutteho věty pro projektivní rovinu. Oproti předchozímu důkazu Pelsmajera, Schaefera a Stasi z roku 2009 náš postup nepoužívá charakterizaci vnořitelnosti do projektivní roviny pomocí zakázaných minorů. 1
|
|
|
The Helly numbers of systems of sets with bounded algebraic and topological complexity
Sosnovec, Jakub ; Tancer, Martin (vedoucí práce) ; Patáková, Zuzana (oponent)
Maehara dokázal, že je-li F systém alespoň d+3 sfér v Rd takový, že každých d+1 sfér z F má neprázdný průnik, pak celý systém F má neprázdný průnik. V této práci rozšiřujeme jeho výsledek Hellyho typu ve dvou směrech. Nejprve ukážeme platnost analogické věty pro systémy pseudosfér, tedy systémy množin splňující, že průnik každého neprázdného podsystému je homeomorfní sféře nějaké dimenze nebo je prázdný. Dále využijeme toho, že sféru v Rd lze vyjádřit jako nulovou množinu reálného polynomu. Je-li P množina polynomů, pak Hellyho číslo systému nulových množin polynomů z P je omezeno dimenzí vektorového prostoru generovaného P. Pro systémy sfér ovšem Maeharův výsledek dává silnější odhad. Ukážeme některé obecné postačující podmínky pro lepší odhad Hellyho čísel v tomto kontextu. Powered by TCPDF (www.tcpdf.org)
|
|
|
Persistentní homologie a neuronové sítě
Černý, Marek ; Šámal, Robert (vedoucí práce) ; Tancer, Martin (oponent)
Hluboké učení prakticky vyřešilo nejrůznější problémy počítačového vidění v průběhu poslední dekády. V práci používáme grupy persistentní homologie z výpočetní topolo- gie k analýze prostorů vnitřních representací příznaků v konvolučních neuronových sítích (CNN). Pozorovali jsme souvislost mezi souhrny homologických persistentních grup rozhodovací hranice a chybou tréninku sítě ResNet-18 v průběhu fenoménu hlubokého dvojitého pok- lesu. Navíc jsme se zaměřili na zvlaštní případ souhrnu, který poukazuje na analogii dvojitého sestupu ve směru epoch, což by mohlo vést lepšímu pochopení vnitřních repre- sentací v průběhu kriticky parametrizovaného režimu sítě. V hlavní části navrhujeme a porovnaváme několik přístupů k procesingu samotných modelů CNN sítí pomocí persistentní homologie. Naše nejlepší metoda zvaná Derivo- vatelný persistentní estimátor kvality (DPAE) dosahuje vysoké přesnosti v predikci kval- ity CNN sítí (tj. R2 skore téměř 0.99). DPAE je topologicky optimalizovatelná end-to-end architektura zahrnující derivovatelný výpočet persistence. Co více, DPAE metoda předčí i původní metodu využívající klasického strojového učení, které byla vytvořena přímo pro dataset, který používáme k testování. Veřejně dáváme k dispozici zdrojový kód jak metody DPAE tak ostatních prezentovaných experimentů. 1
|
|
|
Vertex-transitive Supergraphs
Madaj, Pavel ; Tancer, Martin (vedoucí práce) ; Hušek, Radek (oponent)
V tejto práci skúmame spôsoby ako rozšírit' grafy na nadgrafy, ktoré sú vrcholovo tranzitívne. Predstavíme systém šablón pre konštrukciu týchto nadgrafov. Tento systém využujeme na konštrukciu vrcholovo tranzitívnych nadgrafov exponenciálnej vel'kosti pre všeobecné grafy a nadgrafov kvadratickej vel'kosti pre bipartitné grafy. Pre všeobecné grafy dokážeme kvadratickú dolnú medz. Načrtneme aj prístup, ktorý by mohol viest' k preklenutiu medzery v časovej zložitosti medzi problémom grafového izomorfizmu a problémom rozpoznávania vrcholovo tranzitívnych grafov. 1
|
|
|
Number of faces in a random embedding of a complete graph
Ryzák, David ; Šámal, Robert (vedoucí práce) ; Tancer, Martin (oponent)
Každý konečný graf může být nakreslen na plochu s dostatečně velkým rodem plochy. Takové nakreslení lze popsat (až na homeomorfismus) pomocí lokalních rotací u vrcholů, tzn. cyklických pořadí hran incidentních s jedním z vrcholů. V náhodné nakreslení jsou lokální rotace vybírány náhodně. Rozdělení rodu plochy je v takovém případě dobře známo pro různé skupiny grafů. Avšak my se zaměřujeme na rozdělení počtu stěn různých délek. Omezili jsme se pouze na úplné grafy. Hlavním výsledkem je, že počet stěn pevné délky v náhodném nakreslení konverguje v distribuci k Poissonovu rozdělení. Už dříve jsme vědeli o vztahu mezi cykly v náhodné permutaci a stěnami v náhodném nakreslení. Zjistili jsme však, že konvergují v distribuci ke stejnému rozdělení. Také jsme ale mezi nimi našli rozdíly. Vztahy jsou pak popsány pomocí výpočtů různých momentů a pomocí simulací náhodného nakreslení a náhodné permutace. 1
|
|
|
Věty Hellyho typu a zlomkového Hellyho typu
Tancer, Martin
Simpliciální komplex je d-reprezentovatelný, pokud je nervem souboru konvexních množin v Rd. Klasická Hellyho věta říká, že pokud d-reprezentovatelný komplex obsahuje všechny možné stěny dimenze d, potom se už nutně jedná o plný simplex. Hellyho věta má mnoho zobecnění; uvedeme stručný přehled některých z nich. Třída d-reprezentovatelných komplexů je podtřídou d-kolabovatelných komplexů, a ta je podtřídou d-Lerayových komplexů. Pro d 1 uvedeme příklad komplexů, které jsou 2d-Lerayovy, ale nejsou (3d 1)-kolabovatelné. Pro d 2 uvedeme příklad komplexů, které jsou d-Lerayovy, ale nejsou (2d 2)-reprezentovatelné. Navíc pro d 3 dokážeme, že naposledy zmiňované komplexy jsou také d-kolabovatelné. Na závěr prezentujeme jednoduchý důkaz kombinatorické Alexandrovy duality. Ta je totiž užitečným topologickým nástrojem pro kombinatoriku, například pro topologické verze Hellyho věty.
|
|
|
Metric and analytic methods
Kaluža, Vojtěch ; Tancer, Martin (vedoucí práce) ; Kleiner, Bruce (oponent) ; Fulek, Radoslav (oponent)
Předložená práce se zabývá dvěma nezávislými problémy. V první části uka- zujeme, že nelze libovolnou n2 -prvkovou množinu zobrazit prostě na pravidelnou mřížku n × n bodů v Z2 pouze s použitím zobrazení, která mohou zvětšovat vzdálenosti faktorem omezeným shora nezávisle na n. Tento výsledek dává zá- pornou odpověď na otázku Uriela Feigeho z roku 2002. Náš přístup vychází z práce Buraga a Kleinera a McMullena o bilipschitzovsky nerealizovatelných hus- totách a bilipschitzovsky neekvivalentních separovaných sítích z roku 1998. Popí- šeme postup, který zakóduje danou kladnou, měřitelnou funkci do posloupnosti diskrétních množin. Pak ukážeme, že pokud je tento postup aplikován na typic- kou spojitou funkci definovanou na jednotkovém čtverci, je získaná posloupnost diskrétních množin protipříkladem na Feigeho otázku. Dále také podáváme nový důkaz výsledku Bonka a Kleinera z roku 2002 o bilipschitzovské dekompozici lipschitzovsky regulárních zobrazení. Ve druhé části představíme konstruktivní důkaz silné Hanani-Tutteho věty pro projektivní rovinu. Oproti předchozímu důkazu Pelsmajera, Schaefera a Stasi z roku 2009 náš postup nepoužívá charakterizaci vnořitelnosti do projektivní roviny pomocí zakázaných minorů. 1
|
host ::
RSS.