Войти
Логин:
Пароль:
Забыли пароль?
научная деятельность
структура институтаобразовательные проектыпериодические изданиясотрудники институтапресс-центрконтакты
русский | english

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

 

Семинар Добрушинской математической лаборатории ИППИ РАН

10 июля, вторник, 16:00, ауд. 307.

Максим Жуковский (МФТИ)
Логика биномиального случайного графа: формулы с ограниченной кванторной
глубиной и ограниченным числом перемен кванторов.

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

    Архив прошедших семинаров Добрушинской лаборатории

08.07.2018 | Комеч Сергей Александрович
 

 

  © Федеральное государственное бюджетное учреждение науки
Институт проблем передачи информации им. А.А. Харкевича Российской академии наук, 2018
Об институте  |  Контакты  |  Старая версия сайта