Раскраски метрических пространств с запрещенными одноцветными конфигурациями тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Бердников Алексей Викторович

• Бердников Алексей Викторович
• кандидат наук
• 2021

Оглавление диссертации кандидат наук Бердников Алексей Викторович

Введение

Глава 1. Хроматическое число с несколькими

запрещенными расстояниями

1.1 Постановка задачи

1.2 Формулировка результатов

1.3 Вспомогательные утверждения

1.4 Линейно-алгебраический метод

1.5 Доказательство леммы

1.6 Доказательство леммы

1.7 Доказательство леммы

1.8 Доказательство теоремы

1.9 Доказательство теоремы

1.10 Следствие из теоремы

Глава 2. Хроматические числа графов расстояний без

больших клик

2.1 Формулировка результатов

2.2 Основные леммы

2.3 Вспомогательные леммы

2.4 Доказательство леммы

2.5 Доказательство леммы

2.6 Доказательство теорем 3 и

2.7 Следствие из теоремы

Глава 3. Контрпримеры к гипотезе Борсука на сферах

малого радиуса

3.1 Формулировка результатов

3.2 Доказательство теоремы

3.3 Доказательство теоремы

Заключение

Введение диссертации (часть автореферата) на тему «Раскраски метрических пространств с запрещенными одноцветными конфигурациями»

Введение

Актуальность темы исследования и степень ее разработанности

Данная работа посвящена задачам о раскраске метрических пространств, связанным с двумя классическими сюжетами комбинаторной геометрии — задачей Хадвигера — Нельсона о хроматическом числе пространства и задачей Борсука о разбиении множества на части меньшего диаметра.

Считается, что первый вариант формулировки этой задачи о хроматическом числе плоскости был предложен Э. Нельсоном в 1950 году. В 50-х годах она уже была известна Г. Хадвигеру и П. Эрдёшу, хотя впервые была опубликована лишь в 1960 году [1]. История этой задачи подробно изложена в книге А. Сойфера [2].

Итак, хроматическим числом плоскости называется величина, равная наименьшему количеству цветов, в которые можно покрасить все точки плоскости таким образом, чтобы расстояние между любыми двумя точками одинакового цвета не было равно единице. Эта величина обозначается х(Е2), и задача ее отыскания называется задачей Хадвигера — Нельсона. Несмотря на кажущуюся простоту эта задача до сих пор далека от полного решения. Известно, что х(Е2) ^ 7. Соответствующая раскраска в семь цветов, получающаяся из разбиения плоскости на шестиугольники диаметра чуть меньше единицы, приписывается Дж. Р. Исбеллу. Нижняя же оценка х(Е2) ^ 4, доказанная братьями Мозерами [3], более полувека оставалась непревзойденной, однако в 2018 году была улучшена на единицу О. Д. Н. Дж. де Греем (с привлечением компьютерных вычислений) [4].

Приведенное выше определение допускает множество обобщений. Например, естественно рассматривать хроматическое число п-мерного евклидова пространства Еп (мы будем обозначать эту величину символом х(Еп)). Для значений п ^ 4 известны следующие оценки (помимо указан-

ных выше оценок величины х(Е2)):

Х(Е1) = 2,

(1) (2) (3)

6 < х(Е3) < 15

9 < х(Е4) < 54.

Равенство (1) очевидно. Оценки (2) для трехмерного пространства были получены в 2002 году: нижняя — О. Нехуштаном [5], верхняя — Д. Коулсоном [6]. Из неравенств (3) первое доказали Дж. Эксо, Д. Измаилеску и М. Лим в 2014 году [7] (с использованием вычислений на компьютере), второе — Р. Радоичич и Г. Тот в 2003 году [8].

Представляет интерес и асимптотическое поведение величины х(Еп) при стремлении размерности п к бесконечности. Известны следующие экспоненциальные оценки:

Иными словами, существует константа ( = 1,239... и бесконечно малые последовательности действительных чисел и {б'п}, для которых при

любом натуральном п выполняются неравенства

Оценка снизу была доказана в 2000 году А. М. Райгородским [9] и является улучшением оценки П. Франкла и Р. М. Уилсона [10], которые доказали неравенство х(Еп) > (С + °(1))п при п — то для £ = 1,207... Оценка сверху была найдена Д. Ларманом и К.А.Роджерсом в 1972 году [11] и с тех пор так и не была улучшена. Таким образом, оказалась верна высказанная еще ранее гипотеза Эрдёша о том, что величина х(Еп) растет экспоненциально при п — то.

Помимо увеличения размерности пространства, имеет смысл также увеличивать число «запрещенных расстояний», то есть запрещать двум точкам одного цвета находиться на расстоянии а Е А, где А — некоторое фиксированное множество положительных чисел. Минимальное возможное число цветов в раскраске п-мерного евклидова пространства, удовлетворяющей этому ограничению, называется хроматическим числом этого пространства с множеством запрещенных расстояний А и обозначается

(1,239... + о(1))п < х(Еп) < (3 + о(1))п при п —У то.

(4)

(С + 5пГ^Х(Еп)<(3 + 5'пГ.

х(Еп,А). Существуют исследования, посвященные хроматическим числам с бесконечным множеством запрещенных расстояний [12], но в данной работе, так же как и в ряде других публикаций [13—16], будет рассматриваться лишь случай конечного числа запретов, то есть когда А = {а1,..., ак].

Сразу же отметим, что случай card А = 1 не дает ничего нового, так как в силу однородности вещественного пространства Еп

для любого положительного числа а. Иными словами, величина запре-

хроматическое число пространства. Однако при card А ^ 2 величина х(Еп,А) уже представляет определенный интерес. В частности, в главах 1 и 2 данной работы производится нижняя оценка хроматического числа пространства с несколькими запрещенными расстояниями.

Хроматическое число с несколькими запрещенными расстояниями можно грубо оценить сверху через хроматическое число с одним запрещенным расстоянием. А именно, нетрудно показать, что для любого натурального к и любого набора а1,... ,ак справедливо неравенство

При большом количестве запрещенных расстояний, как правило, рассматривают не саму величину х(Еп,А) для некоторого фиксированного множества А, а максимум таких величин по всем наборам А = {а1,..., ак] заданной мощности к, то есть

Неравенство (5) и результат Лармана и Роджерса (верхняя оценка в неравенствах (4)) позволяют асимптотически оценить сверху величину х(Еп, к) (и заодно убедиться в ее существовании):

х(Еп,{а}) = х(Еп)

щенного расстояния (в том случае, если оно всего одно) не влияет на

x(En,{ai,...,ak])^(x(En))k.

(5)

(6)

х(Еп,к) < (3 + о(1))кп

при п —>■ 00.

(7)

Существуют и нижние асмптотические оценки. В 2001 году А. М. Рай-городский доказал [17], что х(Еп,к) > (Вк)Сп для некоторых полодитель-ных констант В и С .В 2006 году И. М. Шитова представила [13] следующие

результаты для случаев двух, трех и четырех запрещенных расстояний:

х(Еп, 2) > (1,465 + о(1))п при п — то, (8)

Х(ЕП,3) >(1,664 + о(1))п при п — то, (9)

х(Еп, 4) > (1,836 + о(1))п при п —то. (10)

Позднее, в 2009 году, Е. С. Горская, И. М. Митричева, В. Ю. Протасов и А. М. Райгородский [18] опубликовали новый метод получения оценок вида

х(Еп,к)>((к + о(1))п при п — то (11)

для любого натурального к. Они вычислили для малых значений к конкретные значения удовлетворяющие неравенству (11), и высказали предположение, что £(к) растет сублинейно при к — то, причем скорость роста замедляется по мере увеличения к. В данной диссертации доказывается, что значения растут асимптотически быстрее, чем кс для любой ^ 1

константы С <2.

2

Существуют и другие обобщения задачи Хадвигера — Нельсона. Вместо запрета на пары точек одинакового цвета можно запрещать более сложные одноцветные конфигурации (например, тройки точек, удовлетворяющие определенному условию) [19—24].

Вместо евклидова пространства Еп можно рассматривать произвольное метрическое пространство (Х,р). Например, п-мерное векторное пространство Кп, снабженное нормой

1

(.\ р

\\х\\р := I ^^ \Х1\Р I ,

\г=1 /

где р > 1 — некоторое действительное число. Для такого нормированного пространства мы будем использовать обозначение I™. (Ясно, что евклидово пространство является частным случаем I™, а именно Еп = ^О В 2003 году А. М. Райгородский нашел [25; 26] нижнюю асимптотическую оценку хроматического числа пространства I™:

Х(1") > (1,365... + о(1))п при п — то.

Для к запрещенных естественным образом определяется величина х(1р, аналогично величине х(Еп, к). При малых значениях к известны следующие

оценки величины х(1'г,^):

х(11,2)>(1,Ш- + о(1))п при п^ж,

Х(1г,3)^ (2,000...+ о(1))п при п^ж,

х(1\, 4) > (2,250... + о(1))п при п^ж.

Эти результаты были опубликованы И.М.Шитовой в 2007 году [13; 14]. Существует также и верхняя оценка

х(1™,к) < (5 + о(!))кп при п^ж,

которую получили в 2004 году З. Фюреди и Кан Джонхён [27]. Для р £ {1,2} тоже существуют верхние и нижние оценки хроматического числа пространства I™ с одним или несколькими запрещенными расстояниями [28; 29].

Понятие хроматического числа х((Х,р),А) метрического пространства (X, р) с множеством запрещенных расстояний А тесно связано с теорией графов. Чтобы понять эту связь, рассмотрим граф

<5((Х,р),А) •= (Г,£),

где V = X и

£ = {{х,у}сУ\р(х,у)еА]

(так называемый полный дистанционный граф). Проще говоря, это граф, вершинами которого являются точки нашего пространства, причем две точки соединены ребром тогда и только тогда, когда между ними достигается одно из запрещенных расстояний. Такие графы называются графами расстояний, или дистанционными графами. Для удобства введем обозначение Сх ••= &((Х, р), А) (далее для простоты будем считать, что метрика р и множество А фиксированы, поэтому такая краткая запись не должна привести ни к каким неоднозначностям). Нетрудно видеть, что хроматическое число пространства равно хроматическому числу дистанционного графа (отсюда и название):

х((Х,р),А) = х(Ох).

(Напомним, что хроматическим числом х(&) графа С называется наименьшее число цветов, в которые можно раскрасить его вершины так, чтобы каждое ребро соединяло вершины разных цветов [30].)

Рассмотрим Су := <3((У,р),А) —полный граф расстояний, построенный для конечного подпространства V нашего пространства X. Поскольку Су — подграф графа Сх, его хроматическое число не больше хроматического числа графа Сх:

Х(Су) < Х(Ох).

Таким образом, если мы сможем найти величину х(&у) (или оценить ее снизу), то автоматически получим нижнюю оценку хроматического числа пространства X. Более того, среди конечных подмножеств V С X гарантированно существует такое, что х(^у) = х(&х) (даже если X континуально, как, например, в случае X = ). Это следует из теоремы, доказанной в 1951 году Н. Г.де Брёйном и П. Эрдёшем [31]. (Стоит также отметить, что доказательство этой теоремы опирается на аксиому выбора.)

Величину х(^у), в свою очередь, удобно оценивать с помощью неравенства

Х(^) > (12)

где а(Су) —число независимости графа Су (размер наибольшего пустого подграфа графа Су). Значит, всё сводится к оценке, на этот раз верхней, числа а(Су). Опять же, по аналогии с теорией графов мы будем называть множество и С V независимым в метрическом пространстве (V, р) с множеством запрещенных расстояний А, если между парами точек из и не достигается ни одно из запрещенных расстояний:

Ух, у Е и р(х,у)£А, — и будем называть величину

а((У,р),А) := max{card и | и — независимое множество в (У,р)}

числом независимости метрического пространства (V, р) с множеством запрещенных расстояний А. При этом, очевидно, выполняется равенство

a((V,p),A) = a(Cv).

Итак, множество V должно быть подобрано таким образом, чтобы

можно было достаточно точно оценить величину a(Cv). Помимо этого, ко-

card V ,, ^

нечно, хотелось бы, чтобы отношение , было само по себе близко к

a(Gv)

значению x(Gv), однако в большинстве случаев проверить это не представляется возможным.

Один из наиболее эффективных способов получения верхних оценок на числа независимости дистанционных графов — линейно-алгебраический метод в комбинаторике. Он подробно описан в книге Л. Бабаи и П. Франк-ла [32], а также в книге А. М. Райгородского [33]. Именно этот метод (вместе с вышеизложенными идеями) был использован для получения всех нижних асимптотических оценок, перечисленных выше, и будет неоднократно использован в данной работе.

Отметим также, что в большинстве упомянутых выше оценок хроматического числа пространства, так же как и в данной работе, использовались графы расстояний с целочисленными координатами вершин, поэтому все эти результаты связаны также и с теорией кодирования. Чтобы понять эту связь достаточно проинтерпретировать целочисленные точки п-мерного пространства Rn, снабженного некоторой метрикой, как кодовые слова длины п. Если мы теперь рассмотрим граф, вершины которого — это кодовые слова, а ребра соединяют все пары вершин, расстояние между которыми равно некоторому числу d, то любое независимое множество такого графа будет являться кодом с одним запрещенным расстоянием [34; 35].

Помимо полных дистанционных графов на метрическом пространстве (Х,р) рассматриваются и неполные, то есть такие графы G = (V,£), у которых V = X и

£c{{x,y}cV\p(x,y)eA}.

Ясно, что х{1р,Л) = max х{&), где максимум берется по всем дистанционным графам в пространстве IJ^ с множеством запрещенных расстояний А. Можно рассмотреть аналогичную величину, добавив дополнительное ограничение на графы расстояний: для каждого натурального т ^ 3 определим величину Хт(1р, Л) как максимум хроматических чисел полных и неполных дистанционных графов в пространстве с множеством запрещенных расстояний А, не содержащих клик размера т. Если запрещенное расстояние всего одно, то есть А = {а}, сама величина а неважна, поэтому для удобства введем обозначение Хт(1р) := Хт(1р, {1}). Для случая евклидова пространства известно [36—41], что для каждого т существует константа ст > 1,

удовлетворяющая асимптотическому неравенству

Хт(Еп) > (ст + о(1))п при п^ж. (13)

Наибольшие известные значения ст были найдены А. Б. Купавским в 2014 году [42] с использованием вероятностного метода. Интерес к величине Хт(Еп) связан с тем, что обычные (не дистанционные) графы, не содержащие даже 3-клик, могут обладать сколь угодно большим хроматическим числом (теорема, доказанная в 1959 году П. Эрдёшем [43]). Таким образом, оценки вида (13) в некотором смысле переносят классический результат Эрдёша на графы расстояний.

Другая классическая задача, возникающая в связи с раскраской пространства— это задача Борсука о разбиении множеств на части меньшего диаметра. Число Борсука — это величина /(^, равная минимальному количеству частей меньшего диаметра, на которые может быть разбито произвольное множество П в евклиовом ^-мерном пространстве Е11, имеющее диаметр 1. Очевидно, что /(1) = 2. В 30-х годах прошлого века К. Борсук доказал [44], что /(^ всегда больше й, причем ¡(2) = 3, и выдвинул гипотезу, что /(й) = (1 + 1 для всех размерностей й. В 1993 году гипотеза Борсука была опровергнута Дж. Каном и Г. Калаи [45], и сейчас известно, что, хотя ¡(1) = 2,/(2) = 3,/(3) = 4, уже /(64) > 65 и, более того,

ч у/й, __\ й

2 V2 ,, А 3

+0(1)1 <М<\\1$ + 0(1)] (14)

Нижнюю оценку опубликовал в 1999 году А. М. Райгородский [46; 47], а верхнюю получил в 1988 году О. Шрамм [48].

Нас будут интересовать нижние оценки величины при й ^ ж. Пусть П С Еа — конечное множество точек. Граф С = Сп = (П,£) называется его графом диаметров, если (х,у) Е Е тогда и только тогда, когда расстояние 1х — у1 между точками х,у равно диаметру diam П множества П. Граф диаметров является частным случаем графа расстояний. Нетрудно видеть, что для конечных множеств разбиение на части меньшего диаметра и раскраска графа диаметров суть одно и то же. Поэтому имеет место оценка /(й) > х(^о), коль скоро П С Ей.

Нижняя оценка в (14) получается следующим образом. Рассматривается дистанционный граф С в п-мерном евклидовом пространстве Еп,

вершины которого являются (-1,0,1)-векторами, причем фиксированная доля всех координат равна -1, столько же координат равны 1, а остальные координаты равны 0. Этот граф оказывается изоморфен некоторому графу диаметров Н (с диаметром 1) в пространстве Ей, где <1 = п(п+ 1)/2. Далее оценивается снизу хроматическое число графа С:

и это даёт нужную оценку, поскольку ¡(ё) > х(Н) = х(&) и п ~ у/2А. В главе 3 данной диссертации будет доказано, что целый класс конструкций на основе (-1,1) векторов, а также (-1, 0,1)-векторов позволяет строить контрпримеры к гипотезе Борсука с нелинейным ростом величины /(ё).

У всех упомянутых выше конструкций для оценки снизу числа Бор-сука есть общая черта: множество вершин построенного графа единичных диаметров в пространстве Е11 всегда лежит на сфере, радиус которой асимптотически равен 1/л/2. Интуитивно это кажется естественным, ведь любое множество диаметра 1 в евклидовом ^-мерном пространстве Е11 можно накрыть шаром радиуса ^А/(2А + 2) ^ 1/ у/2, и для построения контрпримера к гипотезе Борсука хочется взять множество с как можно большим накрывающим шаром. Однако в 2012 году А. М. Райгородский и А. Б. Купавский доказали [49], что для любого наперед заданного г Е (1/2,1/ у/2) на сфере радиуса г в существует множество диаметра 1, дающее контрпример к гипотезе Борсука.

Райгородский и Купавский для доказательства указанного выше результата использовали (-1,1)-векторы с равным числом положительных и отрицательных координат. В данной диссертации доказывается, что аналогичные контрпримеры к гипотезе Борсука на сферах малых радиусов можно строить с помощью довольно произвольных конфигураций (-1,1)-векторов и (-1,0,1)-векторов.

Цель работы и основные задачи

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

задачами о раскраске метрических пространств. Цель данной работы состоит в развитии линейно-алгебраческих и вероятностных методов в экстремальной комбинаторике и теории графов.

Научная новизна

Все результаты, представленные в диссертации, являются новыми.

Теоретическая и практическая значимость работы

Диссертация носит теоретический характер. Полученные в ней результаты важны для экстремальной теории графов, комбинаторной геометрии, экстремальной комбинаторики и теории кодирования.

Методы исследования

В диссертации используется линейно-алгебраический, вероятностный и другие классические методы экстремальной комбинаторики.

Основные положения, выносимые на защиту

1. Для любого С < найдены полные дистанционные графы в

пространстве (д Е Ы) с к запрещенными расстояниями, хроматическое число которых не меньше (Вк)Сп, где В — некоторая положительная константа, зависящая от выбора С.

2. С помощью вероятностного метода в комбинаторике доказано существование неполных дистанционных графов в пространстве

(р Е Ы) с к запрещенными расстояниями, не имеющих клик фиксированного размера, чье хроматическое число можно оценить снизу в виде (Вк)Сп.

3. Найден класс конструкций на основе (—1,1)-векторов, а также

(—1,0,1)-векторов, дающих новые контрпримеры к гипотезе Борсу-

ка с нелинейным ростом числа Борсука на сферах любого радиуса, 1

превышающего -.

2

Апробация результатов

По теме диссертации были сделаны доклады на следующих научных конференциях:

— Международная конференция «The 5th German-Russian Week of the Young Researcher», Россия, 2015.

— Международная конференция «2nd Russian-Hungarian Combinatorial Workshop», Венгрия, 2018.

Публикации

Основные результаты по теме диссертации изложены в 5 работах. Все они опубликованы в журналах, входящих в перечень ВАК, 4 из них — в журналах, индексируемых базой Scopus, 3 — в журналах, индексируемых базой Web of Science. Все результаты, выносимыме на защиту, в том числе результаты, опубликованные в совместной работе, были получены автором диссертации самостоятель но.

Объем и структура работы.

Диссертация состоит из введения, 3 глав и заключения. Полный объём диссертации составляет 74 страницы, включая 4 таблицы. Список литературы содержит 56 наименований.

Глава 1. Хроматическое число с несколькими запрещенными

расстояниями

1.1 Постановка задачи

В 2009 году Горская, Митричева, Протасов и Райгородский предложили метод [18], позволяющий при помощи выпуклой оптимизации получать асимптотические оценки вида

х(Еп,к)>(Ск + о(1))п при п^ж.

Таким образом, найденные ими численные значения ^ являются нижними оценками величин

Ск - lim ^х(Еп,к).

п^<х>

Помимо нахождения численных приближений этих величин, можно сформулировать ряд других интересных задач. Например, оценить асимптотическое поведение ^ при стремлении к к бесконечности. На основе найденных значений (к авторы статьи [18] высказывают предположение, что рост (к медленнее линейного и замедляется при увеличении параметра к (иными словами, функция ^ вогнута по к).

Ранее, в 2001 году, А. М. Райгородский опубликовал статью [17], в которой доказывается следующий результат.

Теорема (Райгородский). Существуют такие абсолютные постоянные В > 0 и С > 0 и такое число N, что для любого натурального числа к и любого натурального п^ N справедливо неравенство

х(Еп,к) > (Вк)

Сп

Для констант В и С, существование которых утверждается в теореме, и любого натурального к, очевидно, справедливо неравенство

ск > (Вк)с. (1.1)

Таким образом, мы автоматически получаем нижнюю оценку скорости роста величины (к в виде некоторой степени числа к.

В статье А. М. Райгородского доказательство сформулированной выше теоремы производится конструктивно путем явного построения конечных множеств в евклидовом пространстве Еп и оценки их хроматических чисел (общая схема таких доказательств была изложена во введении). Это доказательство позволяет получить конкретные значения В и С, удовлетворяющие теореме, однако эти значения довольно малы: В < и С < —.

2 10

Возникает естественный вопрос: насколько большим может быть показатель степени С, чтобы при некоторой положительной константе В и любом натуральном к выполнялось неравенство (1.1)?

В данной главе будет доказано обобщение теоремы Райгородского на пространства с метрикой, порожденной £д-нормой, для всех натуральных д. Кроме того, будет произведена более точная оценка констант. Из полученных результатов, в частности, будет следовать справедливость неравенства (1.1) для любого значения С < - (при условии, что В достаточно мало).

3

В основе доказательства лежит линейно-алгебраический метод, уже упомянутый во введении.

Результаты этой главы опубликованы в статьях [52] и [53].

1.2 Формулировка результатов

Напомним, что пространством мы называем п-мерное пространство Еп, снабженное нормой

11^11^ — (1.2)

Теорема 1. Пусть зафиксированы натуральное число д и положительные действительные числа К и А, причем д < А < д + 1. Тогда для любого положительного числа С < найдется такое В' > 0, что неравенство

Х(^,к) > (В'к)Сп

будет справедливо при всех натуральных п и всех натуральных к < КпА.

Замечание. Из ограничений С < -1 и А > д следует, что теорема 1

^ 1

применима лишь при С < —.

Теорема 2. Пусть зафиксировано натуральное число д. Тогда для

любого положительного числа С <-- найдется такая константа В >

я+1

0; что неравенство

х(^,к)>(Вк)Сп будет выполнено для всех натуральных к и п.

Первая теорема будет доказана в параграфе 1.8, вторая — в параграфе 1.9. Оба доказательства опираются на леммы сформулированные в параграфе 1.3.

1.3 Вспомогательные утверждения

Доказательства теорем, сформулированных в параграфе 1.2, мы для удобства разобьем на леммы, перечисленные в этом параграфе.

Лемма 1. Пусть фиксированы натуральное число д и положительные константы К1 и С. Тогда существует такое В1 > 0; что неравенство

х(1п^к)^(В1к)Сп (1.3)

справедливо для любого натурального п и любого натурального к < К1.

Доказательство этой леммы см. в параграфе 1.5.

Лемма 2. Пусть фиксированы натуральное число д и положительное действительное число А, удовлетворяющее ограничению

Я^А<д + 1. (1.4)

Пусть также заданы положительные константы К1} К2, С и Ь, причем выполняются следующие условия:

Ь + 1

1 (КЛА ь\к2) > 36, (1.5)

к > 8ЬК2, (1.6)

4 > АС. (1.7)

■

Тогда существует положительное число В2, для которого неравенство

х(1п^к)^(В2к)Сп (1.8)

выполняется при любых натуральных к и п, удовлетворяющих ограничению

К2пА. (1.9)

Лемма 2 будет доказана в параграфе 1.6. Именно для доказательства этой леммы нам пригодится линейно-алгебраический метод. Линейно-алгебраическая часть доказательства вынесена отдельно в параграф 1.4.

Лемма 3. Пусть зафиксированы натуральное число д и положительные действительные константы К2, А и С, причем выполнены условия

К2 > 61, (1.10)

Тогда найдется положительная константа В3, для которой неравенство

х(^,к)>(В3к)Сп (1.12)

будет выполняться при любых натуральных к и п, удовлетворяющих ограничению

к > К2пЛ. (1.13)

1.4 Линейно-алгебраический метод

В доказательстве леммы 2 мы будем использовать следующее утверждение.

Лемма 4. Пусть заданы натуральные числа д, п и к, выбрано простое число р и определено множество запрещенных расстояний

А(р) г е Ы}. (1.14)

Пусть также зафиксировано натуральное число г, и множество V выбрано в пространстве I™ таким образом, что координаты любого вектора из V — натуральные числа от 1 до г, то есть

V С [1,...,г]п С Еп. (1.15)

Тогда имеет место неравенство

р-1

а(У, А(р)) < ^ С™(г - 1)т. (1.16)

т=0

Замечание. 1. Чтобы формулировка леммы была полностью корректной, положим значение биномиального коэффициента

С™ .= 0 при т > п,

а также будем полагать

00 . 1,

чтобы выражение (г-1)т имело смысл при г = 1 и т = 0. Отметим, однако, что в параграфе 1.6 мы будем использовать лемму 4 только при р < п и г > 1, поэтому такие «вырожденные» случаи нам не пригодятся.

2. Множество запрещенных расстояний А(р) формально является бесконечным. Однако само множество V конечно, так что по факту запрещается лишь конечное число расстояний.

Основная идея доказательства леммы 4 заключается в том, чтобы каждому вектору х Е V сопоставить некоторый многочлен Рх над полем рациональных чисел таким образом, что для любого независимого множества и С V набор многочленов

Рх, х Е и, (1.17)

окажется линейно независимым. Это позволит оценить сверху мощность множества и размерностью некоторого пространства многочленов Т, содержащего все векторы (1.17) (в этом и заключается суть линейно-алгебраического метода).

Доказательство. Рассмотрим произвольный вектор х = (х1,..., хп) из множества V. Мы хотим сопоставить этому вектору многочлен Рх над полем рациональных чисел Для этого будем действовать по следующей схеме.

Сначала определим на V функцию

- (\\х-у\\ду.

Таким образом, для каждого у = (у1,..., уп) Е V выполняется равенство

(1х{у) = - У^ + ••• + К - Уп^ (1-18)

где д — натуральное число. Кроме того, все координаты х^ и у^, ^ Е {1,...,п}, — натуральные числа от 1 до г (в силу условия (1.15)), поэтому функция <1Х принимает на V только целые значения.

Далее рассмотрим интерполяционный многочлен Q, обладающий свойством

д(х) = |ж|, ж Е {-(г-1),...,г-1}. (1.19)

Поскольку мы производили интерполяцию только по точкам с целыми абсциссами и ординатами, все коэффициенты многочлена Q являются рациональными, то есть Q Е ^[ж].

Для любого у = (у1,...,уп) ЕУ из равенства (1.18) и свойства (1.19) следует равенство

(1х{у) = (Я(х1- У1))9 + ••• + (Я(хп - у

Опять же, в силу того что д является натуральным числом, функция <1Х на множестве V совпадает с некоторым многочленом Ях Е ,..., уп]:

Лх{у) = Кх(у), УЕУ, (1.20)

— причем в каждый одночлен многочлена Я входит не более одной переменной. Иными словами, многочлен Ях представляет собой сумму рационального свободного члена с одночленами вида

Список литературы диссертационного исследования кандидат наук Бердников Алексей Викторович, 2021 год

Список литературы

1. Gardner, M. Mathematical Games: A new collection of "brain teasers" [Text] / M. Gardner // Scientific American. — 1960. — Vol. 203, issue 4. — P. 172—180.

2. Soifer, A. The Mathematical Coloring Book [Text] : Mathematics of Coloring and the Colorful Life of its Creators / A. Soifer. — New York : Springer New York, 2008. — 618 p.

3. Moser, L. Solution to problem 10 [Text] / L. Moser, W. Moser // Canadian Mathematical Bulletin. — 1961. — Vol. 4. — P. 187—189.

4. de Grey, A. D. N. J. The chromatic number of the plane is at least 5 [Text] / A. D. N. J. de Grey. — 2018. — Apr. 8. — arXiv: 1804.02385 [math.CO].

5. Nechushtan, O. On the space chromatic number [Text] / O. Nechushtan // Discrete Mathematics. — 2002. — Vol. 256, issues 1—2. — P. 499—507.

6. Coulson, D. A 15-colouring of 3-space omitting distance one [Text] / D. Coulson // Discrete Mathematics. — 2002. — Vol. 256, issues 1—2. — P. 83—90.

7. Exoo, G. On the chromatic number of R4 [Text] / G. Exoo, D. Ismailescu, M. Lim // Discrete & Computational Geometry. — 2014. — Vol. 52, no. 2. — P. 416—423.

8. Radoicic, R. Note on the chromatic number of the space [Text] / R. Radoicic, G. Toth // Discrete and Computational Geometry : The Goodman-Pollack Festschrift / ed. by B. Aronov [et al.]. — Berlin, Heidelberg : Springer Berlin Heidelberg, 2003. — P. 695—698. — (Algorithms and Combinatorics ; 25).

9. Райгородский, А. М. О хроматическом числе пространства [Текст] / А. М. Райгородский // Успехи математических наук. — 2000. — Т. 55, вып. 332, № 2. — С. 147—148.

10. Frankl, P. Intersection theorems with geometric consequences [Text] / P. Frankl, R. M. Wilson // Combinatorica. — 1981. — Vol. 1, no. 4. — P. 357—368.

11. Larman, D. G. The realization of distances within sets in Euclidean space [Text] / D. G. Larman, C. A. Rogers // Mathematika. — 1972. — June. — Vol. 19, issue 01. — P. 1—24.

12. Мощевитин, Н. Г. О раскрасках пространства Rn с несколькими запрещенными расстояниями [Текст] / Н. Г. Мощевитин, А. М. Рай-городский // Математические заметки. — 2007. — Т. 81, № 5. — С. 733—743.

13. Шитова, И. М. О хроматическом числе пространства с несколькими запрещенными расстояниями [Текст] / И. М. Шитова // Доклады Академии наук. — 2007. — Т. 413, № 2. — С. 178—180.

14. Райгородский, А. М. О хроматических числах вещественных и рациональных пространств с вещественными или рациональными запрещенными расстояниями [Текст] / А. М. Райгородский, И. М. Шитова // Математический сборник. — 2008. — Т. 199, № 4. — С. 107—142.

15. Пономаренко, Е. И. Новая нижняя оценка хроматического числа рационального пространства [Текст] / Е. И. Пономаренко, А. М. Райгородский // Успехи математических наук. — 2013. — Т. 68, вып. 5. — С. 183—184.

16. Бердников, А. В. О хроматическом числе евклидова пространства с двумя запрещенными расстояниями [Текст] / А. В. Бердников, А. М. Райгородский // Математические заметки. — 2014. — Т. 96, № 5. — С. 790—793.

17. Райгородский, А. М. Проблема Борсука и хроматические числа некоторых метрических пространств [Текст] / А. М. Райгородский // Успехи математических наук. — 2001. — Т. 56, вып. 1. — С. 107—146.

18. Оценка хроматических чисел евклидова пространства методами выпуклой минимизации [Текст] / Е. С. Горская [и др.] // Математический сборник. — 2009. — Т. 200, № 6. — С. 3—22.

19. Райгородский, А. М. Хроматические числа пространств с запрещенными одноцветными треугольниками [Текст] / А. М. Райгородский, Д. В. Самиров // Математические заметки. — 2013. — Т. 93, вып. 1. — С. 117—126.

20. Самиров, Д. В. Новые нижние оценки хроматического числа пространства с запрещенными равнобедренными треугольниками [Текст] / Д. В. Самиров, А. М. Райгородский // Динамические системы. — М. : ВИНИТИ РАН, 2013. — С. 252—268. — (Итоги науки и техники. Серия «Современная математика и ее приложения. Тематические обзоры» ; 125).

21. Самиров, Д. В. Новые оценки в задаче о хроматическом числе пространства с запрещенными равнобедренными треугольниками [Текст] / Д. В. Самиров, А. М. Райгородский // Доклады Академии наук. —

2014. — Т. 456, № 3. — С. 280—283.

22. О хроматическом числе пространства с запрещенным равносторонним треугольником [Текст] / А. Е. Звонарёв [и др.] // Математический сборник. — 2014. — Т. 205, № 9. — С. 47—90.

23. Звонарёв, А. Е. Улучшения теоремы Франкла — Рёдля о числе ребер гиперграфа с запрещенным пересечением и их следствия в задаче о хроматическом числе пространства с запрещенным равносторонним треугольником [Текст] / А. Е. Звонарёв, А. М. Райгородский // Геометрия, топология и приложения : Сборник статей. К 70-летию со дня рождения профессора Николая Петровича Долбилина / под ред. В. М. Бухштабера, А. Г. Сергеева. — М. : МАИК «Наука/Интерпериодика», 2015. — С. 109—119. — (Труды Математического института имени В. А. Стеклова ; 288).

24. Самиров, Д. В. Об одной задаче, связанной с оптимальной раскраской пространства без одноцветных равнобедренных треугольников [Текст] / Д. В. Самиров, А. М. Райгородский // Труды МФТИ. —

2015. — Т. 7, № 2. — С. 39—50.

25. Райгородский, А. М. О хроматическом числе пространства с метрикой

[Текст] / А. М. Райгородский // Успехи математических наук. — 2004. — Т. 59, вып. 5 (359). — С. 161—162.

26. Райгородский, А. М. О хроматических числах метрических пространств [Текст] / А. М. Райгородский // Чебышёвский сборник. — 2004. — Т. 5, вып. 1. — С. 165—173.

27. Furedi, Z. Distance graph on 1П with lT norm [Text] / Z. Furedi, J.-H. Kang // Theoretical Computer Science. — 2004. — Vol. 319, issues 1—3: Combinatorics of the Discrete Plane and Tilings. — P. 357—366.

28. Купавский, А. Б. О хроматическом числе ЕП с множеством запрещенных расстояний [Текст] / А. Б. Купавский // Доклады Академии наук. — 2010. — Т. 435, № 6. — С. 740—743.

29. Kupavskiy, A. On the chromatic number of ЕП with an arbitrary norm [Text] / A. Kupavskiy // Discrete Mathematics. — 2011. — Vol. 311, issue 6. — P. 437—440.

30. Харари, Ф. Теория графов [Текст] / Ф. Харари ; под ред. Г. П. Гаври-лова ; пер. с англ. В. П. Козырева. — М. : Мир, 1973. — 301 с.

31. Bruijn, N. G. de. A colour problem for infinite graphs and a problem in the theory of relations [Text] / N. G. de Bruijn, P. Erdos // Proceedings of the Koninklijke Nederlandse Akademie van Wetenschappen. Series A: Mathematical Sciences. — 1951. — Vol. 54, no. 5. — P. 371—373.

32. Babai, L. Linear algebra methods in combinatorics [Text] / L. Babai, P. Frankl. — Chicago : The University of Chicago, 1992. — 225 p.

33. Райгородский, А. М. Линейно-алгебраический метод в комбинаторике [Текст] / А. М. Райгородский. — 2-е изд. — М. : МЦНМО, 2015. — 144 с.

34. Мак-Вильямс, Ф. Дж. Теория кодов, исправляющих ошибки [Текст] / Ф. Дж. Мак-Вильямс, Н. Дж. А. Слоэн ; пер. с англ. И. И. Грушко, В. А. Зиновьева. — М. : Связь, 1979. — 744 с.

35. Bassalygo, L. Codes with forbidden distances [Text] / L. Bassalygo, G. Cohen, G. Zemor // Discrete Mathematics. — 2000. — Vol. 213, issues 1—3. — P. 3—11.

36. Райгородский, А. М. О дистанционных графах, имеющих большое хроматическое число, но не содержащих больших симплексов [Текст] / А. М. Райгородский // Успехи математических наук. — 2007. — Т. 62, вып. 6 (378). — С. 187—188.

37. Raigorodskii, A. M. Small clique and large chromatic number [Text] / A. M. Raigorodskii, O. I. Rubanov // Electronic Notes in Discrete Mathematics. — 2009. — Vol. 34. — P. 441—445.

38. Raigorodskii, A. M. On the clique and the chromatic numbers of high-dimensional distance graphs [Text] / A. M. Raigorodskii, O. I. Rubanov // Number Theory and Applications : Proceedings of the International Conferences on Number Theory and Cryptography / ed. by S. D. Adhikari,

B. Ramakrishnan. — Gurgaon : Hindustan Book Agency, 2009. — P. 149— 157.

39. Райгородский, А. М. О графах расстояний с большим хроматическим числом и без больших клик [Текст] / А. М. Райгородский, О. И. Рубанов // Математические заметки. — 2010. — Т. 87, вып. 3. —

C. 417—428.

40. Демёхин, Е. Е. Дистанционные графы, имеющие большое хроматическое число и не содержащие клик или циклов заданного размера [Текст] / Е. Е. Демёхин, А. М. Райгородский, О. И. Рубанов // Математический сборник. — 2013. — Т. 204, № 4. — С. 49—78.

41. Купавский, А. Б. О дистанционных графах с большим хроматическим и малым кликовым числами [Текст] / А. Б. Купавский, А. М. Райгородский // Доклады Академии наук. — 2012. — Т. 444, № 5. — С. 483—487.

42. Купавский, А. Б. Явные и вероятностные конструкции дистанционных графов с маленьким кликовым и большим хроматическим числами [Текст] / А. Б. Купавский // Известия Российской академии наук. Серия математическая. — 2014. — Т. 78, № 1. — С. 3—35.

43. Erdös, P. Graph theory and probability [Text] / P. Erdös // Canadian Journal of Mathematics. — 1959. — Vol. 11. — P. 34—38.

44. Borsuk, K. Drei Sätze über die n-dimensionale euklidische Sphäre [Text] / K. Borsuk // Fundamenta Mathematicae. — 1933. — Jg. 20. — S. 177190.

45. Kahn, J. A counterexample to Borsuk's conjecture [Text] / J. Kahn, G. Kalai // Bulletin (new series) of the AMS. — 1993. — Vol. 29. — P. 60—62.

46. Райгородский, А. М. Об одной оценке в проблеме Борсука [Текст] / А. М. Райгородский // Успехи математических наук. — 1999. — Т. 54, вып. 2. — С. 185—186.

47. Raigorodskii, A. M. Cliques and cycles in distance graphs and graphs of diameters [Text] / A. M. Raigorodskii // Discrete Geometry and Algebraic Combinatorics / ed. by A. Barg, O. R. Musin. — Providence, Rhode Island : American Mathematical Society, 2014. — P. 93—109. — (Contemporary Mathematics ; 625).

48. Schramm, O. Illuminating sets of constant width [Text] / O. Schramm // Mathematika. — 1988. — Vol. 35. — P. 180—189.

49. Kupavskii, A. A counterexample to Borsuk's conjecture [Text] / A. Ku-pavskii, A. Raigorodskii // Moscow Journal of Combinatorics and Number Theory. — 2012. — Vol. 2. — P. 27—48.

50. Алон, Н. Вероятностный метод [Текст] : пер. с англ. / Н. Алон, Д. Спенсер. — 2-е изд. — М. : БИНОМ. Лаборатория знаний, 2011. — 320 с.

51. Baker, R. C. The Difference Between Consecutive Primes, II [Text] / R. C. Baker, G. Harman, J. Pintz // Proceedings of the London Mathematical Society. — 2001. — Vol. 83, issue 3. — P. 532—562.

Публикации автора по теме диссертации

52. Бердников, А. В. Оценка хроматического числа евклидова пространства с несколькими запрещенными расстояниями [Текст] / А. В. Бердников // Математические заметки. — 2016. — Т. 99, № 5. — С. 783—787.

53. Бердников, А. В. Хроматическое число с несколькими запрещенными расстояниями в пространстве с l^-метрикой [Текст] / А. В. Бердников // Современная математика и ее приложения. — 2016. — Т. 100. — С. 12—18.

54. Бердников, А. В. Хроматические числа графов расстояний с несколькими запрещенными расстояниями без клик заданного размера [Текст] / А. В. Бердников // Проблемы передачи информации. — 2018. — Т. 54, вып. 1. — С. 78—92.

55. Бердников, А. В. Оценки чисел борсука по дистанционным графам специального вида [Текст] / А. В. Бердников, А. М. Райгородский // Проблемы передачи информации. — 2021. — Вып. 2. — С. 44—50.

56. Бердников, А. В. Числа Борсука множеств специального вида на сферах малого радиуса [Текст] / А. В. Бердников // Труды МФТИ. — 2021. — Т. 13, вып. 3. — С. 29—40.