Семинар за математичку логику, 5. фебруар 2016.
- 01. Фебруар, 2016
- Коментари (0)
Први састанак Семинара у летњем семестру биће одржан у петак, 5. фебруара 2016. у сали 301ф Математичког института САНУ са почетком у 16:15 часова.
Предавач: Жарко Мијајловић
Наслов предавања: Случајни графови и 0-1 закон
Апстракт: Теорија случајних графова налази се на тромеђи комбинаторике, теорије вероватноће и математичке логике.
Ова теорија настала је шездесетих година прошлог века у радовима Erdős–Rényi.
Циљ предавања је да се изложе основне идеје ове теорије, представе конструкција и особине Радо графа (универзалан хомоген пребројив граф) и применом ових особина докаже чувена 0-1 теорема (GKLT[1969], Fagin[1976]):
Ако је А својство првог реда у језику теорије графова, тада један од исказа А или ~А важи у скоро свим коначним графовима.
Коментари(0)