Какое математическое доказательство связано с числом Грэма?

Теорема Грэма–Ротшильда о теории слов-параметров Рамсея связана с числом Грэма. en.wikipedia.org

Суть задачи: соединить каждую пару геометрических вершин n-мерного гиперкуба, чтобы получить полный граф из 2n вершин. en.wikipedia.org Раскрасить каждое из рёбер этого графа красным или синим цветом. en.wikipedia.org Нужно определить, при каком наименьшем значении n каждая такая раскраска содержит по крайней мере один одноцветный полный подграф в четырёх копланарных вершинах. en.wikipedia.org

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

Грэм доказывал в другую сторону: «Если размерность куба не меньше G, обязательно найдётся одноцветный планарный граф на четырёх вершинах». yandex.ru

Пользователь

Время добавления