Экстремальная комбинаторика

Задачи об экстремуме

Экстремальная комбинаторика: как велик или мал может быть объект с заданными свойствами?

Теорема Турана: Максимальное число рёбер в K_{r+1}-свободном графе на n вершинах: e ≤ (1 − 1/r)·n²/2. Достигается на полном r-дольном графе Турана T(n,r).

Задача Эрдёша о числе расстояний: n точек на плоскости определяют ≥ c√n различных расстояний.

Принцип Дирихле (ящиков)

Если n предметов разложить в m ящиков и n > m, то в каком-то ящике окажется ≥ 2 предметов.

Обобщение: если n > km, то в каком-то ящике ≥ k+1.

Применение: среди 13 человек двое родились в один месяц. Среди 367 — двое в один день. Задача о 5 точках в единичном квадрате: двое на расстоянии ≤ √2/2.

Разбиваем квадрат на 4 части; если n=5 точек → хотя бы 2 в одной части → расстояние ≤ диагональ части = √2/2.

Теоремы Рамсея и Гельфанда

Ван дер Варден: Для любых k и r существует N такое, что при любой r-раскраске {1,...,N} есть одноцветная k-членная арифметическая прогрессия.

Теорема Хинчина: При любой двухцветной раскраске натуральных чисел одноцветное множество содержит бесконечно много k-членных АП.

Эти теоремы показывают: в больших структурах неизбежно возникают регулярные паттерны.

Теорема Грина-Тао и простые числа в АП

В 2004 году Бен Грин и Терренс Тао доказали: простые числа содержат арифметические прогрессии любой длины. Доказательство сочетает метод Сцемереди о регулярности (для структурных аргументов) и теорию простых чисел (для оценок плотности псевдослучайных множеств). Это один из величайших результатов XXI века в математике.

Числа Ван дер Вардена и вычислительная сложность: Вычисление W(2;k) — задача с феноменально сложным поведением. W(2;3)=9 (три цвета на 8 чисел без монохромной АП-3). W(2;4)=35, W(2;5)=178, W(2;6)=1132. Рост чрезвычайно быстрый: верхние оценки Гауэрса имеют вид башенных функций (тетрация вида 2^{2^{...^2}}). Сама функция W(r;k) является примитивно-рекурсивной и вычислима, однако практически недостижима для больших k.

Ультраметрика и метрические результаты Рамсея

Ультрафильтры применяются в доказательствах бесконечных версий теоремы Рамсея: компактность пространства ультрафильтров (теорема Тихонова) даёт элегантные нефинитные доказательства. Для метрических пространств существуют аналоги теоремы Рамсея: в любом достаточно большом конечном метрическом пространстве есть большое приблизительно равноудалённое подмножество. Применение в компьютерном зрении (инварианты к деформациям) и базах данных (метрическая кластеризация).

Полихроматические числа Рамсея

Многоцветные числа Рамсея: В отличие от двухцветных, многоцветные варианты значительно сложнее. R(3,3,3) = 17: при трёхцветном рёбер-раскрашивании K₁₇ есть монохромный треугольник. Значение R(3,3,3,3) неизвестно. Размерные числа Рамсея: при каком n-мерном пространстве любая раскраска точек содержит монохромное регулярное многомерное тело? Это активная область исследований.

Комбинаторные игры и теорема Хекса

Игра Хекс на n×n доске — первый игрок (соединяющий левый-правый края) выигрывает при оптимальной игре. Доказательство стратегии украдения (strategy stealing): если бы второй игрок имел выигрышную стратегию, первый мог бы её «украсть». Существование выигрышной стратегии для первого игрока — но построить её конструктивно для больших n — открытая задача. Хекс связан с теоремой Брауэра о неподвижной точке: существование выигрышного пути эквивалентно неподвижной точке непрерывного отображения симплекса.

Теория игр и комбинаторные игры: числа Гранди

Числа Гранди (Nim-значения): G(позиция) = mex{G(p') : p' — следующая позиция}. mex — минимальный исключённый неотрицательный. Теорема Шпрага-Грунди: любая комбинаторная игра эквивалентна нимбу G(позиция). Сумма игр: G(G₁+G₂) = G₁⊕G₂ (XOR). Применение: Ним, Гозинток (Hackenbush), Топпинг.

Алфавитные игры и коды

Игра-угадайка: бинарный поиск — стратегия минимального числа вопросов. Связь с кодом: оптимальное дерево вопросов = оптимальный префиксный код. Игра Ульяма (20 Questions with Lies): допускаем k лжецов — оптимальная стратегия через коды с исправлением k ошибок. Комбинаторная игра Браузера: выигрышная стратегия эквивалентна хроматическому числу некоего графа.

Детерминированные клеточные автоматы

Клеточные автоматы (КА): дискретная модель вычислений. Ряд клеток, каждая в состоянии из конечного алфавита. Переход: новое состояние = f(состояния соседей). Правило 30 (Вольфрам): из простых правил — сложное хаотическое поведение. Правило 110 — Тьюринг-полный КА (доказательство Мэтью Кука, 1994). Игра «Жизнь» Конвея — двумерный КА: сложные структуры (глайдеры, осцилляторы), Тьюринг-полная.

Теорема монотонных функций и вероятностная комбинаторика

Монотонное свойство графа G (добавление рёбер не уничтожает свойство, например, содержать клику) имеет пороговую функцию p*(n). Теорема Фридгута-Кана: если свойство «симметричное» (инвариантно под автоморфизмами Kₙ), то порог остр. Это объясняет «пороги» в G(n,p) — свойство появляется внезапно. Нечёткие пороги: примеры существуют для несимметричных свойств.

Теорема Рамсея для гиперграфов

Обобщение: для k-однородных гиперграфов на R^(k)(s,t) вершинах любая двухцветная раскраска k-подмножеств содержит монохромное s- или t-подмножество. Числа Рамсея для гиперграфов растут вдвойне-экспоненциально. R^(3)(4,4) не известно точно. Теорема Грэхема-Ротшильда: комбинаторные кубы содержат монохромные аффинные подпространства — количественная версия теоремы Хиндмана.

Численный пример: число Рамсея R(3,3)=6

Задача: Доказать R(3,3) ≤ 6: любое двухцветное рёбер-раскрашивание K₆ содержит монохромный треугольник.

Шаг 1: Возьмём произвольную вершину v в K₆. Она соединена с 5 другими вершинами рёбрами двух цветов.

Шаг 2: По принципу Дирихле: из 5 рёбер хотя бы ⌈5/2⌉=3 одного цвета. Пусть v соединена красными рёбрами с вершинами a, b, c.

Шаг 3: Смотрим на треугольник {a,b,c}. Если ребро ab, bc или ac красное → красный треугольник с v. Если все три ребра синие → {a,b,c} сами образуют синий треугольник.

Шаг 4: Оба случая дают монохромный треугольник. Нижняя оценка: K₅ с «пятиугольной» раскраской (5 рёбер цикла = красные, 5 диагоналей = синие) не содержит монохромного треугольника → R(3,3) > 5. Итого R(3,3) = 6. ✓