KGTA seminar, 23. februar 2016.

• 22. Februar,  2016
• Komentari (0)

Naredni sastanak Seminara biće održan u utorak, 23. februara 2016. od 14 do16 sati u sali 844 Matematičkog fakulteta, V sprat.

Predavač: Žarko Mijajlović

Naslov predavanja: SLUČAJNI GRAFOVI I 0-1 ZAKON

Apstrakt: Teorija slučajnih grafova nastala je pedesetih i šezdesetih godina prošlog veka u radovima Erdős–Rényi. Mada se ova teorija najvećim delom odnosi na grafove, njene metode pored kombinatorike leže u teoriji verovatnoće i matematičkoj logici.

Cilj predavanja je da se izlože osnovne ideje ove teorije i navedu zanimljivi primeri.

Takođe, predstavićemo konstrukciju i osobine Rado grafa (univerzalan prebrojiv graf) i primenom osobina ove zasićene strukture dokazati čuvenu 0 - 1 teoremu (Glebski, Kogan, Liagonki i Talanov [1969], Fagin [1976]):

Ako je A svojstvo prvog reda u jeziku teorije grafova, tada jedan od iskaza A ili ~A važi u skoro svim konačnim grafovima.

---