Логика биномиального случайного графа

В докладе речь пойдет о свойствах биномиального случайного графа (или, как его часто называют, случайного графа Эрдеша–Реньи), выразимых на формальных языках первого и второго порядка. К свойствам, выразимым на языке первого порядка, например, относятся свойство содержать треугольник и свойство быть полным. А к свойствам, выразимым на языке второго порядка, например, относятся свойство связности и свойство иметь четное число вершин. Изучением вероятностей подобных свойств занимались с момента зарождения науки о случайных графах, которым можно считать основоположную статью Эрдеша и Реньи 1960-го года. В 2001 году свет увидела книга Дж. Спенсера «Strange logic of random graphs», содержащая обзор известных к тому моментов результатов о вероятностях свойств первого порядка случайного графа. Классический результат в этой области носит название закона нуля или единицы, который утверждает, что вероятность любого свойства первого порядка стремится либо к нулю, либо к единице. Эта теорема была впервые доказана в 1969 году Глебским, Коганом, Лиогоньким и Талановым (а позже независимо в 1976 году Фагиным). Разумеется, с 2001 года наука не стояла на месте – были получены новые результаты, касающиеся не только свойств первого порядка, но и свойств второго порядка, и был сформулирован ряд гипотез, которые остаются открытыми до сих пор.