Navržená témata jsou zatím jenom dvě. V případě zájmu se také můžeme zkusit domluvit na jiném tématu v některé z oblastí: kombinatorická geometrie, topologické metody v kombinatorice, kombinatorika, algoritmická složitost v topologii či geometrii, teorie grafů. Některá témata jsou už zamluvená. Může mít ale význam se podívat i na ta zamluvená. V případě zájmu mohu zkusit najít/vymyslet podobné téma.
Oblast: kombinatorická geometrie s mírnou příměsí topologie a teorie grafů
Vhodné jako: diplomová práce, popř. bakalářská práce (více pojatá jako rešerše)
2-rozměrný simpliciální komplex lze získat tak, že uvážíme nějaký graf a do některých (grafově teoretických) trojúhelníků nalepíme geometrický trojúhelník. Několik příkladů je k vidění na obrázcích níže. (U prvních dvou obrázků jsme nenalepili žádný trojúhelník, v takovém případě máme pouze původní graf, na který lze nahlížet jako na 1-rozměrný simpliciální komplex.)
Věta Halina a Junga (z r. 1964) je analogie Kuratowského věty pro rovinné grafy. Říká, že 2-rozměrný simpliciální komplex lze vnořit (nakreslit) do roviny, právě když neobsahuje určitý typ podrozdělění žádného z komplexů na obrázku níže.
Cílem práce by bylo nejprve pochopit důkaz této věty a vysvětlit ho v modernější terminologii. Následně by bylo cílem pokusit se tuto větu rozšířit na nějaké další plochy, nejsnáze asi na projektivní rovinu. Není ani nutné najít všechny zakázané podkomplexy, spíše by bylo zajímavé zjistit, jestli jich je konečný počet, popř. najít co nejvíce z těchto zakázaných podkomplexů.
Oblast: Grafy na plochách
Vhodné jako: bakalářská práce (či méně odvážná diplomová práce)
Kuratowského věta říká, že graf je rovinný, pokud neobsahuje dělení grafů $K_5$ nebo $K_{3,3}$. Tato věta má také modifikaci známou jako Wagnerova věta: graf je rovinný pokud neobsahuje $K_5$ nebo $K_{3,3}$ jako minor. Těmto grafům se říká zakázané minory.
Zobecnění rovinnosti grafů odpovídá otázka zda daný graf lze nakreslit (bez křížení hran) na zadanou 2-rozměrnou plochu. (Rovinnost odpovídá situaci kdy plocha je rovina či sféra.) I pro další plochy je známo, že existuje konečný počet zakázaných minorů, které charakterizují grafy nakreslitelné na dané ploše. Pro projektivní rovinu je těch minorů 35, pro vyšší plochy přesný seznam není ani pořádně známý.
Nicméně lze navrhnout pozměněné definice minorů, se kterými bude počet minorů menší. Můžeme aplikovat tzv. $Y\Delta$-výměny a $H\infty$-výměny (viz obrázek níže). Když graf před výměnou lze vnořit do plochy tak i graf po příslušné výměně lze také vnořit do dané plochy. Řekneme, že graf $G$ je speciální minor grafu $H$, pokud lze $G$ z $H$ dostat operacemi: ubírání hran a vrcholů, kontrakce hran, $Y\Delta$-výměna nebo $H\infty$-výměna. Potom počet zakázaných speciálních minorů může být menší (a ve skutečnosti je menší!) než počet zakázaných (standardních) minorů. Například pro rovinu, si rozmyslete, že graf $K_5$ lze získat z $K_{3,3}$ pomocí $H\infty$-výměny. Tedy $K_5$ je jediný minimální zakázaný speciální minor pro rovinnost.
Cílem práce by bylo zkoumat speciální minory především pro projektivní rovinu, popř. různé varianty. Součástí řešení práce by mohl být program, který speciální minory pro projektivní rovinu najde (stačí vhodně prozkoumat speciální minory). Část práce v tomto smyslu byla udělána Archdeaconem, ale možná je nenávratně ztracena (odkaz na zastaralou/neexistující internetovou stránku). Součástí práce by také bylo tedy prověřit zda některá tvrzení předkládaná Archdeaconem k uvěření jsou skutečně pravdivá.
Oblast: kombinatorická geometrie s mírnou příměsí topologie
Vhodné jako: diplomová práce či odvážnější bakalářská práce
Attali a Lieutier ve svém článku "Geometry driven collapses for converting a Čech complex into a triangulation of a nicely triangulable shape" zjistili, že potřebují (dostatečně) pěkné triangulace určitých podmnožin $\mathbb R^d$ pro svůj výsledek z oblasti rekonstrunce tvarů prostorů (shape reconstruction). Sami zjistili, že 2-rozměrnou sféru, torus a afinní podprostory $\mathbb R^d$ lze tímto způsobem triangulovat. Další přirozený krok by bylo zjistit, zda tímto způsobem lze triangulovat další 2-rozměrné plochy, když se vhodně vnoří do $\mathbb R^3$.
Přibližně řečeno, triangulace (2-rozměrné) triangulovatelné množiny $A \subseteq \mathbb R^3$ je dostatečně pěkná, pokud rozumně malá konvexní okolí vrcholů protínají pouze trojúhelníky obsahující daný vrchol. Přesná definice vyžaduje zavedení několika pojmů a rád ji vysvětlím na osobní schůzce.
Cílem práce by tedy bylo zjistit zda je možné 2-rozměrné plochy dostatečně pěkně triangulovat, a pokud ano, jak to konkrétně udělat. Dále, v případě zájmu, je i možnost pokusit se najít nějaké dostatečně pěkné triangulace některých vícerozměrných ploch (ty se nazývají variety) v $\mathbb R^d$.
Stav: nezamluvené
Oblast: kombinatorika (s možná mírným přesahem do teorie čísel)
Vhodné jako: bakalářská práce
Diskrétní torickou mřížkou $m \times n$ dostaneme tak, že uvážíme kartézský součin množin $\{0, \dots, m-1\} \times \{0, \dots, n-1\}$ jako podmnožinu $\mathbb Z^2$. Uvažujeme přímky na této mřížce následujícím způsobem. Zvolíme libovolnou přímku $p$ v $\mathbb Z^2$ a promítneme ji na přímku $p'$ na mřížce tak, že kdykoliv bod $(x,y)$ patří do $p$, pak bod $(x \pmod m, y \pmod n)$ přidáme do $p'$. Torickou mřížku si také můžeme například představovat tak, že ji vystřihneme z obdélníkového papíru $[-1/2, m - 1/2] \times [-1/2, n - 1/2]$ a identifikujeme okraje.Přímka na diskrétní torické mřížce $6 \times 4$ může tedy vypadat jako na obrázku níže.
Stav: zamluvené Michaelem Skotnicou
Oblast: komibnatorická geometrie
Vhodné jako: bakalářská či diplomová práce
Hellyho věta v $\mathbb R^d$ říká, že kdykoliv máme soubor $\mathcal F$ alespoň $d+1$ konvexních množin v $\mathbb R^d$ takových, že každých $d+1$ množin z $\mathcal F$ má neprázdný průnik, potom celý soubor $\mathcal F$ má neprázdný průnik. Hellyho věta má různá zobecnění/modifikace, pokud nahradíme konvexní množiny nějakými obecnějšími podmnožinami.
Jedna možná modifikace je následující: Pro každé přirozené $d$ existuje $f(d)$ s následující vlastností. Pro libovolný soubor $\mathcal F$ alespoň $f(d)$ sfér různé dimenze uvnitř $\mathbb R^d$ takový, že každých $f(d)$ množin z $\mathcal F$ má neprázdný průnik, platí, že celý soubor $\mathcal F$ má neprázdný průnik. Tento výsledek plyne z obecného topologického výsledku Goaoca, Patáka, Safernové, Tancera a Wagnera; nicméně obecný topologický postup dává velmi špatný odhad na optimální $f(d)$.
Cílem práce by bylo najít dobrý kvantitativní odhad na $f(d)$. Popř. identifikovat další situace, kdy topologický přístup dává špatný odhad, který je možné geometrickými úvahami vylepšit.
Stav: zamluvené Jakubem Sosnovcem (v případě zájmu určitě mohu nabídnout jiné kombinatoricko-geometrické téma)