Hamiltonovské kružnice v Kneserových grafech
| Název práce v češtině: | Hamiltonovské kružnice v Kneserových grafech |
|---|---|
| Název v anglickém jazyce: | Hamiltonian cycles in Kneser graphs |
| Klíčová slova: | hamiltonovská kružnice;Kneserovy grafy;hyperkrychle |
| Klíčová slova anglicky: | hamiltonian cycle;Kneser graphs;hypercube |
| Akademický rok vypsání: | 2016/2017 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | čeština |
| Ústav: | Informatický ústav Univerzity Karlovy (32-IUUK) |
| Vedoucí / školitel: | doc. Mgr. Robert Šámal, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 12.05.2017 |
| Datum zadání: | 12.05.2017 |
| Datum potvrzení stud. oddělením: | 18.05.2017 |
| Datum a čas obhajoby: | 06.09.2017 00:00 |
| Datum odevzdání elektronické podoby: | 22.07.2017 |
| Datum odevzdání tištěné podoby: | 21.07.2017 |
| Datum proběhlé obhajoby: | 06.09.2017 |
| Oponenti: | doc. Mgr. Petr Gregor, Ph.D. |
| Zásady pro vypracování |
| Lovász [1] se ptal, zda všechny souvislé vrcholově tranzitivní grafy jsou (až na vyjmenované výjimky) hamiltonovské. To motivovalo podrobný výzkum hamiltonovskosti pro konkrétní třídy grafů, viz např. nedávno [2] vyřešená "Middle levels conjecture".
Pro Kneserovy grafy K(n,k) je Lovászova otázka (pozitivně) vyřešena pro n > 2.62k. Studentka prozkoumá dostupnou literaturu, pokusí se dostupné důkazy srozumitelněji vysvětlit, případně rozšířit pro větší část Kneserový grafů. |
| Seznam odborné literatury |
| [1] Lászlo Lovász. Problem 11, in Combinatorial structures and their applications. In Proceedings of the Calgary International Conference on Combinatorial Structures and their Applications (Calgary, Alberta, 1969), pages xvi+508, New York, 1970. Gordon and Breach Science Publishers.
[2] Torsten Mütze: Proof of the middle levels conjecture, Proc London Math Soc (2016) 112 (4): 677-713. A další podle doporučení školitele. |