Семинар за рачунарство и примењену математику, 3. април 2018.

Наредни састанак Семинара биће одржан у уторак, 3. априла 2018. у сали 301ф Математичког института САНУ са почетком у 14:15 часова.

Предавач: Бојан Вучковић, Математички институт САНУ

Наслов предавања: НОВЕ КОМБИНАТОРНЕ КОНСТРУКЦИЈЕ У ВЕЗИ СА ПРОБЛЕМИМА ИЗ ХРОМАТСКЕ ТЕОРИЈЕ ГРАФОВА, ЕКСТРЕМАЛНЕ ТЕОРИЈЕ СКУПОВА И ТЕОРИЈЕ БУЛОВИХ МАТРИЦА

Апстракт: Последњих деценија уведени су и изучавани нови типови бојења графова - такозвана индукована бојења. То су, не обавезно ваљана, бојења грана или грана и чворова графа код којих се боја чвора изводи из боја њему инцидентних грана и суседних чворова. Бојења се најчешће изводе по суми или по скупу, при чему постоји услов да свака два суседна чвора имају различите изведене вредности. Биће приказане дефиниције разних врста индукованог бојења графа, хипотезе по питању потребног броја боја да би се извело тражено бојење за произвољан граф, као и резултати излагача. Код многих од ових типова бојења постигнути резултати су још увек далеко од претпостављених горњих граница формулисаних у хипотезама, и остављају простора за даље унапређивање.

Франклова хипотеза из екстремалне теорије скупова тврди да у свакој коначној фамилији затвореној за унију постоји елемент који се појављује у барем половини скупова фамилије. Овај наизглед једноставан проблем, формулисан 1979. године, је још увек отворен. По питању Франклове хипотезе постоје докази парцијалних резултата.

Биће дат приказ резултата излагача да је Франклова хипотеза задовољена за фамилије састављене од 12 или мање елемената, као и подела фамилија састављених од 6 или мање елемената на такозване FC и NonFC фамилије.

Булове матрице су матрице код којих су сви елементи из скупа {0, 1}. Простор врста Булових матрица је скуп вектора који се могу добити унијом врста дате матрице, док је кардиналност простора врста матрице кардиналност овога скупа. Разматрано је питање за које вредности c из скупа {1,...,2^n} постоји матрица А димензије nxn таква да је кардиналност простора врста матрице А једнака c.


Нажалост није могуће оставити коментар.

Вести и дешавања


Активности на семинарима

све вести