Что такое теория Рамсея: определение термина
В теории Рамсея рассматривают конечные или бесконечные множества, графы, таблицы, разбиения и раскраски. Идея простая: если структура достаточно большая, то как бы вы ни «перемешивали» ее элементы, внутри все равно появится упорядоченный фрагмент.
Часто это формулируют через раскраску ребер графа в несколько цветов и поиск одноцветной подструктуры. Такие утверждения называют теоремами Рамсея, а минимальные размеры, которые гарантируют результат, называют числами Рамсея. Обычно их трудно вычислять точно, поэтому важны оценки и границы.
Простой пример идеи теории Рамсея
Классический пример — задача про компанию людей. Если в комнате 6 человек, то среди них обязательно найдутся либо трое, которые попарно знакомы, либо трое, которые попарно незнакомы. Это факт записывают как R(3,3)=6. Здесь «знакомы» и «незнакомы» можно считать двумя цветами ребер между людьми.
Теория Рамсея говорит, что при росте числа участников такие гарантированные группы возникают неизбежно, даже если связи выглядят случайными. Именно поэтому ее иногда описывают как поиск «порядка в хаосе».
