Combinatorial Nullstellensatz: Cu aplicații la colorarea grafurilor

Titlul original:

Combinatorial Nullstellensatz: With Applications to Graph Colouring

Conținutul cărții:

Combinatorial Nullstellensatz este o teoremă nouă în algebră introdusă de Noga Alon pentru a aborda probleme combinatorii în diverse domenii ale matematicii. Această carte se concentrează pe aplicațiile acestei teoreme la colorarea grafurilor. Un pas cheie în aplicațiile Nullstellensatz combinatorial este de a arăta că coeficientul unui anumit monomial în expansiunea unui polinom este diferit de zero. Cea mai mare parte a cărții se concentrează pe trei metode de calculare a coeficienților:

⬤ Orientarea Alon-Tarsi: Sarcina este de a demonstra că un graf are o orientare cu un grad de ieșire maxim dat și pentru care numărul de subdigrafe euleriene pare este diferit de numărul de subdigrafe euleriene impare. În special, această metodă este utilizată pentru a demonstra că un graf al cărui set de muchii se descompune într-un ciclu Hamilton și în triunghiuri cu vertexuri disjuncte este 3-alegibil și că orice graf plan are o potrivire a cărei eliminare duce la un graf 4-alegibil.

⬤ Formula de interpolare pentru coeficient: Această metodă este utilizată în special pentru a demonstra că rețelele toroidale de ordin par sunt 3-alegibile, grafurile planare r-regulare cu colorație r sunt r-alegibile, iar grafurile complete de ordin p+1, unde p este un prim, sunt p-alegibile.

⬤ Coeficienții ca permanenți ai matricelor: Această metodă este utilizată în special în studiul versiunii de listă a ponderii vertex-edge și pentru a demonstra că orice graf este (2,3)-alegibil.

Lucrarea este potrivită ca o carte de referință pentru un curs universitar de matematică.