Název: Hamiltonovské kružnice v Kneserových grafech
Překlad názvu: Hamiltonian cycles in Kneser graphs
Autoři: Hulcová, Tereza ; Šámal, Robert (vedoucí práce) ; Gregor, Petr (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2017
Jazyk: cze
Abstrakt: [cze] [eng]
V této práci se budeme zabývat existencí hamiltonovských kružnic v Kneserových grafech: graf K(n, k) obsahující jako množinu vrcholů všechny k-tice z n prvků. Hranou jsou spojeny pouze disjunktní dvojice. Lovászova hypotéza o vrcholově tranzitivních gra- fech implikuje hamiltonovskost K(n, k) pro n ≥ 2k + 1. Chen ukázala, že K(n, k) jsou hamiltonovské pro n ≥ 3k, později vylepšila svůj výsledek na n ≥ 2.6k + 1. V obou pří- padech použila Baranyaiho rozklad. Nedávný důkaz hypotézy středních vrstev umožnil dokázat, že bipartitní Kneserovy grafy obsahují hamiltonovskou kružnici. S některými ze zmíněných důkazů seznámíme čtenáře podrobněji. In this thesis, we will discuss existence of hamiltonian cycles in Kneser graphs: graphs K(n,k) with vertex set corresponding to k-element subsets from set of n elements, and vertices will be adjacent if and only if their corresponding k-sets are disjoint. Lovász's conjecture about vertex transitive graphs implies hamiltonicity of Kneser graphs for n ≥ 2k + 1. Chen proved that K(n, k) are hamiltonian for n ≥ 3k. Later she improved her result to n ≥ 2.6k + 1. In both cases she used Baranyai's partition theorem. Recent proof of Middle levels conjecture allowed to show hamiltonicity of bipartite Kneser graphs. We will get familiar with some these results.
Klíčová slova: hamiltonovská kružnice;Kneserovy grafy;hyperkrychle; hamiltonian cycle;Kneser graphs;hypercube

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/90465

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-365062


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce