Seminar za algebru, matematičku logiku i teoriju brojeva 17. 6.

Vreme i mesto: Sreda, 17. jun u 12:15 u sali 844

Predavač: Tanja Stojadinović, Matematički fakultet

Naslov predavanja: Hromatska funkcija grafa – tri otvorene hipoteze

Sažetak: Problem bojenja geografske karte sa četiri boje, postavljen 1852. godine, doveo je do razvoja mnogih alata u algebarskoj kombinatorici i drugim oblastima, među njima i uvođenja hromatskog polinoma grafa 1912. godine. Birhof je očekivao da će, ako pokaže da je vrednost hromatskog polinoma u broju 4 pozitivna za svaki planaran graf, rešiti problem četiri boje. Iako je na kraju ovaj problem rešen mnogo kasnije, potpuno drugačijim metodama, hromatski polinom je otvorio čitavo novo polje istraživanja. Najveći pomak u tom istraživanju dogodio se 1995. kada je Ričard Stenli uveo hromatsku simetričnu funkciju grafa, kao uopštenje hromatskog polinoma. Ona nam daje informacije o tome koliko puta je svaka boja upotrebljena prilikom pravilnog bojenja grafa, a za njeno ispitivanje nam je na raspolaganju dobro razvijena teorija simetričnih funkcija. U ovom izlaganju biće predstavljene tri glavne hipoteze koje se tiču hromatske funkcije, od kojih su dve formulisane pre 30 godina u Stenlijevom radu. Najpoznatija od njih je Stenli-Stembridž hipoteza, koja kaže da ako posmatramo graf neuporedivosti poseta koji ne sadrži lanac od tri elementa i četvrti koji je neuporediv sa njima, njegova hromatska funkcija ima pozitivne koeficijente kada se razvije u bazi elementarnih simetričnih funkcija. U prethodne tri decenije uvedena su mnoga uopštenja ove funkcije u nadi da će se lakše dokazati njihova pozitivnost, a takođe su izdvojene i razne klase grafova čija hromatska funkcija jeste pozitivna u elementarnoj bazi. Iako je prošle godine predstavljen dokaz ove hipoteze koji koristi verovatnoće vezane za Jangove tabloe, algebarski kombinatoristi nastavljaju svoja istraživanja. Druga hipoteza kaže da su dva drveta sa istim hromatskim funkcijama izomorfna. Dokazana je za nekolicinu familija drveta, i proverena za drveta sa najviše 29 čvorova. Na kraju, ,,ukrštanjem“ prethodne dve, pre nekoliko godina formulisana je i treća hipoteza, koja tvrdi da ako drvo sadrži čvor stepena većeg ili jednakog četiri, njegova hromatska funkcija nije pozitivna u elementarnoj bazi.

Najavu predavanja i više informacija o seminaru možete pronaći na stranici seminara:

https://aml.matf.bg.ac.rs/?str=seminar