Original title: CSP pocházející z kombinatorické topologie
Translated title: CSP coming from combinatorial topology
Authors: Zavoral, Patrik ; Tancer, Martin (advisor) ; Chmel, Petr (referee)
Document type: Bachelor's theses
Year: 2025
Language: cze
Abstract: [cze] [eng]
Graph G je k-zalinkovaný, pokud každé vnoření G do prostoru obsahuje k-tici cyklů, z nichž každé dva jsou topologicky netriviálně zalinkované. k-zalinkované grafy existují, ale jejich známé konstrukce jsou velmi velké. Na druhou stranu, již úplný graf K6 je 2-zalinkovaný. V této práci dokážeme, že úplný graf K3k není k-zalinkovaný pro žádné dalsí k ≥ 3. Použijeme k tomu prohledávací formulaci k-zalinkovanosti, která v malých grafech povede ke vnořením bez k-tic cyklů se vzájemně lichými linkovacími čísly. Takové vnoření pro K9 zrealizujeme geometricky za pomocí unlinků, a tuto konstrukci následně zobecníme na vnoření K3k pro libovolné k ≥ 3. A graph G is intrinsically k-linked if every spatial embedding of G contains k pair- wise topologically non-trivially linked cycles. Intrinsically k-linked graphs exist, but the known constructions are very large. At the same time, the complete graph K6 is already intrinsically 2-linked. We show that K3k is not intrinsically k-linked for any k ≥ 3. To do this, we formulate k-linkedness as a search problem, which will yield embeddings of var- ious small graphs without any k-link with pairwise odd linking numbers. We will realize such embedding of K9 geometrically using unlinks, and finally generalize this construction to K3k for any k ≥ 3.
Keywords: Multiply linked graph|CSP|algorithms; Násobně propletený graf|CSP|algoritmy

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/202639

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


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