Логика биномиального случайного графа: формулы с ограниченной кванторной глубиной и ограниченным числом перемен кванторов

В докладе речь пойдёт о логике биномиального случайного графа, а именно обзору цикла результатов об асимптотике вероятностей истинности формул первого порядка с ограниченной кванторной глубиной. Будут упомянуты как прежние результаты, посвящённые законам нуля или единицы для случайного графа G(n,p) с вероятностью проведения ребра p, равной n^{-alpha}, при 0<alpha<1, так и новые результаты, посвящённые случаю alpha>1, а также формулам с ограниченным числом перемен кванторов. В частности, удалось доказать, что наименьшее число перемен кванторов формулы первого порядка с бесконечным спектром равно трём. Под спектром формулы здесь подразумевается множество таких alpha, что вероятность истинности формулы не стремится ни к нулю, ни к единице. Для доказательства законов нуля или единицы при alpha>1 докладчиком получены новые оценки количества классов логической эквивалентности.