О дистанционных графах с большим хроматическим и малым кликовым числами

1.    Введение и формулировка результата

Назовем дистанционным графом, или графом расстояний, любой граф G = (V, E), у которого

V С R n , E С {{ x, y } : | x - y | = a } , a> 0.

Здесь | x - y | — обычное евклидово расстояние между векторами x, y. Желая подчеркнуть, что вершины графа принадлежат пространству размерности n, будем говорить об n -мерном дистанционном графе. Если | V | <  ∞ , то скажем явно, что граф расстояний конечный.

Напомним, что хроматическим числом графа G = (V, E ) называется величина x(G), равная наименьшему количеству цветов, в которые можно так покрасить элементы множества V , чтобы концы любого ребра из множества E были разных цветов. В свою очередь обхватом графа G называется длина g(G) кратчайшего цикла в нем. Классическое утверждение П. Эрдеша (см. [1]) гласит, что для любых k, l существует граф G, у которого x(G) > k, g(G) > l. Утверждение доказывается с помощью вероятностного метода.

Основной вопрос настоящей работы: что служит естественным аналогом утверждения Эрдеша для дистанционных графов? Этот вопрос тесно связан с известной проблемой Нелсона–Хадвигера. Эта проблема состоит в отыскании хроматического числа пространства R n , т.е. величины x( R n ), равной наименьшему количеству цветов, в которые можно так покрасить все точки R n , чтобы между одноцветными точками не было расстояния 1. В терминах дистанционных графов x( R n ) — это хроматическое число графа расстояний, у которого V = R n . А поскольку, как нетрудно видеть, x( R n ) <  ^то , некоторые соображения

Настоящая работа выполнена при финансовой поддержке гранта РФФИ № 12-01-00683, гранта Президента РФ № MД-666.2012.1 и гранта НШ-2519.2012.1 поддержки ведущих научных школ.

компактности (см. [2]) показывают, что хроматическое число пространства достигается на конечном n-мерном дистанционном графе.

Сейчас известно, что

(Z + o(1)) n <  x( R n ) <  (3 + o(1)) n , Z = 1.239 ...

Нижняя оценка принадлежит А. М. Райгородскому (см. [3]), верхняя — Д. Ларману и К. А. Роджерсу (см. [4]).

В терминах графов расстояний нижнюю оценку можно сформулировать так: существует функция 5 = 5(n), стремящаяся к нулю при n ^ то , и такая последовательность конечных n-мерных дистанционных графов G n , что x(G n ) ^ (Z + 5(n)) n .

Назовем кликой в графе любой полный подграф в нем, а кликовым числом графа — число вершин в самой большой клике. Заметим, что клика в графе расстояний — это симплекс. Обозначим кликовое число графа G через w(G). Естественный аналог утверждения Эрдеша в дистанционном случае звучит примерно так: существует последовательность конечных n-мерных графов расстояний G _n , у которых кликовые числа «маленькие», а хроматические числа растут экспоненциально.

В работах [5––8] изучались величины

Z (k) = sup { Z : з 5(n) = o(1), V n, 3 G в R n , ^(G) < k, x(G) >  (Z + 5(n)) n } .

Для этих величин получены достаточно хорошие оценки. Для нас сейчас важно то, что, как видно из этих оценок, £(k) ^ Z при к ^ то . В настоящей работе мы докажем следующую теорему.

Теорема 1. Пусть к = k(n) — любая функция, стремящаяся к бесконечности с ростом n. Тогда существуют функция 5 = 5(n), стремящаяся к нулю при n ^ то , и такая последовательность конечных n-мерных дистанционных графов G n , что x(G n ) ^ >  (Z + 5(n)) n и w(G _n ) <  k(n).

Пафос теоремы в том, что константа в основании экспоненты, которая служит оценкой для хроматического числа, в точности равна величине ζ , а не просто «близка» к ней. И для этого достаточен любой сколь угодно медленный рост верхней границы k(n) для кликового числа.

Теорему 1 мы докажем в следующем разделе. А в завершение этого раздела скажем, что с проблемой Нелсона–Хадвигера можно ознакомиться по обзорам [9, 10] и по книгам [11––16].

2.    Доказательство теоремы 1

Зафиксируем произвольную функцию k = k(n), стремящуюся к бесконечности с ростом n .

Пусть для начала а и b < a — произвольные числа из интервала (0,1/2). Для каждой пары таких чисел рассмотрим последовательность множеств

V n (a,b) = { x = (xi,... ,X n ) : X i G { — 1, 0,1 } , |{ i : X i = 1 }| = [an], |{ i : X i = — 1 }| = [bn] } .

Здесь [x] — целая часть числа x. Стандартные вычисления с применением формулы Стирлинга показывают, что | V _n (a, b) | = (в (a, b) + o(1)) n , где в (a, b) > 1. Пусть p — минимальное простое число, такое, что [an] + [bn] — 2p <  — 2[bn]. Обозначив через (x, у) евклидово скалярное произведение векторов, положим

E n (a,b) = {{ x,у } : x,у G V n (a,b), (x,y) = [an] + [bn] — p } .

Образовалась последовательность конечных n-мерных дистанционных графов G n (a,b) = (V n (a,b), E n (a,b)).

Назовем множество W С V вершин какого-либо графа G = (V, E) независимым, если никакие два его элемента не соединены ребром из множества E . Размер любого из максимальных по мощности независимых множеств в графе G обозначим через a(G) и будем говорить, что a(G) — число независимости данного графа. В определенном смысле неза- висимые множества — это «антиклики»; именно поэтому число независимости и кликовое число принято обозначать первой и последней буквами греческого алфавита.

В работе [3] показано, что a(G _n (a,b)) <  (ү(a, b) + o(1)) ⁿ , где 1 < ү(a, b) < e(a,b) (более

подробно нужные выкладки проведены в [12]). В то же время практически очевидно, что

X(G) >

| V | a(G)

для любого графа G = (V, E). В нашем случае, стало быть,

x(G n (a,b)) >

(в(а,Ь)+ o(1)) ⁿ

(Y(a,b) + o(1))n

(в(а,Ь) .

= (үй + o(1’J .

Как доказано все в тех же [3, 12], значение max a,b

eCa^b) Y ^{( a,b )}

достигается при a _o = 0.36063... и bo = 0.063... (a _o и bo служат решениями некоторой системы трансцендентных уравнений), и оно в точности равно ζ. Если бы было заодно выполнено неравенство ^(G n ) ^ k, то говорить было бы дальше не о чем. Однако в графах G _n полно k-клик.

Применим вероятностный метод. Рассмотрим G n = G _n (ao,bo). Пусть в = в(ao,bo), ү = ү(a _o ,b _o ), N = | V _n (a _o ,b _o ) | . Положим p = N ^{- 3 /k} . Поскольку, очевидно, p G (0,1], эту величину можно интерпретировать как вероятность. А именно, мы будем удалять ребра графа G n независимо друг от друга с вероятностью 1 — р. Получится случайный граф. Если мы докажем, что с положительной вероятностью у этого графа нет k-клик и его число независимости не превосходит (ү+o(1)) ⁿ , то мы найдем нужный нам граф и теорема будет доказана.

Положим l = [5a Gp in Nj +1 > 5a G in N.

Имеем l - 5a(Gn)N3/k in N < 5N3/k(in N)(ү + o(1))n = (в + o(1))3n/k(ү + o(1))n = (ү + o(1))n, т.к. k ^ то (разумеется, здесь все величины o(1) разные).

Докажем, что с положительной вероятностью у случайного графа G одновременно w(G) < k и a(G) < l. Ясно, что этого хватит для завершения доказательства теоремы.

Обозначим через X _n число k-клик в случайном графе, а через Y _n — число независимых множеств размера l в нем. Ввиду неравенства Маркова достаточно получить оценки MX n <  2 и MY n <  2 при больших n, где M — математическое ожидание. Имеем

MX n <  C N p C k <  N ^k p k— = N ^k • N - ¹ . 5( k - ¹) ^ 0.

Вместе с тем

MY n =

E

(1 _— p) |{{ ^x, y }G E n ^{: x,} y G A }|

A c V n , | A | = l

В работе [7] доказана оценка

I^{{ x,y }e E n : x,y e A }\ > -og^

Из нее следует, что

MY n <  C^l N (1 - p) 40^ <  N¹

pi ²

e 4 a ( Gn ) =

l ln N- ρl e        4a(Gn) .

Но

так что

4 P^ > 1.25ln N, 4a(Gn) / l ln N - —P— < -0.251 In N ^ -TO, 4a(Gn)

MY n ^ o,

и теорема доказана.