|
|
Structure of flow-continuous mappings in algebraic context
Hušek, Radek ; Šámal, Robert (vedoucí práce) ; Bonamy, Marthe (oponent) ; Kaiser, Tomáš (oponent)
- Structure of Flow-continuous Mappings in Algebraic Context Radek Hušek Práce zkoumá strukturu prostoru cyklů v grafech - speciálně otázky o nikde-nulových tocích a dvojpokrytích cykly. Nejprve ukážeme, že existují hranově 2-souvislé grafy, které rozlišují Z2 2 a Z4 grupovou souvislost (grupová souvislost je zesílením nikde-nulových toků). Poté zkoumáme domněnku Matta DeVose o existenci toků v grafech za podmínky, že existuje grafový homomorfismus mezi vhodnými Cayleyho grafy. Formulujeme zesílení této domněnky, které nazýváme "strong homomorphism property" (SHP), které nám dovolí rozdělovat vrcholy vyššího stupně (a tedy redukovat problém na kubické grafy). Předkládáme hypotézu, že SHP platí pro každý graf a nejmenší grupu, v níž má tento graf nikde-nulový tok. Také ukazujeme, že jak SHP, tak původní domněnka implikují existenci dvojpokrytí cykly s malým počtem cyklů. Následně se zabýváme počítáním objektů na grafech - speciálně dvojpokrytí kružnicemi. Ukazujeme téměř exponenciální dolní odhad pro grafy s vhodným nakreslením na plochu, ale taktéž nahlédneme, že tento odhad se nevztahuje na Flower snarky, které žádné takové nakreslení nemají. Následně ukazujeme asymptoticky těsný odhad na počet CDC Flower snarků a taktéž vylepšujeme dolní odhad pro rovinné grafy na exponenciální. Na závěr...
|
host ::
RSS.