Семинар за рачунарство и примењену математику, 12. март 2019.

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

Предавач: Лука Милићевић, Математички институт САНУ

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

Апстракт: Позната теорема Грејема и Полака тврди да не постоји партиција комплетног графа на $n$ чворова у мање од $n-1$ комплетних бипартитних графова. Природно уопштење овог тврђења за случај $r$-графова је следеће питање: колики је најмањи природан број $f_r(n)$ такав да се комплетан $r$-граф на $n$ чворова може поделити у $f_r(n)$ комплетних $r$-партитних $r$-графова? Алон је 1986. године показао да важи $f_3(n) = n-2$, и да за $r > 3$ важи $A_r n^{\lfloor \frac{r}{2} \rfloor} \leq f_r(n)\leq B_r n^{\lfloor \frac{r}{2} \rfloor}$, за неке позитивне константе $A_r < B_r$. Оцене за $f_r$ нису имале асимптотска побољшања од тог резултата. У овом предавању, биће разматран случај 4-графова и неки повезани проблеми.


Оставите ваш коментар:


(опционо)
(неће бити приказано)



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


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

све вести