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