Време и место: Среда, 17. јун у 12:15 у сали 844
Предавач: Тања Стојадиновић, Математички факултет
Наслов предавања: Хроматска функција графа – три отворене хипотезе
Сажетак: Проблем бојења географске карте са четири боје, постављен 1852. године, довео је до развоја многих алата у алгебарској комбинаторици и другим областима, међу њима и увођења хроматског полинома графа 1912. године. Бирхоф је очекивао да ће, ако покаже да је вредност хроматског полинома у броју 4 позитивна за сваки планаран граф, решити проблем четири боје. Иако је на крају овај проблем решен много касније, потпуно другачијим методама, хроматски полином је отворио читаво ново поље истраживања. Највећи помак у том истраживању догодио се 1995. када је Ричард Стенли увео хроматску симетричну функцију графа, као уопштење хроматског полинома. Она нам даје информације о томе колико пута је свака боја употребљена приликом правилног бојења графа, а за њено испитивање нам је на располагању добро развијена теорија симетричних функција. У овом излагању биће представљене три главне хипотезе које се тичу хроматске функције, од којих су две формулисане пре 30 година у Стенлијевом раду. Најпознатија од њих је Стенли-Стембриџ хипотеза, која каже да ако посматрамо граф неупоредивости посета који не садржи ланац од три елемента и четврти који је неупоредив са њима, његова хроматска функција има позитивне коефицијенте када се развије у бази елементарних симетричних функција. У претходне три деценије уведена су многа уопштења ове функције у нади да ће се лакше доказати њихова позитивност, а такође су издвојене и разне класе графова чија хроматска функција јесте позитивна у елементарној бази. Иако је прошле године представљен доказ ове хипотезе који користи вероватноће везане за Јангове таблое, алгебарски комбинатористи настављају своја истраживања. Друга хипотеза каже да су два дрвета са истим хроматским функцијама изоморфна. Доказана је за неколицину фамилија дрвета, и проверена за дрвета са највише 29 чворова. На крају, ,,укрштањем“ претходне две, пре неколико година формулисана је и трећа хипотеза, која тврди да ако дрво садржи чвор степена већег или једнаког четири, његова хроматска функција није позитивна у елементарној бази.
Најаву предавања и више информација о семинару можете пронаћи на страници семинара:
