|
|
Structure and complexity of homomorphisms
Bok, Jan ; Nešetřil, Jaroslav (vedoucí práce)
Tato práce se zabývá výpočetními problémy okolo grafových homomorfismů a příbuz- ných konceptů. Především se zabýváme složitostními dichotomiemi, které rozlišují mezi polynomiálními a NP-úplnými problémy. Výsledky tohoto typu jsou velmi populární, a to jak díky klasickému výsledku Hella a Nešetřila, tak i díky nedávnému vyřešení hypotézy o dichotomii pro problémy s omezujícími podmínkami (CSP). Práce se dělí na tři části, jejichž společným pojítkem je cíl prozkoumat složitost a následně určit dichotomii různých problémů speciálních typů či zobecnění grafových ho- momorfismů. První část se zabývá signed grafy, kde dokazujeme složitostní dichotomii listové, do- sud nezkoumané varianty homomorfismu pro případ, že cílový graf je strom anebo graf tzv. cyklově- nebo cestově-separovatelný. Druhá část se zabývá problémem grafového na- krytí, který je známý jak v algebraické, tak v algoritmické teorii grafů. Tato část práce si klade za cíl rozšířit zkoumání složitosti na grafy s povolenými vícenásobnými hranami, smyčkami a s půlhranami. Zde zkoumáme (a) klasifikaci složitosti pro jednovrcholové a dvouvrcholové cíle, (b) jaká je správná definice grafového nakrytí pro nesouvislé cíle a (c) co se stane, když přidáme do problému listové podmínky. Poslední část se zabývá acyklickými barveními a složitostí hledání...
|
|
|
Structure and complexity of homomorphisms
Bok, Jan ; Nešetřil, Jaroslav (vedoucí práce) ; Golovach, Petr (oponent) ; Proskurowski, Andrzej (oponent)
Tato práce se zabývá výpočetními problémy okolo grafových homomorfismů a příbuz- ných konceptů. Především se zabýváme složitostními dichotomiemi, které rozlišují mezi polynomiálními a NP-úplnými problémy. Výsledky tohoto typu jsou velmi populární, a to jak díky klasickému výsledku Hella a Nešetřila, tak i díky nedávnému vyřešení hypotézy o dichotomii pro problémy s omezujícími podmínkami (CSP). Práce se dělí na tři části, jejichž společným pojítkem je cíl prozkoumat složitost a následně určit dichotomii různých problémů speciálních typů či zobecnění grafových ho- momorfismů. První část se zabývá signed grafy, kde dokazujeme složitostní dichotomii listové, do- sud nezkoumané varianty homomorfismu pro případ, že cílový graf je strom anebo graf tzv. cyklově- nebo cestově-separovatelný. Druhá část se zabývá problémem grafového na- krytí, který je známý jak v algebraické, tak v algoritmické teorii grafů. Tato část práce si klade za cíl rozšířit zkoumání složitosti na grafy s povolenými vícenásobnými hranami, smyčkami a s půlhranami. Zde zkoumáme (a) klasifikaci složitosti pro jednovrcholové a dvouvrcholové cíle, (b) jaká je správná definice grafového nakrytí pro nesouvislé cíle a (c) co se stane, když přidáme do problému listové podmínky. Poslední část se zabývá acyklickými barveními a složitostí hledání...
|
|
|
Structural aspects of aesthetic visualinformation processing
Douchová, Veronika ; Nešetřil, Jaroslav (vedoucí práce) ; Klazar, Martin (oponent) ; Vlček, Tomáš (oponent)
Univerzita Karlova Filozofická fakulta Katedra logiky Obor: Logika Strukturální aspekty zpracování vizuální informace s estetickou složkou Structural aspects of aesthetic visual information processing Abstrakt Mgr. Veronika Douchová vedoucí (supervisor): prof. RNDr. Jaroslav Nešetřil, DrSc., 2022 Abstrakt Tato disertační práce studuje a formuluje potenciální rámec pro analýzu as- pektů estetiky vizuální informace ze strukturální a matematické perspektivy. Práce využívá výsledky relativně nového oboru neuroestetiky (podoboru neu- rologie založenému koncem 90. let Semirem Zekim), které propojují proces vidění a vyhodnocování estetické vizuální informace se strukturou lidského mozku. Výsledky bádání v neuroestetice identifikují principy ovlivňující es- tetické soudy a propojují jejich formování se strukturou lidského mozku, jde např. o aspekty modularity, symetrie, harmonie nebo vyváženého stavu. Ve své práci tvrdím, že tyto výsledky poskytují objektivní interpretativní rámec pro analýzu specifických aspektů vizuální informace s estetickou komponen- tou pomocí matematických metod. Aplikací těchto výsledků na estetické mě- řítko G. D. Birkhoffa pokládám objektivní základy pro jeho teoretické metody postavené na algebraických invariantech estetického zážitku. V práci dále analyzuji teorii prof. J. Nešetřila a...
|
|
| |
|
|
Representation of special classes of combinatorial objects
Scholleová, Barbora ; Nešetřil, Jaroslav (vedoucí práce) ; Loebl, Martin (oponent)
V této práci se pokoušíme propojit poznatky ze dvou oblastí teorie grafů. Nejprve uvádíme základní pojmy týkající se homomorfismů grafů. Text směřuje k defi- nici nahrazovací operace užitím vhodného nahrazovacího grafu. Dále popisujeme vlastnosti stromové hloubky, jedné z význačných charakteristik každého grafu. Posléze se zabýváme reprezentacemi kategorií v kategorii Graph všech konečných grafů a Graphk všech konečných grafů se stromovou hloubkou nejvýše k.
|
|
|
Freimanova věta v aditivní kombinatorice
Hančl, Jaroslav ; Klazar, Martin (vedoucí práce) ; Nešetřil, Jaroslav (oponent)
V předložené shrnující práci studujeme takzvaný inverzní problém aditivní teorie čísel. Snažíme se tedy charakterizovat množiny A přirozených čísel, víme-li nějaké informace o jejich násobcích 2A = A + A. Zpočátku se budeme věnovat konečným množinám s vlastností |2A| = 2|A| - 1, dále si ukážeme zobecnění pro takové abelovské grupy G, v nichž má každý prvek řad omezenýy konstantou r, a jejich podmnožiny A splňující |2A| - c|A|. Nakonec se dostaneme až k slavné Freimanově větě, která popisuje množiny přirozených čísel A, jež jsou malé ve smyslu |2A| - c|A|. Tuto větu dokážeme a uvedeme některé její důsledky a aplikace.
|
|
|
Algebraic, Structural, and Complexity Aspects of Geometric Representations of Graphs
Zeman, Peter ; Klavík, Pavel (vedoucí práce) ; Nešetřil, Jaroslav (oponent)
Title: Algebraic, Structural and Complexity Aspects of Geometric Representations of Graphs Author: Peter Zeman Department: Computer Science Institute Supervisor: RNDr. Pavel Klavík Supervisor's e-mail: klavik@iuuk.mff.cuni.cz Keywords: automorphism groups, interval graphs, circle graphs, comparability graphs, H-graphs, recognition, dominating set, graph isomorphism, maximum clique, coloring Abstract: We study symmetries of geometrically represented graphs. We describe a tech- nique to determine the automorphism group of a geometrically represented graph, by understanding the structure of the induced action on all geometric representations. We prove that interval graphs have the same automorphism groups as trees, and for a given interval graph, we construct a tree with the same automorphism group which answers a question of Hanlon [Trans. Amer. Math. Soc 272(2), 1982]. For permutation and circle graphs, we give an inductive characterization by semidirect and wreath prod- ucts. We also prove that every abstract group can be realized by the automorphism group of a comparability graph/poset of the dimension at most four. We also study H-graphs, introduced by Biró, Hujter, and Tuza in 1992. Those are intersection graphs of connected subgraphs of a subdivision of a graph H. This thesis is the first comprehensive...
|
|
| |
|
|
Ramseyova teorie a kombinatorické hry
Valla, Tomáš ; Nešetřil, Jaroslav (vedoucí práce) ; Valtr, Pavel (oponent)
Ramseyova teorie studuje vnitřní homogenitu matematických struktur (grafů, číselných oborů), jejichž části (podgrafy, podmnožiny) jsou libovolně obarveny. Často platí, že je-li studovaný objekt dostatečně velký, lze v něm najít určitý jednobarevný podobjekt. Kombinatorické hry jsou hry dvou hráčů s plnou informací, kde záleží pouze na jejich inteligenci. Teorie kombinatorických her studuje především otázky existence vyhrávajících či neprohrávajících strategií. Vezmeme-li ramseyovskou větu a necháme-li objekt, který tato věta studuje, střídavě barvit dvěma hráči, jejichž cílem je vytvořit určitý monochromatický podobjekt, dostaneme kombinatorickou hru. Předmětem našeho zájmu je jednak nejmenší velikost objektu, při které platí ramseyovská věta, tzv. ramseyovské číslo, a jednak nejmeněí velikost téhož objektu, při které má první hráč vyhrávající strategii v příslušné kombinatorické hře, tzv. herní číslo. V této práci popisujeme takové ramseyovské věty, u nichž je ramseyovské číslo podstatně větší než číslo herní. To znamená, že podáváme důkazy existence vyhrávajících strategií prvního hráče spolu s horními odhady na ramseyovská a herní čísla a obě čísla porovnáváme.
|
|
|
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.