О нижних оценках хроматического числа пространства с запрещенными одноцветными треугольниками

В комбинаторной геометрии большой популярностью пользуется задача. Нельсопа-Эрдеша-Хадвигера, ставшая широко известной в 50-е годы XX столетия (см. [1-4]). Суть этой задачи состоит в отыскании величины y(Rⁿ), которая носит названия хроматического числа пространства и равна, минимальному числу цветов, в которые можно так покрасить все точки Rⁿ, чтобы любые две точки на расстоянии 1 были разных цветов. Описанная проблема. все еще является открытой даже для евклидовой плоскости: на. настоящий момент известно лишь, что 5 6 x(R²) 6 7, причем оценка сверху довольно тривиальна. О малых значениях п можно подробнее прочитать в обзорах и исследованиях [3], [4], [5-13], однако наиболее интересным представляется случай п ^ то. Наилучшая верхняя оценка при растущем п была доказана в работе [14] и выглядит следующим образом (см. также [15]):

_X(Rⁿ) 6 (3 + о(1))^п, п ^ то.

Что касается нижних оценок, то при помощи линейно-алгебраического метода, в классической работе [16] в 1981 году была получена оценка:

y(Rn) > (1.207... + о(1))п, п ^то.

Наилучшая же нижняя оценка при п ^ то была не так доказана в работе [17]:

y(Rn) > (1.239 ... + o(1))n, п ^ то.

Исходная задача обросла большим количеством обобщений, в частности, указанная проблема имеет смысл для произвольных метрических пространств (см. [18-23]). Упомянем также задачу о хроматическом числе сферы y(S^Tl), которая формулируется ровно так же, как проблема Нельсона-Эрдеша-Хадвигера, но вместо всего пространства рассматриваются точки п-мерной сферы (см. [24-28]). Наконец, довольно популярным является вопрос: чему равно минимальное количество цветов y(Rⁿ; ^1>---^_т)>^в которые можно так покрасить точки пространства, чтобы расстояние между любыми двумя точками одного цвета не лежало во множестве {Z1,... ,1_т} (см. [4], [6], [29-31])?

Наша основная задача будет близка к описанной выше. А именно, для 0 <  а <  1 < b <  V2 определим величину x_a,b(Rⁿ) ^как минимальное количество цветов, в которые можно так покрасить точки пространства, чтобы никакие три точки не образовывали равнобедренный треугольник с длинами боковых сторон 1 и длиной основания в пределах от а до b. Данную величину называют хроматическим числом пространства с запрещенными одноцветными треугольниками. Она изучалась в недавних работах [32-35] и частично освещалась в нашем предыдущем исследовании [36]. Нас будут интересовать в основном нижние оценки величины y_a,b(Rⁿ).

В следующем разделе мы укажем имеющиеся результаты касательно исследуемой величины и приведем формулировки полученных нами результатов, а также общий план их доказательства. В разделе 3 мы покажем, как соотносятся наши результатами с наилучшими известными на настоящий момент границами.

2.    Формулировки основных результатов

Итак, приведем наилучшие имеющиеся на текущий момент оценки и обсудим основные идеи их доказательства.

Теорема 8. Пусть 0 <а< 1

3 = к — а²(к — у), г =

а(к — а)

1 + 2(а — к)

При а >  0 и ж G [3 — к + а + г, а + г] поломсим

Ci (а) = (а + 2г)“^+2г (а + г)^-а-гг^- (1 — а — 2г)^1-а-2г х х(к — а — г)^-к+а+г (1 — к — г)^-1+к+г,

С2(ж, а) = (а + г)^а+тж^-х(а + г — _ж)²(^-“^-г+^ж)г^г(ж — а)^-ж+Д С₃(ж, а, 3) = (к — а — г)^к-“^-г (3 — х)^-/3+ж х х (к + ж — а — 3 — г г' " ■'" " ' ⁺' х х(1 — к — г)^1-к-г (1 + а + 3 — ж — 2к)^-1-“^ч3+х+2к , А(а, 3) = тахС₂(ж, а) • Сз(ж, а, 3 )•

Тогда                                                                  n

^Xa,b(Rn) > (Д(а,3)(к — у)^-к+7(1 + у — к)^-1-7+« ^{+ 0 (1)}) .

Теорема 9. Пусть 0 <а< 1

а = к — Ь2(к — у),

3 = к — а2(к — у), г =

а(к — а)

1 + 2(а — к)

Пусть таксисе а > 0 их Е [3 — к + а + г, а + г]. Полосисим

5 = [—-1 , Р =   ^Л.

[ 7 — nJ          5

Допустим, р > 3 - 7- Тогда w (R") > (^^^ + "<»)".

^Х(а,^{3 )}

где функции С1(а) и Х(а,3) определены в формулировке предыдущей теоремы.

Теорема 10. Пусть 0 <а< 1 <Ь

Поломсим

5 (кИ

Зафиксируем г Е {1,...,5} и рассмотрим к — 7

Р = —— г

а' = тах{а, 7 — р},

а' (к — а') г =-----—.----г.

1 + 2(а' — к)

Пусть у Е [3, к], х Е [у — к + а' + г, а' + г]. Тогда

Х-Ж") > (ЙАМЩЙУ + "(1))",

Х(а ,У)

где функции С1(а') и Х(а',у) определены в формулировке теоремы 8.

Обратимся к первой из представленных теорем. Общая идея ее доказательства заключается в следующем. При помощи явных построений получают совокупность ^(0,1), состоящую из (0,1)-векторов (то есть векторов с координатами, равными 0 или 1), у которых попарные скалярные произведения лежат в заданном отрезке. Пусть М(0,1) = |М(0,1)|. На следующем шаге линейно-алгебраическим методом оценивается максимальный размер D(0,1) подсовокупности Р(0,1) С ^(0,1), в которой запрещено ровно одно скалярное произведение р. На последнем этапе при помощи этих двух оценок и простых геометрических соображений выводится, что

V , _(R"₎ > ^М(0, 1)

Х“,Ь' Ю 3Д(О> !) •

Следующие теоремы представляют собой некоторое усложнение исходной техники.

Наша основная идея заключается в том, чтобы на первом и втором этапах использовать не (0,1)-векторы, а ( —1, 0,1)-векторы, то есть векторы с координатами из множества { —1, 0,1}. Аналогично определениям D(0,1) и М(0,1) вводятся определения величин D( — 1, 0,1) и М( —1, 0,1). При этом оказывается, что v , (R") > МИ0,1)                         m

^X“^ ) - 3D( — 1,0, 1).                                     I I

Конечно, почти всегда М(—1, 0,1) > М(0,1), остается добиться того, чтобы величина D( — 1, 0,1) была не слишком большой по сравпешпо с D(0,1). Плоя введения (—1, 0,1)-векторов была впервые успешно применена в работе [17] для усиления нижней оценки хроматического числа пространства x(R"), именно это послужило мотивацией для применения данных векторов в нашей задаче.

Доказанный нами результат звучит следующим образом.

Теорема 11. Пусти натуральные числа ki,k_—i,l удовлетворяют условию 0 < l < k_i + k_—i< n/2 и пусти разности q = k_i + k_—i — l является простим числом.

Введем следующие обозначения:

у = l/n, к = k_i/n, к_—1 = k_—i/n; а = к₁ + к— — Ь²(к₁ + к— — у), 3 = к1 + к_—1 — а²(к1 + к_—1 — у);

<5 = (ап"|, 3 = L3nJ.

Пусти, наконец, целые неотрицательные числа

Г, ri, ro, Г—i, S, Si, So, S — i, t, ti, to, t—i удовлетворяют соотношениям г + s + t = n, r1 + ro + r—i = r, Si + So + S—i = s, ti + to + t—i = t; ri + Si + ti = ki, r—1 + S—1 + t—i = k-i; max(—2ri, —2r—i) + max(0, ri — r—i — ro)+ max(0, r—i — ro — ri) + max(—2si, —2s—i)+ max(0, si — s—i — So) + max(0, s—i — So — si) + max(—2ti, —2t—i) + max(0, ti — t—i — to)+ max(0, t—i — to — ti) > <5.

Тогда

Xa,b(Rⁿ) >

E

(mi,mi)EB

л mi rm

Cn cn—mi

X

X

Г^ri n^r° nsi n^s° Г^а\ n^{t0 c}r ^T—Ti^s ^cs—si^ct^Ct—ti

—

, 2 Ell cy cry, \ А г= — i

1^s,,i /-'Y^S,,0      z-"Y^ti,i /-"Y^ti,0

■ s ^cs_i — s,i^ct_i  ^ct_i — t_ii

)

где области суммирования Л задается условиями гщ > 0; Si,: > 0; ti,: > 0; г, j Е { —1, 0,1};

52 ^ri,: = ^r:, ^{j Е {—}1,⁰,^1}; i

52 ^Si,: =^S:, ^{j Е {—}1,⁰,^1}; i

^ ti: = t₃, j е {—1,0,1}; i

52^ri,: = ^ri, ^{г Е {—}1,⁰,^1}; :

52 ^Si,: = ^Si, ^{г Е {—}1,⁰,^1}; :

^ ti: = ti, г Е {—1, 0,1};

:

ri,i — ri, —i — r—i,i + r—i, —i + Si,i — Si, —i — S —i,i + S —i, —i +

+ ti,i — ti,—i — t—i,i + t—i,—i > 3, а области В определяется следующим образом:

В = {(mi, m2): m_i,m₂ Е N U {0}, m_i + m2 6 n, m_i + 2m2 6 q — 1}.

Предложим небольшое пояснение относительно формулировки данной теоремы. На са мом деле величина

Е

с ^т1 с^т2 ^п ^п-

ті

ті,т2ЕВ

представляет собой оценку величины D(-1, 0,1), а выражение в скобках является оценкой величины М(—1, 0,1). Наконец, число 3 в знаменателе возникает из формулы (1), которую, по сути, и представляет наша оценка.

3.    Численные результаты

Покажем, как соотносится оценка теоремы 11 с известивши на настоящий момент результатами.

Ниже приведены две таблицы с оценками исследуемой величины X_a,b(Rⁿ)- По вертикали откладывается параметр а с шатом 0.02, по горизонтали — параметр b с шатом 0.05, в ячейке таблицы записана константа с в основании экспоненты в правой части оценки вида y_a,b(Rⁿ) > (с + о(1))^п,п ^ то. Прочерк означает, что полученная оценка не является экспоненциальной, то есть с 6 1.

Таблица!

Максимум из оценок теорем 8 10

	1.10	1.15	1.2	1.25	1.30	1.35	1.40
0.02	1.053	1.079	1.104	1.129	1.153	1.177	1.200
0.04	1.049	1.075	1.100	1.125	1.149	1.173	1.196
0.06	1.044	1.070	1.095	1.120	1.144	1.168	1.191
0.08	1.038	1.064	1.089	1.114	1.138	1.162	1.185
0.10	1.032	1.057	1.082	1.107	1.131	1.155	1.177
0.12	1.025	1.050	1.075	1.099	1.123	1.147	1.170
0.14	1.020	1.043	1.067	1.091	1.115	1.138	1.161
0.16	1.015	1.036	1.059	1.083	1.106	1.130	1.153
0.18	1.010	1.029	1.051	1.074	1.098	1.121	1.143
0.20	1.006	1.023	1.044	1.066	1.089	1.111	1.134
0.22	1.002	1.018	1.037	1.058	1.080	1.103	1.125
0.24	—	1.013	1.030	1.051	1.072	1.094	1.115
0.26	—	1.009	1.025	1.043	1.064	1.085	1.106
0.28	—	1.004	1.019	1.037	1.056	1.076	1.097
0.30	—	1.001	1.015	1.030	1.049	1.068	1.088
0.32	—	—	1.010	1.025	1.042	1.060	1.080
0.34	—	—	1.005	1.020	1.035	1.053	1.072
0.36	—	—	1.002	1.014	1.030	1.046	1.064
0.38	—	—	1.002	1.009	1.024	1.040	1.057
0.40	—	—	1.002	1.005	1.018	1.034	1.050
0.42	—	—	1.002	1.005	1.013	1.028	1.043
0.44	—	—	1.002	1.005	1.007	1.022	1.037
0.46	—	—	1.002	1.005	1.005	1.016	1.031
0.48	—	—	1.002	1.005	1.005	1.010	1.025
0.50	—	—	1.002	1.005	1.005	1.005	1.019
0.52	—	—	1.002	1.005	1.005	1.005	1.012
0.54	—	—	1.002	1.005	1.005	1.005	1.006
0.56	—	—	1.002	1.005	1.005	1.005	1.005
0.58	—	—	1.002	1.005	1.005	1.005	1.005
0.60	—	—	1.002	1.005	1.005	1.005	1.005

В таблице 1 продемонстрирован максимум из оценок теорем 8-10.

В таблице 2 мы привели численные результаты теоремы 11. Жирным шрифтом выделены участки, где новая оценка экспоненциально превосходит результаты теорем 8-10. Оказывается, что новая теорема превосходит предыдущие оценки при малых а и больших Ь. Также небольшое улучшение имеется в области, где оценки теорем 8-10 близки к 1. Отметим, что имеется большая область значений параметров, при которых новая теорема значительно проигрывает: оценка величины D(- 1, 0,1) при помощи линейноалгебраического метода оказалась слишком плохой, и выгоднее в данном случае работать с (0,1)-векторамп.

Т а б л и ц а 2

Оценка теоремы 11

	1.10	1.15	1.2	1.25	1.30	1.35	1.40
0.02	1.036	1.062	1.088	1.113	1.149	1.186	1.216
0.04	1.034	1.059	1.085	1.110	1.143	1.181	1.211
0.06	1.030	1.056	1.081	1.106	1.133	1.175	1.204
0.08	1.027	1.051	1.077	1.101	1.126	1.166	1.195
0.10	1.023	1.045	1.070	1.096	1.120	1.156	1.185
0.12	1.019	1.040	1.064	1.088	1.113	1.145	1.173
0.14	1.015	1.034	1.057	1.082	1.105	1.133	1.160
0.16	1.012	1.029	1.051	1.074	1.098	1.121	1.146
0.18	1.008	1.025	1.044	1.067	1.090	1.113	1.136
0.20	1.005	1.020	1.038	1.059	1.082	1.105	1.127
0.22	1.001	1.016	1.032	1.052	1.074	1.094	1.118
0.24	—	1.011	1.027	1.046	1.066	1.089	1.110
0.26	—	1.006	1.022	1.039	1.058	1.081	1.103
0.28	—	1.003	1.017	1.033	1.053	1.071	1.093
0.30	—	1.001	1.014	1.028	1.044	1.066	1.088
0.32	—	—	1.011	1.023	1.038	1.058	1.076
0.34	—	—	1.008	1.019	1.033	1.053	1.067
0.36	—	—	1.005	1.016	1.027	1.043	1.061
0.38	—	—	1.003	1.013	1.023	1.037	1.055
0.40	—	—	1.002	1.010	1.018	1.032	1.047
0.42	—	—	—	1.007	1.016	1.028	1.042
0.44	—	—	—	1.003	1.013	1.025	1.035
0.46	—	—	—	1.001	1.007	1.021	1.030
0.48	—	—	—	—	1.006	1.017	1.026
0.50	—	—	—	—	1.004	1.013	1.022
0.52	—	—	—	—	1.003	1.010	1.017
0.54	—	—	—	—	1.001	1.006	1.013
0.56	—	—	—	—	—	1.003	1.011
0.58	—	—	—	—	—	1.001	1.008
0.60	—	—	—	—	—	—	1.007
0.62	—	—	—	—	—	—	1.005
0.64	—	—	—	—	—	—	1.003
0.66	—	—	—	—	—	—	1.002