Адрес e-mail:
Прошедшие события
Лекция о моделировании заболеваний ЦНС на рыбках данио-рерио
Панельная онлайн-дискуссия на тему «Новая волна. Акселерация будущего»
Онлайн-собрание ректората и студенческого актива института
AI 2020: технологии, рынок и управление продуктами
Родительское собрание в МФТИ
Летняя онлайн-школа «Всероссийский навигатор абитуриентов МФТИ»
Фазли Атауллаханов: «Физика свертывания крови и COVID-19»
Юрий Яровиков: «Какая математика нужна в анализе данных?»
Михаил Бурцев — об экспериментах с Memory Transformer
Даниил Поляков: «Мощь Python на все случаи жизни»
Презентация магистерской программы «Биоинформатика» ФБМФ и Napoleon IT
Александр Львовский: «Квантовая революция как мировой технологический тренд»
Выпускной МФТИ 2020: онлайн-формат не отменяет праздник
Директор ФИАН Николай Колачевский: «Наука и технологии: путь в лидерство»
Онлайн-презентация кафедры космической физики ЛФИ
Сессия вопросов-ответов с биоинформатиком Антоном Буздиным
Презентация магистерской программы «Физика сверхпроводимости и квантовых материалов»
Презентация магистерской программы «Двумерные материалы: физика и технология наноструктур»
Презентация магистерской программы «Цифровые технологии в бизнесе»
Денис Дмитриев: «Особенности поступления и ответы на вопросы. Приемная кампания — 2020»

Лекция Тобиаса Мюллера: «Logic and random graphs from minor closed classes»

опубликовано: 09.05.2017
tobias.jpgВ рамках еженедельного Математического кружка Физтех-школы прикладной математики и информатики (ФПМИ) лекцию прочтёт доктор наук Тобиас Мюллер (Mathematical Institute of Utrecht University), специалист в области комбинаторики и случайных графов. Тема: «Logic and random graphs from minor closed classes». 

Дата и время: 12 мая в 18:30 в 115 КПМ.

Лекция пройдёт на английском языке.

Abstract

A classical result of Glebskii et al. 1969 and indepently Fagin 1976 states that in the Erdos-Renyi model with edge-probability p=1/2 every graph property that can be expressed as a sentence in first order logic holds with probability tending to either zero or one. 

A class of graphs is minor closed, if it is closed under the operations of removing edges and of "contracting" edges. (An example of a minor closed class of graphs is the class of all graphs that have a crossing-free drawing on some fixed surface S.)

I will discuss a recent work, joint with P. Heinig, M. Noy and A.Taraz, on analogues of the classical result of Glebskii et al./Fagin for random graphs from a minor closed class (i.e. we sample a graph uniformly at random from all graphs on n vertices from some minor closed class).

The proofs build on the major progress that was made in recent years in the study of these random graph models.

За мероприятиями ФПМИ можно следить по ссылке.

Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

© 2001-2020 Московский физико-технический институт (национальный исследовательский университет)

Противодействие коррупции | Сведения о доходах

Политика обработки персональных данных МФТИ

Техподдержка сайта | API

Использование новостных материалов сайта возможно только при наличии активной ссылки на https://mipt.ru

МФТИ в социальных сетях