Seminar za matematičku logiku, 5. februar 2016.

• 01. Februar,  2016
• Komentari (0)

Prvi sastanak Seminara u letnjem semestru biće održan u petak, 5. februara 2016. u sali 301f Matematičkog instituta SANU sa početkom u 16:15 časova.

Predavač: Žarko Mijajlović

Naslov predavanja: Slučajni grafovi i 0-1 zakon

Apstrakt: Teorija slučajnih grafova nalazi se na tromeđi kombinatorike, teorije verovatnoće i matematičke logike.

Ova teorija nastala je šezdesetih godina prošlog veka u radovima Erdős–Rényi.

Cilj predavanja je da se izlože osnovne ideje ove teorije, predstave konstrukcija i osobine Rado grafa (univerzalan homogen prebrojiv graf) i primenom ovih osobina dokaže čuvena 0-1 teorema (GKLT[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.

---