Mgr. Jan Volec, Ph.D.
Důkaz Goldberg-Seymourovy domněnky s pomocí počítače
| školitel: |
Mgr. Jan Volec, Ph.D. |
| e-mail: |
zobrazit e-mail
|
| typ práce: |
bakalářská práce, diplomová práce
|
| zaměření: |
MINF, APIN |
| klíčová slova: |
Teorie grafů, hranová barevnost, párování, počítačově asistované důkazy |
| odkaz: |
http://honza.ucw.cz/thesis
|
| popis: |
Tématem této práce je jeden z nejznámějších problémů z oblasti hránové barevnosti grafů, kde je cílem pokrýt množinu hran grafu co nejmenším počtem párování. Jinými slovy, chceme všem hranám přiřadit barvy tak, aby každé dvě sousední hrany dostaly různou barvu.
Goldberg-Seymourova domněnka o hranové barevnosti multigrafů říká, že libovolný multigraf jehož každý vrchol má stupeň nejvýše D lze hranově obarvit pomocí max(D+1, w) barev, kde w značí nejmenší přirozené číslo takové, že pro všechny H podgrafy G s lichým počtem vrcholů číslo w shora odhaduje zlomek 2|E(H)|/(|V(H)|-1). Číslo w je zajisté dolním odhadem, a stejně tak je dolním odhadem i číslo D. Přestože Petersenův graf má D=3 i w=3, je známo, že není hranově-3-obarvitelný, a proto je max(D+1,w) nejlepší horní odhad, v jaký lze doufat.
Cílem této práce je nastudovat nedávný důkaz Goldberg-Seymourovy domněnky a případně též navrhnout verifikaci pomocných tvrzení v tomto důkazu pomocí počítače. |
| literatura: |
A. Bondy, U.S.R. Murty: Graph Theory, Graduate Texts in Mathematics 244, Springer, 2008
G. Chen, G. Jing, W. Zang: Proof of the Goldberg-Seymour Conjecture on Edge-Colorings of Multigraphs, https://arxiv.org/abs/1901.10316
https://en.wikipedia.org/wiki/Goldberg%E2%80%93Seymour_conjecture |
| naposledy změněno: |
22.06.2022 20:14:27 |
Metody inspirované algoritmickým lokálním lemmatem
| školitel: |
Mgr. Jan Volec, Ph.D. |
| e-mail: |
zobrazit e-mail
|
| typ práce: |
bakalářská práce, diplomová práce
|
| zaměření: |
MINF |
| klíčová slova: |
Teorie grafů, pravděpodobnostní metoda, lokální lemma, acyklické obarvení |
| odkaz: |
http://honza.ucw.cz/thesis
|
| popis: |
Tématem této práce je použití nových kombinatorických technik vzniklých jako vedlejší produkt průlomového výsledku Mosera o efektivních algoritmických verzí Lovászova lokálního lemmatu, a následné enumerační metody od Rosenfelda.
Klasickou aplikací lokálního lemmatu je tzv. problém acyklického obarvení hran grafu. Úkolem je obarvit hrany grafu tak, že každé dvě sousední hrany dostanou různé barvy a hrany každého (sudého) cyklu v tomto grafu byl dohromady obarveny alespoň 3 barvami. Fiamčíkova domněnka z roku 1978 (nezávisle též vyslovena v roce 2001 Alonem, Sudakovem a Zaksem) říká, že má-li graf maximální stupeň D, tak lze najít acyklické obarvení hran pomocí D+2 barev (tzn. stačí přidat pouze jednu barvu navíc oproti Vizingově větě). Nejlepší částečný výsledek říká, že existuje acyklické obarvení pomocí 2D-1 barev.
Cílém této práce je nastudovat Rosenfeldovu metodu, a pokusit se ji použít na nalezení acyklického obarvení grafu s co nejmenší paletou barev, a porovnat dosažené výsledky s jinými technikami. |
| literatura: |
https://terrytao.wordpress.com/2009/08/05/mosers-entropy-compression-argument/
M. Rosenfeld: Another approach to non-repetitive colorings of graphs of bounded degree, https://arxiv.org/abs/2006.09094
A. Bernshteyn, T. Brazelton, R. Cao, A. Kang: Counting colorings of triangle-free graphs, https://arxiv.org/abs/2109.13376
L. Kirousis, J. Livieratos: Improved bounds for acyclic coloring parameters, https://arxiv.org/abs/2202.13846 |
| naposledy změněno: |
28.06.2022 10:11:40 |
Důkazy s pomocí počítače v extremální kombinatorice
| školitel: |
Mgr. Jan Volec, Ph.D. |
| e-mail: |
zobrazit e-mail
|
| typ práce: |
bakalářská práce, diplomová práce
|
| zaměření: |
MINF |
| klíčová slova: |
Kombinatorika, lineární a semidefinitní programování, počítačově asistované důkazy |
| popis: |
Hlavním tématem této práce je použití nedávno objevených metod - např. flag algeber či zlomkové obsazení (occupancy fraction) - jež umožňují použít metody spojité optimalizace pro diskrétní úlohy - na otevřené problémy v extremální kombinatorice.
Typický problém z extremální kombinatoriky se snaží (asymptoticky) optimalizovat přes určitou třídu diskretních struktur (např. všech grafů na n vrcholech), daný parametr (např. počet k-prvkových podmnožin vrcholů jež indukují cyklus délky k).
Cílem teto práce je zjistit, zda výše zmíněné metody umožnují vyřešení některého z otevřených problémů extremální teorie grafů, hypergrafů nebo permutací. |
| naposledy změněno: |
28.06.2022 10:12:17 |
Databáze V3S
Aplikace V3S eviduje výsledky vědy a výzkumu a další aktivity vědecko-výzkumných pracovníků ve vědecké komunitě. Aplikace V3S slouží k odesílání výsledků do RIV, exportům pro statistické analýzy i k interním hodnocením vědecko-výzkumné činnosti.
Seznam publikaci ve V3S
za obsah této stránky zodpovídá:
Radek Fučík | naposledy změněno: 7.8.2011
