Seminar za računarstvo i primenjenu matematiku, 12. mart 2019.

Naredni sastanak Seminara biće održan u utorak, 12. marta 2019. u sali 301f Matematičkog instituta SANU sa početkom u 14:15.

Predavač: Luka Milićević, Matematički institut SANU

Naslov predavanja: DEKOMPOZICIJE KOMPLETNIH HIPERGRAFOVA

Apstrakt: Poznata teorema Grejema i Polaka tvrdi da ne postoji particija kompletnog grafa na $n$ čvorova u manje od $n-1$ kompletnih bipartitnih grafova. Prirodno uopštenje ovog tvrđenja za slučaj $r$-grafova je sledeće pitanje: koliki je najmanji prirodan broj $f_r(n)$ takav da se kompletan $r$-graf na $n$ čvorova može podeliti u $f_r(n)$ kompletnih $r$-partitnih $r$-grafova? Alon je 1986. godine pokazao da važi $f_3(n) = n-2$, i da za $r > 3$ važi $A_r n^{lfloor frac{r}{2} floor} leq f_r(n)leq B_r n^{lfloor frac{r}{2} floor}$, za neke pozitivne konstante $A_r < B_r$. Ocene za $f_r$ nisu imale asimptotska poboljšanja od tog rezultata. U ovom predavanju, biće razmatran slučaj 4-grafova i neki povezani problemi.



Nažalost nije moguće ostaviti komentar.