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