Теория Рамсея
Теория Рамсея изучает, как полный беспорядок становится невозможным: любая достаточно большая структура должна содержать высокоорганизованную подструктуру.
Definition
Раздел комбинаторики, изучающий, насколько большой должна быть структура, чтобы гарантировать, что любое её разбиение или раскраска приводит к монохроматической или иным образом заданной подструктуре.
Scope
Эта область охватывает теорему Рамсея для графов и гиперграфов и её количественные числа Рамсея, результаты разбиения для целых чисел, такие как теоремы Шура, ван дер Вардена и Хейлса-Джуэтта, а также абстрактную структурную теорию Рамсея параметрических множеств. Она иллюстрирует экстремально-комбинаторный принцип, согласно которому достаточно большие системы не могут избежать порядка.
Sub-topics
Core questions
- Насколько большой должна быть структура, чтобы принудительно содержать неустранимую упорядоченную подструктуру?
- Каковы точные или приблизительные пороговые значения, числа Рамсея, для этих гарантий?
- Как теоремы о разбиении для целых чисел гарантируют арифметические закономерности?
- Какие абстрактные семейства структур обладают свойством Рамсея?
Key concepts
- Теорема Рамсея
- Числа Рамсея
- Монохроматические подструктуры
- Теорема ван дер Вардена
- Теорема Шура
- Теорема Хейлса-Джуэтта
Clinical relevance
Гарантии неустранимой структуры типа Рамсея используются в аргументах нижних границ в теоретической информатике, анализе больших сетей и аддитивной теории чисел, в то время как разрыв между известными границами стимулирует развитие вероятностного метода.
History
Теорема Фрэнка Рамсея 1930 года о разбиениях, первоначально доказанная для вопроса в логике, была признана Эрдошем и Секерешем как основа широкой теории неустранимой структуры, которая развивалась на протяжении XX века.
Key figures
- Frank Ramsey
- Paul Erdos
- Bartel van der Waerden
Related topics
Seminal works
- graham1990
- landman2003
Frequently asked questions
- Каков лозунг теории Рамсея?
- Полный беспорядок невозможен: любая достаточно большая система, как бы она ни была устроена, должна содержать значительную упорядоченную часть.
- Почему числа Рамсея трудно вычислить?
- Количество раскрасок для проверки растёт астрономически, и даже малые числа Рамсея, такие как R(5,5), остаются неизвестными, несмотря на интенсивные усилия.