Закон «нуля или единицы» для случайных графов
Лекция посвящена одному результату (независимо полученному Глебским и др. (1969) и Фагиным (1976)) на стыке теории вероятностей, математической логики и теории игр — закону «нуля или единицы». Формулируется он, в простейшем случае, так: для случайного графа в модели Эрдёша–Реньи с постоянной вероятностью ребра всякое утверждение о графе, выразимое на языке первого порядка, либо асимптотически почти наверное истинно, либо асимптотически почти наверное ложно. (Все эти понятия, разумеется, будут подробно разъяснены на лекции.) Ключевой момент в доказательстве — переход от истинности формул первого порядка к стратегиям в специально подобранных играх на графах (играх Эренфойхта).
Онлайн-курсы по математике
3
Математика для поступающих в 8 класс
Курс поможет ученикам 6−7 классов подготовиться к поступлению в физико-математическую школу. Вы научитесь решать задания из вступительных работ Президентского ФМЛ № 239, ФТЛ им. П. Л. Капицы, школы № 179, лицея «Вторая школа» и ФМШ № 2007.
Бесплатный
Математика: от баллов к знаниям
Если вы абитуриент или студент нематематических специальностей и хотите не завалить сессию, наш курс для вас.
Бесплатный
Алгебра 7 класс
Бесплатные уроки по алгебре для 7 класса, записанные в студии Президентского ФМЛ № 239 для проекта Российская Электронная Школа.
Бесплатный