А.М.Райгородский

Вероятностные методы в комбинаторике-II

Спецкурс посвящен одному из самых красивых и современных разделов комбинаторного анализа. Несмотря на то, что в конечном счете будет изложена весьма нетривиальная вероятностно-комбинаторная техника, спецкурс будет доступен первокурсникам. Он служит продолжением одноименного спецкурса осеннего семестра, однако большинство тем будет понятно и новым слушателям!

Программа курса:

1. Неравенство Талаграна. Применения в задачах о раскраске графов, а также в теории алгоритмов.
2. Энтропия и раскраски гиперграфов.
3. Вероятность в комбинаторной геометрии.
4. Ветвящиеся процессы и связность случайного графа.
5. Размерность Вапника Червоненкиса в комбинаторной геометрии и математической статистике.
6. Случайные веб-графы.