На главную страницу НМУ

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

Основы теории Рамсея и регулярность в комбинаторике-I

1.Простейшие примеры задач "рамсеевского" типа.

2.Основные инструменты, используемые для решения задач теории Рамсея.

2.1Вероятностный метод: линейность математического ожидания, локальная лемма Ловаса, альтернирование и пр.

2.2Линейно-алгебраический метод: теоремы Франкла - Уилсона, "combinatorial Nullstellensatz" и пр.

2.3Лемма регулярности Семереди.

2.4Метод тригонометрических сумм. Круговой метод.

3.Рамсеевские задачи в теории графов и гиперграфов.

3.1Теорема Рамсея.

3.2Числа Рамсея. Верхние и нижние оценки.

3.3Конструктивные нижние оценки для чисел Рамсея. Полиномиальные алгоритмы построения рамсеевских графов.

3.4Обобщения чисел Рамсея. Связь с проблемами "турановского" типа в комбинаторике.

4.Рамсеевские задачи в геометрии.

4.1"Евклидова" теория Рамсея.

4.2Рамсеевские и гиперрамсеевские множества в пространствах.

4.3Раскраски метрических пространств и их подмножеств.

4.4Проблемы Эрдеша - Секереша.

4.5Различные аналоги обобщенных чисел Рамсея в геометрии.


Rambler's Top100