CSP pocházející z kombinatorické topologie

• Název práce v češtině: CSP pocházející z kombinatorické topologie
• Název v anglickém jazyce: CSP coming from combinatorial topology
• Klíčová slova: Násobně propletený graf|CSP|algoritmy
• Klíčová slova anglicky: Multiply linked graph|CSP|algorithms
• Akademický rok vypsání: 2024/2025
• Typ práce: bakalářská práce
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: prof. RNDr. Martin Tancer, Ph.D.
• Řešitel: Patrik Zavoral - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 21.03.2025
• Datum zadání: 27.03.2025
• Datum potvrzení stud. oddělením: 27.03.2025

Zásady pro vypracování

Graf je k-násobně propletený, pokud každé jeho vnoření do R^3 obsahuje k-tici cyklů z nichž každé dva jsou propletené (v topologickém smyslu). Existence násobně propletených grafů je známá, ale známé konstrukce vedou k obrovským grafům. Například není známo, jestli úplný graf K_9 je trojnásobně propletený. Tuto úlohu lze přirozeně formulovat jako tzv. "Constraint satisfaction problem" (CSP). Pro graf K_9 například dostáváme CSP se 189 proměnnými, které mohou nabývat hodnot 0 nebo 1 a dále 280 omezeními v nichž se vyskytují 27-ární relace. Toto CSP je už příliš velké, aby šlo naivně projít všechny možnosti. Na druhou stranu toto CSP vykazuje vysokou míru symetrie (je na něm jistá struktura vektorového prostoru a také symetrie pocházející ze symetrií K_9), která by měla pomoci k jeho řešení. To lze případně kombinovat s jinými technikami na řešení CSP.

Cílem práce je řešit výše zmíněné CSP, popř. další pocházející z jiných nastavení parametrů. Ideální by bylo navrhnout vhodný algoritmus (který doběhne) pro vyřešení CSP pro K_9. Dá se předpokládat, že algoritmus bude adaptivní ve smyslu, že bude uzpůsobovat svůj běh na základě získaných mezivýsledků. Vzhledem k tomu, že ale nejsou záruky, že takový algoritmus se podaří navrhnout, práci lze považovat za úspěšnou při dosažení jiných cílů. Těmi mohou například být vyřešení CSP pro jiné malé husté grafy (například K_9 bez hrany); navržení a provedení vhodných náhodných experimentů pro dolní odhady; teoretické vylepšení odhadů (když už je příslušné CSP příliš velké, tak řešení nemá).

Práce bude vypracována anglicky.

Seznam odborné literatury

Brailsford, S.C., Potts, C.N. and Smith, B.M., 1999. Constraint satisfaction problems: Algorithms and applications. European journal of operational research, 119(3), pp.557-581.

Conway, J.H. and McA. Gordon, C., 1983. Knots and links in spatial graphs. Journal of Graph Theory, 7(4), pp.445-453.

Flapan, E., Mellor, B., and Naimi, R. 2008, Intrinsic linking and knotting are arbitrarily complex, Fund. Math. 201(2), 131--148

Winter, M., 2024. Do triple-linked graphs exist? MathOverflow question, https://mathoverflow.net/questions/465865/do-triple-linked-graphs-exist