|
|
Structural properties of hereditary permutation classes
Opler, Michal ; Jelínek, Vít (vedoucí práce) ; Valtr, Pavel (oponent)
Permutační třída C je splittovatelná pokud je obsažena v mergi svých dvou vlastních podtříd, a je 1-amalgamovatelná pokud pro libovolné permutace σ, τ ∈ C, každá s jedním vyznačeným prvkem, dokážeme najít permutaci π ∈ C, která obsahuje σ i τ tak že jejich vyznačené prvky splývají. V této práci zkoumáme 1-amalgamovatelnost a splittovatelnost permutačních tříd. Již dříve bylo dokázáno, že nesplittovatelnost implikuje 1-amalgamovatelnost. My ukážeme, že tyto dvě vlastnosti permutačních tříd nejsou ekvivalentní nalezením permutační třídy, která je splittovatelná a zároveň 1-amalgamovatelná. Navíc ukážeme, že existuje nekonečně mnoho takových permutačních tříd. Naše konstrukce je založená na konceptu LR-nafouknutí nebo více obecně na dědičných 2-obarvení, které v této práci také zavedeme a které by mohly být zajímavé i mimo naše použití. 1
|
|
|
Algoritmus pro dokreslování rovinných nakreslení
Hora, Martin ; Jelínek, Vít (vedoucí práce) ; Šámal, Robert (oponent)
Tento text se zabývá problémem dokreslování rovinných grafů. Vstupem pro- blému je graf G, jehož podgraf je již nakreslen do roviny. Cílem je pak rozhodnout, zda lze do roviny dokreslit i zbytek grafu G, a získat tak rovinné nakreslení G. Již bylo dokázáno, že lze dokreslitelnost rovinných grafů řešit v lineárním čase. Avšak všechny známé lineární algoritmy jsou poměrně komplikované, a pravděpodobně proto nebyla zveřejněna žádná jejich implementace. V práci představíme nový jednodušší lineární algoritmus řešící dokreslitelnost a dokážeme jeho korektnost. Dále pak k této práci přiložíme implementaci tohoto algoritmu v programovacím jazyce C++. 1
|
|
|
Hereditary classes of binary matrices
Kučera, Stanislav ; Jelínek, Vít (vedoucí práce) ; Klazar, Martin (oponent)
Intervalové minory binárních matic byly zavedeny Jacobem Foxem při vý- zkumu Stanleyho-Wilfových limit. Prozkoumáme, co se dá odvodit z jejich vztahu s teorií neobsahování podmaticových vzorů, což je velmi populární oblast diskrétní matematiky. Začneme charakterizací matic neobsahujících malé intervalové mi- nory. Poté se podíváme na třídy matic uzavřené na intervalové minory a najdeme takové třídy, které nelze popsat pomocí konečně mnoha zakázaných intervalových minorů. Také zadefinujeme a prozkoumáme variantu klasické Turánovské otázky zkoumané v oblastech kombinatoriky permutací a binárních matic a kombinato- rické geometrie. 1
|
|
|
Průnikové reprezentace grafů
Töpfer, Martin ; Jelínek, Vít (vedoucí práce) ; Šámal, Robert (oponent)
Průnikový graf je graf, ve kterém mezi dvěma vrcholy vede hrana, právě když jim odpovídající objekty se protínají. Tato práce se zabývá průnikovými grafy L-útvarů (tzv. L-grafy) a jejich speciálním případem, kdy konce všech L-útvarů jsou na jedné přímce (tzv. vnějškovými L-grafy). Po přehledu, co platí o L-grafech, používáme podobné postupy na vnějškové L-grafy. Ukážeme, že intervalové grafy, tětivové grafy (circular graphs) a vnějškově rovinné grafy jsou vnějškové L-grafy. Poté charakterizujeme vnějškové L-grafy pomocí uspořádání vrcholů bez zakázaných vzorů. Powered by TCPDF (www.tcpdf.org)
|
|
|
Generating random pattern-avoiding matrices
Kučera, Stanislav ; Jelínek, Vít (vedoucí práce) ; Šámal, Robert (oponent)
Binární matice neobsahující menší matici jako podmatici se stávají zajímavým tématem. V mé práci uvádím dva nové algoritmy pro testování, zda velká čtvercová binární matice obsahuje menší binární matici, a randomizovaný proces, který aproximuje uniformní náhodnou matici neobsahující danou matici. Toto umožní vědeckým pracovníkům testovat jejich hypotézy na náhodných maticích. Proto moje práce také obsahuje efektivní přenositelnou implementaci všech zmíněných algoritmů. Powered by TCPDF (www.tcpdf.org)
|
|
|
Structure and enumeration of permutation classes
Karpilovskij, Mark ; Jelínek, Vít (vedoucí práce) ; Balko, Martin (oponent)
Definujeme operaci složení dvou dědičných tříd permutací pomocí standardního skládání permutací jako funkcí a zkoumáme vlastnosti a strukturu permutačních tříd s ohledem na tuto operaci. Převážně se zabýváme otázkou, zda lze danou permutační třídu složit z jejích vlastních podtříd. Ukážeme příklady tříd, které lze složit ze dvou vlastních podtříd, příklady tříd, které jdou složit ze tří, ale ne ze dvou vlastních podtříd a také několik příkladů tříd, které nelze složit z žádného konečného počtu vlastních podtříd. Powered by TCPDF (www.tcpdf.org)
|
|
|
Cops and robber game on directed complete graphs
Slívová, Veronika ; Gavenčiak, Tomáš (vedoucí práce) ; Jelínek, Vít (oponent)
BAKALÁŘSKÁ PRÁCE - ABSTRAKT Veronika Slívová Tato práce se zabývá hrou Cops and robber (četníci a zloděj) na turnajích (graf vzniklý zorientováním hran úplného grafu). Ukážeme, že na polapení zloděje stačí málo četníků, pokud turnaj obsahuje vrchol vysokého výstupního stupně. Naopak počet četníků potřebný k polapení zloděje na libovolném turnaji nelze omezit. Dále se práce zabývá cirkulárními turnaji a turnaji vzniklými cyklickou orientací každé trojice ze Steinerovského systému trojic. Vyvrátíme domněnku Geňi Hahna, že počet četníků potřebný k polapení zloděje na libovolném grafu, který vznikl orientací Steinerovského systému trojic, je omezený. Dokážeme, že k polapení zloděje na libovolném cirkulárním turnaji, potřebujeme také neomezený počet četníků. Prozkoumáme i variantu 2-rychlého četníka, který vyhraje hru na libovolném turnaji prvním tahem. Naopak na turnajích s vrcholy stejného výstupního stupně je 2-rychlý zloděj polapitelný triviálně nebo jej nelze chytit.
|
|
| |
|
|
Pattern-avoiding permutation classes
Opler, Michal ; Jelínek, Vít (vedoucí práce) ; Klazar, Martin (oponent)
Major index permutace π je součet všech indexů i takových, že πi > πi+1. V této práci zkoumáme distribuci major indexu na permutacích neobsahujích zakázané vzory. Zajímá nás hodnota Mm n (Π), což je počet permutací délky n s major indexem m a množinou zakázaných vzorů Π. Podařilo se nám ukázat, že pro jednoprvkovou množinu Π = {σ} krom okrajových triviálních pří- padů, se hodnoty Mm n (Π) chovají monotónně, nebo-li Mm n (Π) ≤ Mm n+1(Π). Hlavním výsledkem je rozbor asymptotického chování hodnot Mm n (Π) pro n jdoucí k nekonečnu. Ukážeme, že pro každé pevné m, Π a dostatečně velké n jsou hodnoty Mm n (Π) rovny polynomu v proměnné n a navíc jsme schopni určit stupně těchto polynomů pro různé množiny zakázaných vzorů. 1
|
|
|
Enumerace kompozic čísel se zakázanými vzory
Dodova, Borjana ; Klazar, Martin (vedoucí práce) ; Jelínek, Vít (oponent)
Enumerace kompozic čísel se zakázanými vzory Abstrakt Tato práce si klade za cíl odvodit některé výsledky pro 3-regulární kompozice, tedy kompozice se zakázaným vzorem {121, 212, 11}, které jsou jistým zobecněním Carlitzových kompozic. Pomocí generujících funkcí příslušejících kompozicím se zakázanou množinou vzorů {121, 11} a {212, 11} počítáme horní asymptotický odhad koeficientů mocninného rozvoje generující funkce příslušející 3-regulárním kompozicím. S využitím teorie konečných automatů dostáváme také dolní odhad. Ten posléze zpřesňujeme na základě 3-blokových kompozic. Pro generující funkci příslušející 3- regulárním kompozicím se zvýrazněnou předposlední a poslední částí dokazujeme rekurzivní vztah. Kromě 3-regulárních kompozic a úloh, které s nimi přímo souvisejí, se zabýváme také kompozicemi s množinou zakázaných vzorů {312, 321} s částmi z konečné množiny [d], pro něž odvozujeme maticový tvar generující funkce. V závěru práce dokazujeme transcendentalitu generující funkce příslušející Carlitzovým kompozicím.
|
host ::
RSS.