Числа Рамсея.

Число Рамсея R(k, m) это наименьшее число n такое, что в любом графе с n вершинами, найдутся либо k попарно смежных, либо m попарно несмежных.

Теорема Рамсея гарантирует существование чисел Рамсея для любых k и m. Таким образом можно говорить о содержании в бесконечном графе высокоорганизованной структуры любой сложности. Но об этом позже (быть может). А пока хочется остановиться на числах Рамсея. Для удобства перефразируем определение:
Число Рамсея R(k, m) это наименьшее число n такое, что в любом полном графе с n вершинами, ребра которого раскрашены в красный и синий цвета, найдется либо подграф с k вершинами, все ребра которого окрашены в красный цвет, либо подграф с m вершинами, все ребра которого окрашены в синий цвет.
Чтобы понять сложность вычисления чисел Рамсея, то следует отметить что число R(5, 5) до сих пор не найдено.
Можно заметить три очевидных факта, касающихся чисел Рамсея:

1. R(k, m) = R(m, k)

2. R(1, m) = 1

3. R(2, m) = m

Остальные числа вычисляются индивидуально.

Задача о вычислении R(3, 3) известна как "задача о вечеринке": среди любых 6 человек найдется либо 3 попарно знакомых, либо 3 попарно незнакомых. Другими словами R(3, 3) <= 6. Доказательство строится следующим образом (в терминах второго приведенного определения):
Изобразим граф с шестью вершинами и возьмем одну из них - A:

Вершина A соединена с пятью другими вершинами (красными и синими ребрами). Без ограничения общности можно считать, что она соединена красными ребрами по крайней мере с тремя вершинами - B, C, D. Далее, если одно из ребер BC, CD, BD красное (например BC), то имеем красный треугольник (ABC). Если же все они синие, то BCD - синий треугольник. Конец доказательства.
Имея в виду то, что число 5 не удовлетворяет требованиям задачи, получаем R(3, 3) = 6.
Дальше докажем, что R(3, 4) = 9. Сначала установим, что R(3, 4) > 8. Для этого достаточно привести пример раскраски графа из 8 вершин, не содержащего красных треугольников и полных синих подграфов из 4 вершин:

Осталось доказать, что полный граф из 9 вершин так раскрасить нельзя. Допустим, такая раскраска возможна. Будем рассуждать как в предыдущем доказательстве. Возьмем одну из вершин (A), с остальными вершинами она соединена 8 ребрами. Пусть k из них покрашены в красный цвет, а остальные 8-k - в синий.
Если k >= R(2, 4) = 4, то A соединена красными ребрами хотя бы с четырьмя вершинами (B, C, D, E). Если две из этих вершин соединены красным ребром, то сразу имеем красный треугольник, а если нет, то BCDE - полный синий граф из четырех вершин. Значит k < 4.
Аналогичным образом 8-k < R(3, 3) = 6.
Из этих двух неравенств имеем (k < 4) && (k > 2) => k = 3.
Так как наши рассуждения не зависят от выбора вершины, то можно утверждать, что из любой вершины выходит ровно три красных ребра, а значит общее число красных ребер в графе равно 3 * 9 / 2. Но это число не является целым, мы пришли к противоречию. Следовательно требуемой раскраски не существует и R(3, 4) = 9. Конец доказательства.

P.S. Данное доказательство пока не слишком сложное, но все же сложнее вычисления R(3, 3). Для больших параметров доказательства значительно усложняются. Дело в том, что не существует системного метода поиска чисел Рамсея (есть только грубые оценки), а с ростом параметров начинается очень обширное комбинаторное многообразие, не позволяющее найти решение даже компьютеру...

P.P.S. Практического применения чисел Рамсея нет, но в процессе их поиска было разработано масса полезного инструментария как в теории графов, так и в смежных областях.