КГТА семинар, 23. фебруар 2016.

Наредни састанак Семинара биће одржан у уторак, 23. фебруара 2016. од 14-16h у сали 844 Математичког факултета, V спрат.

Предавач: Жарко Мијајловић

Наслов предавања: СЛУЧАЈНИ ГРАФОВИ И 0-1 ЗАКОН

Апстракт: Теорија случајних графова настала је педесетих и шездесетих година прошлог века у радовима Erdős–Rényi. Мада се ова теорија највећим делом односи на графове, њене методе поред комбинаторике леже у теорији вероватноће и математичкој логици. Циљ предавања је да се изложе основне идеје ове теорије и наведу занимљиви примери. Такође, представићемо конструкцију и особине Радо графа (универзалан пребројив граф) и применом особина ове засићене структуре доказати чувену 0 – 1 теорему (Глебски, Коган, Лиагонки и Таланов [1969], Фагин [1976]): Ако је А својство првог реда у језику теорије графова, тада један од исказа А или ~А важи у скоро свим коначним графовима.