Теория Рамсея: Порядок в неизбежном хаосе
В 1930 году выдающийся британский математик и философ Фрэнк Пламптон Рамсей опубликовал работу, которая породила совершенно новый раздел комбинаторики. Теория Рамсея изучает условия, при которых в достаточно большой структуре (например, графе или последовательности чисел) с математической неизбежностью возникает определенный порядок, как бы мы ни пытались этот порядок разрушить. Девиз этой теории можно сформулировать так: «Абсолютный хаос невозможен».
Самым популярным введением в теорию Рамсея является Задача о знакомствах (Party problem). Она звучит так: какое минимальное количество людей нужно собрать на вечеринке, чтобы среди них гарантированно нашлись либо трое попарно знакомых друг с другом, либо трое попарно незнакомых? Теория доказывает, что ответ равен ровно 6. Если перевести это на язык теории графов: если ребра полного графа на шести вершинах раскрасить в два цвета (например, красный для знакомых и синий для незнакомых), то в графе обязательно возникнет одноцветный треугольник.
Это число 6 обозначается как число Рамсея R(3,3). С увеличением размеров искомых структур вычисление чисел Рамсея становится невероятно сложной задачей. Например, точное значение R(4,4) было найдено и равно 18. А вот точное значение R(5,5) неизвестно до сих пор! Математикам удалось лишь установить границы: оно находится где-то между 43 и 48. Как однажды заметил Пал Эрдёш, если инопланетяне потребуют от землян вычислить R(5,5) под угрозой уничтожения планеты, мы должны бросить все вычислительные мощности Земли на эту задачу. Но если они потребуют R(6,6) — нам лучше сразу начать превентивную войну, потому что вычислить его невозможно в принципе (из-за комбинаторного взрыва).
Помимо графов, теория Рамсея применяется к числам (Теорема Ван дер Вардена об арифметических прогрессиях в раскрашенных целых числах) и геометрии. В информатике и теории сложности вычислений результаты Рамсея применяются для нижних оценок структур данных и алгоритмов сортировки. Если мы знаем, что в любом достаточно большом наборе данных неизбежно существуют упорядоченные подструктуры, мы можем алгоритмически опираться на этот факт для оптимизации поиска, построения хеш-таблиц и анализа сложных телекоммуникационных сетей.
