Семинар Добрушинской математической лаборатории ИППИ РАН
10 июля, вторник, 16:00, ауд. 307.
Максим Жуковский (МФТИ)
Логика биномиального случайного графа: формулы с ограниченной кванторной
глубиной и ограниченным числом перемен кванторов.
Аннотация:
В докладе речь пойдёт о логике биномиального случайного графа, а именно обзору
цикла результатов об асимптотике вероятностей истинности формул первого порядка
с ограниченной кванторной глубиной. Будут упомянуты как прежние результаты,
посвящённые законам нуля или единицы для случайного графа G(n,p) с
вероятностью проведения ребра p, равной n^{-alpha}, при 0<alpha<1, так и новые
результаты, посвящённые случаю alpha>1, а также формулам с ограниченным числом перемен
кванторов. В частности, удалось доказать, что наименьшее число перемен
кванторов формулы первого порядка с бесконечным спектром равно трём. Под спектром
формулы здесь подразумевается множество таких alpha, что вероятность истинности
формулы не стремится ни к нулю, ни к единице.
Для доказательства законов нуля или единицы при alpha>1 докладчиком получены
новые оценки количества классов логической эквивалентности.
Архив прошедших семинаров Добрушинской лаборатории
08.07.2018 | Комеч Сергей Александрович |