Закон «нуля или единицы» для случайных графов

Лекция посвящена одному результату (независимо полученному Глебским и др. (1969) и Фагиным (1976)) на стыке теории вероятностей, математической логики и теории игр — закону «нуля или единицы». Формулируется он, в простейшем случае, так: для случайного графа в модели Эрдёша–Реньи с постоянной вероятностью ребра всякое утверждение о графе, выразимое на языке первого порядка, либо асимптотически почти наверное истинно, либо асимптотически почти наверное ложно. (Все эти понятия, разумеется, будут подробно разъяснены на лекции.) Ключевой момент в доказательстве — переход от истинности формул первого порядка к стратегиям в специально подобранных играх на графах (играх Эренфойхта).