|
|
Využití gadgetové konstrukce pro strukturální konvergenci
Hons, Tomáš ; Hartman, David (vedoucí práce) ; Ossona de Mendez, Patrice (oponent) ; Pultr, Aleš (oponent)
Strukturální konvergence je framework konvergence grafů a relačních struktur zalo- žený na počítání pravděpodobnosti splnění formulí predikátové logiky. V práci navrhu- jeme gadgetovou konstrukci, která nalezla uplatnění v mnoha oblastech matematiky, jako metodu výroby konvergentních posloupností relačních struktur. Pro elementární a lokální konvergenci studujeme chování posloupnosti struktur vytvořených gadgetovou konstrukcí z konvergentních poslouností základních struktur a gadgetů. Ukazujeme, že elementární konvergence je vždy zachována, zatímco v případě lokální konvergence je potřeba dalších předpokladů, což ilustrujeme řadou příkladů. Dokazujeme několik postačujících podmínek pro zachování lokální konvergence. Jedna z nich říká, že posloupnost vytvořených struk- tur je lokálně konvergentní, pokud v posloupnosti základních struktur byly nahrazované hrany husté. Představené postačující podmínky částečně komplementujeme inverzními větami. 1
|
|
| |
|
|
Computational Homotopy Theory
Krčál, Marek ; Matoušek, Jiří (vedoucí práce) ; Pultr, Aleš (oponent) ; Romero Ibáñez, Ana (oponent)
dizertační práce "Výpočetní homotopická teorie": Tato práce studuje výpočetní složitost několika základních problémů algebraické topologie, které mají souvislost s otázkami v kombinatorice a výpočetní ge- ometrií. Problém rozšiřitelnosti je zadán topologickými prostory X, Y, podpros- torem A ⊆ X a (spojitým) zobrazením f : A → Y . A otázka je, zda f může být rozšířeno na celý prostor X. Předpokládáme, že X, Y a A jsou zadány jako konečné simpliciální komplexy a f jako simpliciální zobrazení. Výpočetní složitost budeme zkoumat za předpokladu, že Y je d-souvislý pro nějaké d ≥ 1. Jinak je známo, že z teorie grup plyne, že problém rozšiřitel- nosti je nerozhodnutelný. Zde dokážeme, že rozšiřitelnost je i při tomto předpokladu nerozhod- nutelná, pokud dim X dosáhne hodnoty 2d+2. Na druhou stranu pro každou pevnou hodnotu dim X ≤ 2d + 1 nalezneme algoritmus, který řeší problém rozšiřitelnosti v polynomiálním čase. Ukážeme, že složitost výpočtu množiny všech homotopických tříd zo- brazení X → Y má podobnou charakteristiku. Dále uvážíme problém homotopických grup πk(Y ) pro 1-souvislý prostor Y a dimenzi k ≥ 2. První algoritmus na jejich výpočet našel Brown v roce 1957. My ukážeme, že πk(Y ) lze vypočíst v polynomiálním čase pro každou pevnou dimenzi k ≥ 2. Na druhou stranu dokážeme, že výpočet πk(Y ) je...
|
|
|
Combinatorial Properties of Finite Models
Hubička, Jan ; Nešetřil, Jaroslav (vedoucí práce) ; Pultr, Aleš (oponent) ; Cameron, P. (oponent)
V této práci se věnujeme univerzáním strukturám pro vnoření i homomorfismy a sjednocujeme výsledky týkající se obou těchto pojmů. Ukážeme, že mnohé z univerzálních a ultrahomogenních struktur jsou reprezentovatelné pomocí jednoduchých konečných technik. O takových strukturách říkáme, že mají konečnou prezentaci. Na základě klasické reprezentace náhodného grafu (R. Rado) hledáme konečné prezentace pro známé ultrahomogenní struktury. Podle klasifikačního programu najdeme prezentace všech ultrahomogenních neorientovaných grafů, turnajů a částečných uspořádání. Ukážeme také prezentaci racionálního Urysohnova prostoru a některých orientovaných grafů. Věnujeme se také známým strukturám, které lze považovat za konečné prezentace. Uvádíme přehled struktur, které popisují částečná uspořádání a u nichž můžeme dokázat jejich univerzalitu (například uspořádání množin slov, geometrických objektů, polynomů, či homomorfismové uspořádání struktur). Ukážeme nový kombinatorický důkaz existence univerzálních struktur pro třídy struktur definovaných pomocí zakázaných homomorfismů. Z tohoto důkazu plyne nová konstrukce homomorfismových dualit a souvislost s Urysohnovým prostorem.
|
|
|
Specialni bezbodove prostory
Novák, Jan ; Pultr, Aleš (vedoucí práce) ; Klazar, Martin (oponent)
1 Tato práce se zabývá oddělovacími axiomy v bezbodové topologii. Zavádíme pojem slabé inkluze, což je relace, která je slabší než relace ≤. Slabé inkluze poskytují formalizmus, kterým lze studovat standardní separační axiomy jako subfitness, fit- ness nebo regularitu. Důkazy provedené pomocí slabých inkluzí často přináší nový pohled na vlastnosti daného axiomu. Práce se soustředí zejména na výsledky ohledně subfitness axiomu. Studujeme zde sublokál, který vznikne jako průnik všech codense sublokálů daného lokálu. Dokazu- jeme, že tento sublokál nemusí být nutně subfit. Pro spaciální framy nemusí být spaciální.
|
|
|
Some point-free aspects of connectedness
Jakl, Tomáš ; Pultr, Aleš (vedoucí práce)
V této práci ukážeme Stoneovu větu o reprezentaci, která je také známa pod názvem Stoneova dualita, v bezbodovém kontextu. Předvedený důkaz je bezvýběrový, a protože se nemusíme starat o jednotlivé body, je mnohem jednodušší než původní důkaz. Ukážeme, že pro každý nekonečný kardinál κ jsou protějšky κ-úplných Booleových algebrer κ-bazicky nesouvislé Stoneovy framy. Také předvedeme přesnou charakterizaci morfismů, které jsou v ko- responenci s κ-úplnými Booleovskými homomorfismy. Ikdyž Booleanizace není obecně funktoriální, v části duality extremálně nesouvislých Stoneových framů funktoriální je a dokonce tvoří ekvivalenci kategorií. Na konci práce se zaměříme na De Morganovské (respektive extremálně nesouvislé) framy a ukážeme jejich novou charakterizaci pomocí jejich superhustých sublokálů. Naproti tomu jsou metrizovatelné framy, které nemají žádný netriviální su- perhustý sublokál, a proto nikdy není jejich netriviální Čech-Stoneova kom- paktifikace metrizovatelná. 1
|
|
|
Semigroup-valued metric spaces
Konečný, Matěj ; Hubička, Jan (vedoucí práce) ; Pultr, Aleš (oponent)
Strukturální Ramseyova teorie je obor na rozmezí kombinatoriky a teorie modelů s hlubokými souvislostmi s dynamickými systémy. Ramseyovskost většiny známých ramseyovských tříd v konečném binárním symetrickém relačním jazyce se dá dokázat s využitím nějaké varianty tzv. shortest path completion (například Sauerovy S-metrické prostory, Conantovy zobecněné metrické prostory, Braunfel- dovy Λ-ultrametrické prostory či Cherlinovy metricky homogenní grafy). V této práci zkoumáme limity shortest path completion. Nabízíme abstrakci - met- rické prostory se vzdálenostmi z pologrupy - pro všechny zmíněné ramseyovské třídy a studujeme ramseyovské expanze a EPPA (extension property for partial automorphisms) této abstrakce. Na tyto výsledky lze také nahlížet jako na důkaz toho, že samotná otázka, které neúplné struktury mají zúplnění v nějaké amal- gamační třídě, je zajímavá a důležitá. Naše výsledky mají i další aplikace (jako například stationary independence relations). Jako důsledek našich obecných vět znovu dokážeme výsledky Hubičky a Nešetřila o Sauerových S-metrických prostorech, výsledky Hubičky, Nešetřila a autora o Conantových generlizovaných metrických prostorech, Braunfeldovy výsledky o Λ-...
|
|
|
d-Frames as algebraic duals of bitopological spaces
Jakl, Tomáš ; Pultr, Aleš (vedoucí práce) ; Picado, Jorge (oponent) ; Cintula, Petr (oponent)
Achim Jung a Drew Moshier vyvinuli dualitu pro bitopologické prostory podobnou Stoneově dualitě čímž, mimo jiné, získali praktický nástroj k vyřešení konkrétího problému v teorii stabilně kompaktních prostorů. Tímto také objevili že tato dualita mezi bitopologickými prostory a jejich algebraickými protějšky, zvanými d-framy, zahrnuje i další známé duality. Cílem této práce je vzít práci Junga a Moshiera a doplnit některé z chybějících aspektů je- jich teorie. Konkrétně, prozkoumáme základní kategorické vlastnosti d-framů, vyvineme takovou Vietorisovu konstrukci pro d-framy, že zobecníme příslušné Vietorisovy konstrukce v dalších kat- egoriích, a prozkoumáme spojitosti mezi bitopologickými prostory a parakonzistentní logikou a poté vyvineme vhodnou (geometrickou) logiku pro d-framy.
|
|
|
Some point-free aspects of connectedness
Jakl, Tomáš ; Pultr, Aleš (vedoucí práce)
V této práci ukážeme Stoneovu větu o reprezentaci, která je také známa pod názvem Stoneova dualita, v bezbodovém kontextu. Předvedený důkaz je bezvýběrový, a protože se nemusíme starat o jednotlivé body, je mnohem jednodušší než původní důkaz. Ukážeme, že pro každý nekonečný kardinál κ jsou protějšky κ-úplných Booleových algebrer κ-bazicky nesouvislé Stoneovy framy. Také předvedeme přesnou charakterizaci morfismů, které jsou v ko- responenci s κ-úplnými Booleovskými homomorfismy. Ikdyž Booleanizace není obecně funktoriální, v části duality extremálně nesouvislých Stoneových framů funktoriální je a dokonce tvoří ekvivalenci kategorií. Na konci práce se zaměříme na De Morganovské (respektive extremálně nesouvislé) framy a ukážeme jejich novou charakterizaci pomocí jejich superhustých sublokálů. Naproti tomu jsou metrizovatelné framy, které nemají žádný netriviální su- perhustý sublokál, a proto nikdy není jejich netriviální Čech-Stoneova kom- paktifikace metrizovatelná. 1
|
|
|
Extension property of structures
Hartman, David ; Nešetřil, Jaroslav (vedoucí práce) ; Pultr, Aleš (oponent) ; Woodrow, Robert (oponent)
Tato práce rozebírá vlastnost relačních struktur, která implikuje jejich vysokou symetričnost. Strukturu nazveme homogenní pokud lze libovolné lokální zobrazení rozšířit na zobrazení nad celou strukturou a to pro li- bovolnou volbu konečné vzorové množiny. Typ lokálního a globálního zo- brazení potom určuje různé typy homogenity. Prominentní místo má ul- trahomogenita, která označuje strukturu, pro kterou libovolný lokální iso- morfismus nad konečnými podstrukturami je rozšiřitelný na automorfismus. Na rozdíl od grafů je klasifikace ultrahomogenních relačních struktur stále otevřeným problémem. Cílem práce je charakterizovat "vzdálenost" od ho- mogenity a to dvěma způsoby. Nejprve zvyšuje "složitost struktury" přidáváním relací a sleduje změny klasifikace homogenních struktur. To vede k několika klasifikacím homomorfně-homogenních L-obarvitelných grafů pro různé L, kde L-obarvitelný graf je graf, kde vrcholy a hrany dostávají množiny barev z částečně uspořádané množiny L. Na to navazují výsledky a diskuze nad hier- archií tříd definovanou skrze různé typy homogenity s ohledem na koincidenci jednotlivých tříd. Druhý pohled zkoumá pro dané struktury jak minimálně rozšířit jejich jazyk, abychom dosáhli homogenity....
|
host ::
RSS.