|
|
Topological and geometrical combinatorics
Tancer, Martin ; Matoušek, Jiří (vedoucí práce) ; Pultr, Aleš (oponent) ; Kaiser, Tomáš (oponent) ; Meshulam, Roy (oponent)
1 Topological and Geometrical Combinatorics Martin Tancer Český abstrakt práce Cílem práce je prezentovat několik nových výsledků v oblasti topologických metod v kombinatorice. Výsledky lze zařadit do dvou hlavních oblastí. První oblast pokrývá průsečíkové struktury konvexních množin. V práci je ukázáno, že konečné projektivní roviny nemůžou být průsečíkovými strukturami konvexních množin pevné dimenze, což odpovídá na otázku Alona, Kalaie, Matouška a Meshu- lama. Dále je ukázáno, že d-kolabovatelnost (nutná podmínka na vlastnosti průsečíkových struktur konvexních množin v dimenzi d) je NP-těžká k rozpoznání pro d ≥ 4. A také je ukázáno, že d-kolabovatelnost není nutnou podmínkou na vlastnosti průsečíkových vzorů dobrých pokrytí, což vyvrací domněnku G. Wegnera z roku 1975. Do druhé oblasti spadá několik výsledků ohledně algoritmické obtížnosti rozpoz- návání simpliciálních komplexů vnořitelných do Rd . Konkrétněji, je algortmicky ne- rozhodnutelné, zda lze k-rozměrný simpliciální komplex po částech lineárně vnořit do Rd , pokud d ≥ 5 a k ∈ {d − 1, d}. Dále je tento problém NP-těžký, pokud d ≥ 4 a d ≥ k ≥ 2d−2 3 .
|
|
|
Lipschitzovská zobrazení diskrétních množin
Kaluža, Vojtěch ; Matoušek, Jiří (vedoucí práce) ; Šámal, Robert (oponent)
V této práci se zabýváme Feigeho otázkou existence konstantně lipschitzov- ské bijekce každé n2 -prvkové podmnožiny S ⊂ Z2 na pravidelnou mřížku n × n bodů v Z2 . Uvedeme řešení tohoto problému v případě, že body v S jsou uspořá- dány ve tvaru dlouhého obdélníku nebo ve tvaru čtverce bez vnitřku. Hlavní částí práce je rešerše článků Buraga a Kleinera [2] a McMullena [12], zabývajících se problémem existence bilipschitzovsky neekvivalentních separovaných sítí, který je podobný Feigeho problému. Dle těchto článků zkonstruujeme separovanou síť v R2 bilipschitzovsky neekvivalentní Z2 na základě konstrukce kladné omezené měřitelné funkce, která není Jakobiánem žádného bilipschitzovského homeomor- fismu skoro všude. Ukážeme McMullenovu konstrukci takové funkce a doplníme důkaz její správnosti. 1
|
|
|
Samodlážditelné simplexy
Safernová, Zuzana ; Matoušek, Jiří (vedoucí práce)
V předložené práci se zabýváme problémem k-samodlážditelnosti čtyřstěnů. Simplex S je k-samodlážditelný, pokud se dá rozdělit na k navzájem shodných simplexů (s disjunktními vnitřky), jež jsou navíc podobné původnímu simplexu S. V rovině jsou všechny k-samodlážditelné trojúhleníky charakterizovány, na druhou stranu jediné k-samodlážditelné simplexy v dimenzi d>=3 jsou známy pro hodnotu k=md , kde m>=2, tzv. Hillovy simplexy. V práci dokážeme, že v dimenzi 3 existují k-samodlážditelné čtyřstěny pouze pro k=m3 , což částečně potvrzuje Hertelovu domněnku, že jediné k-samodlážditelné čtyřstěny jsou Hillovy. Domníváme se, že k= md je nutná podmínka pro existenci k-samodlážditelných simplexů (d>3).
|
|
|
Erdos-Szekeres type theorems
Eliáš, Marek ; Matoušek, Jiří (vedoucí práce) ; Cibulka, Josef (oponent)
Nech P = (p1, p2, . . . , pN ) je postupnosť bodov v rovine, kde pi = (xi, yi) a x1 < x2 < · · · < xN . Slávna Erdős-Szekeresova veta z roku 1935 hovorí, že každá taká postupnosť P obsahuje monotónnu podpostupnosť S dĺžky√ N . Iná, podobne slávna veta z toho istého článku hovorí, že každá taká po- stupnosť P obsahuje konvexnú alebo konkávnu podpostupnosť dĺžky Ω(log N). Najprv definujeme (k + 1)-ticu K ⊆ P ako pozitívnu, keď leží na grafe funkcie s nezápornou k-tou deriváciou a podobne tiež negatívnu (k + 1)-ticu. Ďalej hovoríme, že S ⊆ P je monotónna k-teho rádu, keď jej (k + 1)-tice sú buďto všetky pozitívne alebo všetky negatívne. V tejto práci skúmame kvantitatívne odhady pre zodpovedajúce Ramseyovské funkcie. Dostávame Ω(log(k−1) N) ako dolný odhad. Taktiež uvádzame vylepšené odhady pre súvisiace problémy ako Order types a One-sided sets of hyperplanes. 1
|
|
|
Pokrývání sečen konvexní oblasti
Sterzik, Marek ; Matoušek, Jiří (oponent) ; Valtr, Pavel (vedoucí práce)
Pro danou konvexní oblast v rovině se snažíme nalézt co možná nejkratší množinu (navíc volitelně splňující předepsané vlastnosti), která protíná všechny přímky, které protínají danou oblast. Velikost pokrývacích množin měříme Hausdorffovou 1-dimenzionílní mírou 1. V první kapitole je podán úvod do problému. Druhá kapitola se zabívá problémem horního odhadu velikosti minimální pokrývacé množiny. Třetí kapitola se zabývá existencí a vlastnostmi nejmenšího pokrytí. Ve čtvrté kapitole je rozebírán problém dolního odhadu pro velikost pokrytí. V páté kapitole jsou studovány další souvislosti a zobecnění problému.
|
|
|
Perfektní dláždění simplexů
Safernová, Zuzana ; Cibulka, Josef (oponent) ; Matoušek, Jiří (vedoucí práce)
V předložené práci se zabýváme problémem k-samodlážditelnosti d-dimenzionálních simplexů. Simplex S je k-samodlážditelný, pokud se dá rozdělit na k navzájem shodných simplexů (s disjunktními vnitřky), jež jsou navíc podobné původnímu simplexu S. Jediné dosud známé k-samodlážditelné simplexy v dimenzi d 3 jsou pro hodnotu k = md, kde m 2. V práci nastiňujeme Matouškův důkaz neexistence 2-samodlážditelných simplexů pro d 3, který poté opravíme. Uvádíme několik vlastních geometrických postřehů pro k = 2. Na závěr dokazujeme, že v prostoru dimenze 3 neexistuje 3-samodlážditelný simplex.
|
|
| |
|
| |
|
| |
|
| |
host ::
RSS.