Регулярность разбиений и структурная теория Рамсея

Структурная теория Рамсея показывает, что всякий раз, когда целые числа или другие богатые структуры разбиваются на конечное число классов, один класс должен содержать предписанные арифметические или комбинаторные паттерны.

Definition

Система или паттерн является регулярным относительно разбиения, если для каждого разбиения базового множества на конечное число классов по крайней мере один класс содержит решение или экземпляр паттерна; структурная теория Рамсея изучает, какие паттерны обладают этим свойством.

Scope

Эта тема охватывает регулярность разбиений на множестве целых чисел — теорему Шура, теорему ван дер Вардена о монохроматических арифметических прогрессиях и характеризацию Радо уравнений, регулярных относительно разбиений, — а также теорему Хейлса-Джуэтта, результат об абстрактных комбинаторных линиях, из которого следуют многие из этих утверждений. Она помещает теорию Рамсея в контекст аддитивной комбинаторики.

Core questions

• Какие арифметические паттерны должны появляться в некотором классе любого конечного раскрашивания целых чисел?
• Когда линейное уравнение имеет монохроматическое решение при любом раскрашивании?
• Как теорема Хейлса-Джуэтта объединяет эти результаты о разбиениях?
• Как эти результаты связаны с плотностями и аддитивной комбинаторикой?

Key concepts

• Регулярность разбиений
• Теорема Шура
• Теорема ван дер Вардена
• Теорема Радо
• Теорема Хейлса-Джуэтта
• Комбинаторные линии

Key theories

Теорема ван дер Вардена

Для любого числа цветов и любой целевой длины существует целое число N такое, что любое раскрашивание целых чисел от единицы до N содержит монохроматическую арифметическую прогрессию этой длины.

Теорема Хейлса-Джуэтта

В многомерном комбинаторном кубе над фиксированным алфавитом любое конечное раскрашивание содержит монохроматическую комбинаторную линию, что является главной теоремой, подразумевающей теорему ван дер Вардена и многие другие результаты о разбиениях.

Clinical relevance

Эти результаты о регулярности разбиений являются краеугольными камнями аддитивной комбинаторики и теории чисел, связываясь с теоремой Семереди об арифметических прогрессиях и теоремой Грина-Тао о простых числах, и они информируют аргументы «структура против случайности» во всей математике.

History

Теорема Шура 1916 года и теорема ван дер Вардена 1927 года об арифметических прогрессиях положили начало теории разбиений целых чисел, которую систематизировал Радо, а теорема Хейлса-Джуэтта 1963 года абстрактно объединила.

Key figures

• Bartel van der Waerden
• Issai Schur
• Richard Rado

Seminal works

• graham1990
• landman2003

Frequently asked questions

Что гарантирует теорема ван дер Вардена?

Как бы ни были разбиты целые числа до некоторой большой границы на несколько цветовых классов, один класс обязательно будет содержать равномерно распределенную последовательность любой желаемой длины.

Почему теорема Хейлса-Джуэтта называется главной теоремой?

Потому что теорема ван дер Вардена и несколько других результатов о разбиениях следуют как частные случаи ее утверждения о монохроматических комбинаторных линиях.