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 |
za obsah této stránky zodpovídá:
Ľubomíra Dvořáková | naposledy změněno: 12.9.2011