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

• 22. Фебруар, 2016
• Коментари (0)

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

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

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

Апстракт: Теорија случајних графова настала је педесетих и шездесетих година прошлог века у радовима Erdős–Rényi. Мада се ова теорија највећим делом односи на графове, њене методе поред комбинаторике леже у теорији вероватноће и математичкој логици.

Циљ предавања је да се изложе основне идеје ове теорије и наведу занимљиви примери.

Такође, представићемо конструкцију и особине Радо графа (универзалан пребројив граф) и применом особина ове засићене структуре доказати чувену 0 - 1 теорему (Глебски, Коган, Лиагонки и Таланов [1969], Фагин [1976]):

Ако је А својство првог реда у језику теорије графова, тада један од исказа А или ~А важи у скоро свим коначним графовима.