Original title: Hamiltonovské kružnice v Kneserových grafech
Translated title: Hamiltonian cycles in Kneser graphs
Authors: Hulcová, Tereza ; Šámal, Robert (advisor) ; Gregor, Petr (referee)
Document type: Bachelor's theses
Year: 2017
Language: cze
Abstract: [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.
Keywords: hamiltonian cycle;Kneser graphs;hypercube; hamiltonovská kružnice;Kneserovy grafy;hyperkrychle

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/90465

Permalink: http://www.nusl.cz/ntk/nusl-365062


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses