Combinatorial Nullstellensatz: With Applications to Graph Colouring

Obsah knihy:

Kombinatorický Nullstellensatz je nová veta v algebre, ktorú zaviedol Noga Alon na riešenie kombinatorických problémov v rôznych oblastiach matematiky. Táto kniha sa zameriava na aplikácie tejto vety na farbenie grafov. Kľúčovým krokom v aplikáciách Combinatorial Nullstellensatz je ukázať, že koeficient určitého monómu v rozšírení polynómu je nenulový. Hlavná časť knihy sa sústreďuje na tri metódy výpočtu koeficientov:

⬤ Alon-Tarsiho orientácia: Úlohou je ukázať, že graf má orientáciu s daným maximálnym stupňom von a pre ktorý sa počet párnych Eulerových podgrafov líši od počtu nepárnych Eulerových podgrafov. Konkrétne sa táto metóda používa na dokázanie, že graf, ktorého množina hrán sa rozkladá na Hamiltonov cyklus a vrcholovo disjunktné trojuholníky, je 3-voliteľný a že každý rovinný graf má zhodu, ktorej vymazaním vzniká 4-voliteľný graf.

⬤ Interpolačný vzorec pre koeficient: Táto metóda sa používa najmä na to, aby sa ukázalo, že toroidálne siete párneho rádu sú 3-vyberateľné, r-hranné kolmé r-pravidelné rovinné grafy sú r-hranné vyberateľné a úplné grafy rádu p+1, kde p je prvočíslo, sú p-hranné vyberateľné.

⬤ Koeficienty ako trvalé prvky matíc: Táto metóda sa používa najmä pri štúdiu verzie zoznamu váh vrcholov a hrán a pri dokazovaní, že každý graf je (2,3)-vyberateľný.

Je vhodná ako príručka pre postgraduálny kurz matematiky.