 |
Число ГрэмаЧисло Грэма является верхней границей на решение определённой проблемы в теории Рамсея, а именно: Рассмотрим n-мерный гиперкуб и соединим все пары вершин для получения полного графа с Гиперкуб - это ясно что такое, см. статью про Гиперкубы. Полный граф - фигура, полученная при соединении всех вершин гиперкуба между собой. Полный подграф, который нам нужен, или подграф K4 ,выглядит как квадрат, у которого четыре вершины соединены попарно линиями. В общем, понятно, о чём речь. Можно доказать, что n>3, то есть обычный полный граф от куба не подходит: ***** ... здесь нужны изображения ... ***** Вот еще достижения в области нижней границы: В 1971 году: n>=6 В 2003 году: n>=11 В 2006 году: n>=13 Число Грэма как верхняя граница уже неактуальна, так как уже было установлено, что n<=F7(12), где F(n) = 2{n}3, т.е. 2 и 3 с n стрелками сверхстепени между ними. Итак, Число Грэма на самом деле это G(64): G1: 3^^^^3 = 3{4}3 G2: 3^^^...^^^3 = 3{3{4}3}3 Gn: 3^^^...^^^3 = 3{G(n-1)}3 В нотации массивов это будет между {3,65,1,2} и {3,66,1,2}, причём намного ближе к {3,65,1,2}. В цепных стрелках Конвея, Число Грэма между 3 -> 3 -> 64 -> 2 и 3 -> 3 -> 65 -> 2. |
вершинами. Раскрасим каждое ребро этого графа либо в красный, либо в чёрный цвет. При каком наименьшем значении n каждая такая раскраска обязательно содержит раскрашенный в один цвет полный подграф с четырьмя вершинами, все из которых лежат в одной плоскости?|
|
|
|