|
|
Rothova věta o aritmetických posloupnostech
Krkavec, Michal ; Klazar, Martin (vedoucí práce) ; Kráľ, Daniel (oponent)
Název práce: Rothova věta o aritmetických posloupnostech Autor: Michal Krkavec Katedra: Katedra aplikované matematiky Vedoucí bakalářské práce: doc. RNDr. Martin Klazar, Dr., Katedra aplikované matematiky Abstrakt: V předložené práci se zabýváme vlastnostmi množin přirozených čí- sel neobsahujících aritmetické posloupnosti. Cílem této práce je podat přehled a srovnání analytických a kombinatorických důkazů Rothovy věty, která tvrdí, že každá množina s kladnou horní asymptotickou hustotou obsahuje aritmetic- kou posloupnost délky tři. Zaměříme se také na vývoj poznatků od Erd˝osovy- Turánovy domněnky přes Rothovu větu až ke slavné Szemerédiho větě, která podala odpověď pro aritmetické posloupnosti libovolné délky k. V závěru práce se seznámíme s odhady čísla r3(n), které odpovídá největší velikosti podmnožiny A ⊆ [n], jež neobsahuje žádné aritmetické posloupnosti délky tři. Ukážeme dvě konstrukce, jak takové množiny A ⊆ [n] vybrat. Klíčová slova: Aditivní teorie čísel, Aritmetická posloupnost, Rothova věta, Elki- nova konstrukce
|
|
|
Datové struktury pro setříděné ukládání dat
Bulánek, Jan ; Koucký, Michal (vedoucí práce) ; Kráľ, Daniel (oponent)
V předložené práci studujeme dvě varianty přihrádkovací hry. Tato hra je použita v důkazu spodniho odhadu časové složitosti vkládání prvků do setříděného pole. Ukážeme, že tyto varianty přihrádkovací hramy jí až na konstantní faktor ekvivalentní časovou složitost. Dále ukážeme výhody použití setříděných polí z hlediska vyrovnávacích pamětí. Na závěr ukážeme jednu možnou implementaci vyhledávání datové struktury s použití velikosti n1+e.
|
|
|
Szemerédi Regularity Lemma a jeho aplikace v kombinatorice
Hladký, Jan ; Kráľ, Daniel (vedoucí práce) ; Dvořák, Zdeněk (oponent)
V práci podáme důkaz domněnky Loebla, Komlóse a Sósové (1995) pro husté grafy. Dokážeme následující tvrzení. Pro libovolné q > 0 existuje číslo n0 takové, že pokud má libovolný graf G řadu n > n0 alespoň polovinu vrcholů se stupněm alespoň k > qn, pak G obsahuje každý strom na k+1 vrcholech jako podgraf. Tím vylepšujeme předchozí výsledky autorů Zhao (2002) a Piguet a Stein (2007). Ukážeme, že v jistých případech lze předpoklady věty oslabit. Je diskutována dolní mez k problému. Jako důsledek hlavní věty dostaneme těsný odhad Ramseyova čísla dvou stromů. Důkaz hlavní věty kombinuje vnořovací techniku založenou na Regularity Lemmatu s Metodou stability. Výsledku bylo dosaženo ve společné práci s Dianou Piguet.
|
|
| |
|
|
Varianty problému obarvení
Lidický, Bernard ; Kráľ, Daniel (oponent) ; Fiala, Jiří (vedoucí práce)
V předložené práci studujeme seznamové barvení rovinných grafů. Seznamové barvení je varianta problému barvení grafu, kde každý vrchol má přidělený svůj vlastní seznam možných barev. Říkáme, že graf je k-vybíravý, je-li možnée nalézt dobré obarvení pokaždé, když všechny seznamy obsahují alespoň k barev. Je známo, že každý rovinný graf bez trojúhelníků je 4-vybíravý a každý rovinný bipartitní graf (t.j. bez lichých cyklů) je 3-vybíravý. Práce ukazuje postačující podmínky pro 3-vybíravost rovinných grafů bez trojúhelníků s omezeným výskytem krátkých cyklů.
|
|
|
Zakázané minory pro apexové třídy grafů
Klimošová, Tereza ; Dvořák, Zdeněk (oponent) ; Kráľ, Daniel (vedoucí práce)
V předložené práci se zabýváme hledáním minimálních zakázaných minorů, neboli obstrukcí, pro třídu apexů částečných 2-stromů. Jelikož je tato třída uzavřená na minory, má podle Robertson-Seymourovy věty konečnou množinu obstrukcí. Množina obstrukcí je jedna z možných charakterizací každé třídy uzavřené na minory. V práci analyzujeme strukturu obstrukcí pro třídu apexů částečných 2-stromů a díky její znalosti nacházíme všechny obstrukce s výjimkou speciálního typu obstrukcí, které mají path-width 3. Při hledání obstrukcí využíváme znalosti obstrukcí pro příbuzné třídy grafů.
|
|
| |
|
|
Rozklady grafů
Škoda, Petr ; Fiala, Jiří (oponent) ; Kráľ, Daniel (vedoucí práce)
Submodulární rozkladové funkce zobecňují známé druhy stromových rozkladů grafů. Pro každé pevné k existují polynomiální algoritmy, které rozhodují, zda je stromová či větvená šířka nejvýše k. My ukážeme, že neexistuje algoritmus, který by rozhodoval, zda je šířka dané submodulární rozkladové funkce nejvýše dva v čase menším než exponenciálním. Dále popíšeme novou duální strukturu pro submodulární rozkladové funkce podobnou volným zámotkům pro souvislostní funkce.
|
|
| |
|
|
Parametrizovaná složitost v teorii grafů
Suchý, Ondřej ; Kráľ, Daniel (oponent) ; Kratochvíl, Jan (vedoucí práce)
Seidelovo přepnutí množiny vrcholu je operace, která z grafu odebere hrany vycházející z této množiny a přidá do něj hrany tam, kde mezi množinou a zbytkem grafu nebyly. Ostatní hrany nejsou touto operací dotčeny. Parametrizovaná složitost se ptá, zda lze exponenciální část algoritmu pro těžké problémy omezit nějakou funkcí pouze zvoleného parametru, u nejž lze očekávat malé hodnoty. Tato práce zkoumá složitost otázek, zda lze zadaný graf převést na graf s nějakou vlastností P pomocí Seidelova přepnutí, z parametrizovaného hlediska. Nejdříve krátce shrneme dosud známé výsledky. Pak předvedeme parametrizovanou dostupnost přepnutí na regulární grafy, grafy s omezeným stupněm vrcholu, s omezeným počtem hran a grafy prosté zakázaného podgrafu. Krátce podáme základní definice a postupy parametrizované složitosti.
|
host ::
RSS.