Combinatorial Nullstellensatz: With Applications to Graph Colouring
A kombinatorikus nullstellensatz egy új algebrai tétel, amelyet Noga Alon vezetett be a matematika különböző területein felmerülő kombinatorikai problémák megoldására. Ez a könyv ennek a tételnek a gráfszínezésre való alkalmazására összpontosít. A kombinatorikus nullstellensatz alkalmazásainak egyik legfontosabb lépése annak megmutatása, hogy egy bizonyos monom együtthatója egy polinom kiterjesztésében nem nulla. A könyv nagy része az együtthatók kiszámításának három módszerére koncentrál:
⬤ Alon-Tarsi orientáció: A feladat az, hogy megmutassuk, hogy egy gráfnak van olyan orientációja, amelynek adott a maximális kimeneti fokszáma, és amelynél a páros Euler-féle részgráfok száma különbözik a páratlan Euler-féle részgráfok számától. Konkrétan ezzel a módszerrel megmutatható, hogy egy olyan gráf, amelynek élhalmaza Hamilton-ciklusra és csúcsoktól elválasztott háromszögekre bomlik, 3-választható, és hogy minden sík gráfnak van olyan illeszkedése, amelynek törlése 4-választható gráfot eredményez.
⬤ Interpolációs képlet az együtthatóra: Ezt a módszert különösen arra használjuk, hogy megmutassuk, hogy a páros rendű toroidális rácsok 3-kiválaszthatóak, az r-edge színezhető r-szabályos síkgráfok r-edge választhatóak, és a p+1 rendű teljes gráfok, ahol p egy prím, p-edge választhatóak.
⬤ A koefficiensek, mint a mátrixok állandói: Ezt a módszert különösen a csúcs-élek súlyozásának listás változatának tanulmányozására és annak kimutatására használják, hogy minden gráf (2,3)-választható.
A könyv alkalmas a matematika felsőfokú kurzusának referenciakönyveként.