Záverečné rigorózne skúšky a obhajoba dizertačnej práce z Luke Postle

Link: http://www-old.aco.gatech.edu/dissert/postle.html

Záverečná doktorská skúška a obhajoba dizertačnej práce Luke Postle

Názov: 5-Zoznam-farbenie Grafy na povrchu

čas: Utorok 14. augusta, 1:00
miesto: Skiles 005
poradca: Robin Thomas, Matematická škola
Výbor: Dr. Xingxing Yu, Matematická škola
Dr. William T. Trotter, Matematická škola
Dr. William Cook, škola priemyselného a systémového inžinierstva
Dr. Zdenek Dvořák, Ústav teoretickej informatiky, Univerzita Karlova
Reader: Dr. Zdenek Dvořák, Ústav teoretickej informatiky, Univerzita Karlova

Abstrakt:

Thomassen dokázal, že na pevnom povrchu môžu byť zakotvené len 6 kritické grafy. Ukázal tiež, že rovinné grafy sú 5-listovo farebné. Táto diplomová práca vyvíja nové techniky na preukázanie všeobecných teorémov pre 5-listové farebné grafy zabudované do pevného povrchu. V skutočnosti sa stanovuje všeobecná paradigma, ktorá zlepšuje počet predchádzajúcich výsledkov pri riešení niekoľkých otvorených dohôd. Okrem toho sú dôkazy takmer úplne samostatné.

V nasledujúcom prípade nechajme S pevnú plochu, G je graf vložený do S a L tak, že pre každý vrchol v G, L (v) má veľkosť najmenej päť. Po prvé, táto diplomová práca poskytuje nezávislý dôkaz a zároveň zlepšuje viazanosť, ktorú získali DeVos, Kawarabayashi a Mohar, ktorý hovorí, že ak G má veľkú šírku okrajov, potom G je 5-listovo sfarbiteľný. Väzba na šírku okrajov je vylepšená z exponenciálneho na logaritmický v rode Euler, čo je najlepšie možné až po multiplikačnú konštantu. Po druhé, táto práca dokazuje, že existujú iba konečne veľa kritických 6-listov, ktoré sa dajú zakomponovať do S, a riešia domnienku Thomassena z roku 1994. Naozaj sa ukazuje, že počet vrcholov v kritickom grafe o 6 zoznamoch je nanajvýš lineárny v rode, čo je najlepšie možné až po multiplikačnú konštantu. Ako dôsledok,

Ďalej dokazujeme, že počet L farieb L-farebného grafu zakomponovaného v S je exponenciálny v počte vrcholov G, s konštantou závislou len na Eulerovom rode g S. Týmto sa vyriešil ešte ďalší dohad Thomassena od roku 2007. Táto práca tiež dokazuje, že ak X je podmnožina vrcholov G, ktoré majú párovú vzdialenosť v poradí najmenej log (g) a šírka okraja G je tiež aspoň v poradí log ( g), potom sa akékoľvek L-zafarbenie X rozširuje na L-sfarbenie G. Pre planárne grafy to bolo domýšľané Albertsonom a nedávno dokázané Dvořákom, Lidickým, Moharom a Postle. Pre pravidelné sfarbenie to dokázali Albertson a Hutchinson. Ďalšie súvisiace zovšeobecnenia sa skúmajú.