Что такое число Грэма и как оно связано с теорией Рамсея?

Число Грэма — гигантское число, которое является верхней границей для решения определённой проблемы в теории Рамсея 12.

Оно является некоторой очень большой степенью тройки, которая записывается с помощью нотации Кнута 1. Названо в честь Рональда Грэма 1.

Связь с теорией Рамсея заключается в следующей задаче 4:

Представим себе N-мерный куб, его вершины в случайном порядке соединены красными или синими отрезками-линиями 4. Задача — понять, до какого значения N возможно (если по-разному закрашивать рёбра куба), избежать ситуации, при которой одна плоскость в кубе будет окрашена одним цветом 4. То есть не должен получиться одноцветный «конвертик» 4.

Грэм и Ротшильд в 1971 году доказали, что эта проблема имеет решение, и оно представляет собой число, которое больше 6 (нижняя граница), и меньше некоего N 5. Нижняя граница впоследствии была повышена до 13, а верхняя граница получила название малого числа Грэма 5.