Логика случайного графа: от законов нуля или единицы до приложений

С 1960 года после выхода основоположной статьи Эрдеша и Реньи огромное количество работ было посвящено изучению свойств случайного графа. Значительная часть этих работ посвящена свойствам графов, описываемым на языке первого порядка и монадическом языке второго порядка. К таким свойствам можно отнести, например, свойство содержать треугольник, свойство содержать изолированную вершину и свойство связности. В 2001 году свет увидела книга Дж. Спенсера "Strange logic of random graphs", содержащая обзор известных к тому моменту результатов о вероятностях свойств первого порядка случайного графа. Классический результат в этой области носит название закона нуля или единицы, который утверждает, что вероятность любого свойства первого порядка стремится либо к нулю, либо к единице. Разумеется, с 2001 года наука не стояла на месте — были получены новые результаты, касающиеся не только свойств первого порядка, но и монадических свойств. Более того, эти результаты нашли свое применение в задачах оценивания описательной сложности графовых свойств, решение которых, в свою очередь, позволяет находить новые алгоритмы проверки этих свойств.