Андрей Михайлович Райгородский

Линейно-алгебраические и вероятностные методы в комбинаторике

А.М.Райгородский планирует провести 4 занятия.

Лекция 1.: Рассмотрим простой пример. Пусть R_n={1,...,n}, M={M₁,...,M_s} — совокупность некоторых подмножеств R_n, причем M_i∩M_j≠∅ для любых i, j. Спрашивается, насколько большой при данном ограничении может оказаться M? Задачи подобного типа называются экстремальными задачами теории гиперграфов с запретами на мощности пересечения ребер (M — гиперграф). В лекции будут изложены основы двух мощных методов решения подобных задач — вероятностного и линейно-алгебраического. С помощью этих методов будут доказаны теоремы Эрдеша-Ко-Радо, Франкла-Уилсона, Алсведе-Хачатряна и др.
Лекция 2.: Сперва мы рассмотрим нетривиальные обобщения задач из первой лекции на случай векторов в пространстве. Теперь мы будем говорить не о совокупностях множеств с запретами на мощности пересечения, а о системах векторов с запретами на скалярные произведения. С помощью линейно-алгебраического метода мы докажем несколько важных результатов относительно мощностей упомянутых систем. Затем мы применим полученные результаты к двум классическим проблемам комбинаторной геометрии — проблеме Борсука и проблеме о хроматическом числе пространства (в первом случае речь пойдет о разбиении множеств на части меньшего диаметра, во втором — о раскраске пространства без одноцветных точек на расстоянии 1).
Лекция 3.: В этой лекции мы поговорим еще об одном классическом понятии комбинаторики — а именно, о числе Рамсея R(s,t). Сначала мы применим различные вероятностные методы к отысканию нетривиальных оценок величины R(s,t). Проблема будет состоять, однако ж, в том, что все оценки, которые мы таким способом найдем, окажутся, конечно, неконструктивными. И одна весьма изящная модификация линейно-алгебраического подхода позволит нам эту проблему устранить.
Лекция 4.: В этой лекции мы вернемся к изучению гиперграфов. На сей раз мы станем раскрашивать множества их вершин в два цвета, стараясь добиться того, чтобы разница между количествами вершин первого и второго цветов в каждом из ребер была как можно меньше. Сочетание вероятностных и линейно-алгебраических методов поможет нам достичь весьма существенных успехов на этом пути. Будут, в частности, доказаны теоремы Спенсера и Бека-Фиалы.