Экстремальная комбинаторика и случайные графы

Одно из классических утверждений экстремальной комбинаторики — это теорема Эрдеша-Ко-Радо 1961 года, которая устанавливает размер наибольшей совокупности попарно пересекающихся $k$-элементных подмножеств $n$-элементного множества. В докладе мы расскажем об истории проблематики, возникшей в связи с этой теоремой. Мы покажем, что эта проблематика находится в самом центре современного комбинаторного анализа, продемонстрируем ее связи с теорией кодирования, комбинаторной геометрией, алгебраической топологией. Особое внимание мы уделим недавней вероятностной интерпретации задачи — в терминах теории случайных графов.