Combinatorial Nullstellensatz: With Applications to Graph Colouring (Kombinatorický nulový test: s aplikacemi na barvení grafů)

Původní název:

Combinatorial Nullstellensatz: With Applications to Graph Colouring

Obsah knihy:

Kombinatorická nulová věta (Combinatorial Nullstellensatz) je nová věta v algebře, kterou zavedl Noga Alon k řešení kombinatorických problémů v různých oblastech matematiky. Tato kniha se zaměřuje na aplikace této věty na barvení grafů. Klíčovým krokem v aplikacích Combinatorial Nullstellensatz je ukázat, že koeficient určitého monominu v expanzi polynomu je nenulový. Hlavní část knihy se soustřeďuje na tři metody výpočtu koeficientů:

⬤ Alon-Tarsiho orientace: Úkolem je ukázat, že graf má orientaci s daným maximálním výstupním stupněm, pro kterou se počet sudých Eulerových podgrafů liší od počtu lichých Eulerových podgrafů. Konkrétně se touto metodou ukáže, že graf, jehož množina hran se rozkládá na Hamiltonův cyklus a vrcholově nesouvislé trojúhelníky, je 3-volitelný a že každý rovinný graf má shodu, jejíž odstranění vede ke 4-volitelnému grafu.

⬤ Interpolační vzorec pro koeficient: Tato metoda se používá zejména k tomu, aby se ukázalo, že toroidální mřížky sudého řádu jsou 3-volitelné, r-hranné kolmé r-regulární planární grafy jsou r-hranné volitelné a úplné grafy řádu p+1, kde p je prvočíslo, jsou p-hranné volitelné.

⬤ Koeficienty jako trvalé prvky matic: Tato metoda se používá zejména při studiu listové verze vážení vrcholů a hran a k ukázání, že každý graf je (2,3)-vybratelný.

Kniha je vhodná jako příručka pro postgraduální kurz matematiky.