Дистанционные графы в рациональных пространствах тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Соколов Артемий Алексеевич

• Соколов Артемий Алексеевич
• кандидат наук
• 2023

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

Введение

Глава 1. Рациональный дистанционный граф с произвольной

квадратичной метрикой

1.1 Основные определения и свойства

1.2 Основные свойства 0(0"-, д)

1.2.1 С((^п,д) как подмножество

1.3 Кликовое число С(0",д)

1.3.1 Нахождение кликового числа

1.4 Хроматические числа

1.4.1 Малые размерности

1.4.2 Растущая размерность

1.4.3 Связь с аффинным хроматическим числом

1.5 Изоморфизмы графов

1.6 «Обращение вложения»

Глава 2. Рациональная проблема Борсука с произвольной

квадратичной метрикой

Глава 3. Псевдоевклидово пространство

3.1 Случай (г,в) = (1, 1)

3.2 Произвольные г, в =

Заключение

Список обозначений

Стр.

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

Приложение А. Свойства рациональных квадратичных форм

А.1 Основные свойства

А.2 Инварианты

Введение диссертации (часть автореферата) на тему «Дистанционные графы в рациональных пространствах»

Введение

Дистанционные графы

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

Несмотря на простоту формулировки, эта проблема до сих пор не решена, а на данный момент известны лишь следующие оценки:

5 < х(^2) < 7,

причем верхняя оценка была получена почти одновременно с постановкой задачи, а нижняя оценка была получена в 2018 году в работе [2].

Эта проблема была достаточно быстро обобщена на случай произвольного и величина х(Кп), равная минимальному количеству

цветов, в которые можно покрасить все точки так, чтобы точки на расстоянии 1 были покрашены в разные цвета, называется хроматическим числом пространства

В пространствах К3 и К4 известны следующие оценки:

6 ^ Х(К3) ^ 15 [3; 4]. 9 < х(^4) < 49 [5; 6].

Как видно, зазор между верхними и нижними оценками очень сильно растет.

И в растущей размерности этот зазор только увеличивается, на данный момент известны следующие оценки:

(1.239 + о(1))п ^ х(^п) ^ (3 + о(1))п;

где верхняя оценка получена Ларманом и Роджерсом [7], а нижняя — в 2000 году Райгородским [8].

Хроматические числа пространств тесно связаны с понятием дистанционного графа, являющегося основным объектом этой работы. Граф называется дистанционным графом в если его вершинами являются точки в а ребрами соединены те пары точек, которые находятся на расстоянии 1 друг от друга.

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

Знаменитая теорема де Брёйна - Эрдёша (см. [9]) утверждает, что если хроматическое число бесконечного графа конечно, то оно достигается на его конечном подграфе, а именно, существует его конечный подграф с хроматическим числом, равным хроматическому числу всего графа.

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

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

Так возникла идея рассмотрения рационального аналога этой задачи для пространства Q2 (пространства рациональных точек плоскости) в работе Вудала [10], в которой он показал, что

Х(02) = 2.

Определение х(02) получается дословным повторением определения %(К2), только для пространства Q2 с евклидовой метрикой.

В 1970-х годах Бенда и Перлес написали рукопись (впоследствии опубликованную в 2000 году в работе [11]), в которой предложили альтернативное доказательство того, что х(02) = 2, а также показали, что

Х(03) = 2 х(04) = 4

Отметим, что все раскраски в к цветов, дающие оценки сверху, обладают свойством аддитивности, т.е. являются таким гомоморфизмом из Qn в группу что соседние вершины переходят в разные элементы. Более подробно про аддитивные раскраски можно прочитать в работе [12] и работе [13], к которой мы еще вернемся.

Стоит отметить то, насколько разными получаются результаты, полученные в вещественном и рациональном случае.

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

8 ^ Х(05) ^ Х(^5) ^ 140,

где оценка сверху получена в работе [6], а нижняя оценка получена в 2008 году в работе [14].

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

Заметим, что величина ¡х>(Кп), равная кликовому числу дистанционного графа вершинами которого служат все точки в точности равна п + 1.

Однако в рациональном случае ответ уже не так очевиден. В 1988 году Чилакамарри опубликовал работу [15], в которой изучил кликовое число ¡х>^п), а именно максимальное количество точек в Qn таких, что попарные расстояния между ними равны 1. Он доказал, что ^ п — 1, и предъявил

способ найти точное значение в зависимости от того, решается ли определенное квадратное диофантово уравнение. Далее, в 2005 году Элсхольц и Клотц в работе [16] решили это квадратное диофантово уравнение в зависимости от разложения на простые множители числа п.

В малых размерностях для кликовых чисел получается следующая таблица:

п 1 2 3 4 5 6 7 8

ш(ОГ) 2 2 2 4 4 6 8 9

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

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

5, верхние оценки для х(Оп) получаются только с помощью очевидного неравенства х(Оп) ^ х(Кп).

Стоит отметить, что оценка х(Кп) ^ (1.239 + о(1))п получается с помощью линейно-алгебраического метода и рассмотрения дистанционного графа, вершины которого являются подмножеством множества {—1, 0,1}п.

Однако, у этого графа соседние точки находятся на иррациональном расстоянии, что не позволяет рассуждением подобия сделать его равным 1, сохранив рациональность координат. Эту проблему исправили Е. И. Пономаренко и А. М. Райгородский в работе [17], модифицировав конструкцию для и получив оценку

Х(0П) ^ (1.199 + о(1))п.

Мы покажем, что иррациональность расстояния между соседними точками не такая большая проблема, и поднимем оценку до неравенства

Х(0П) ^ (1.239 + о(1)Г.

Определение дистанционного графа можно обобщить так, чтобы проводились ребра между всеми парами точек, находящимися на расстоянии а для некоторого фиксированного а > 0. Это расстояние а будем называть запрещенным расстоянием дистанционного графа.

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

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

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

В связи с этим для любого (I Е 0_,(1 > 0, определим граф С(Оп,(1), вершины которого являются точками в Qn, а соединенные ребром вершины находятся на расстоянии Использование в этом определении логично потому, что в любое расстояние между рациональными точками является корнем из рационального числа.

В работе [18] изучается величина и(Оп,й), которая равна максимальному количеству точек в Qn таких, что попарные расстояния между ними равны

Показано, что это значение зависит от величины (1, а также доказано неравенство ш(Оп,й) ^ п — 3 для произвольных п и d. Позднее один из авторов этой статьи, М.Нобл, в работе [19] доказал неравенство ^ п — 2 и показал, что эта оценка неулучшаема.

Также естественным образом возникает вопрос о значении хроматического числа х(Оп^) с запрещенным расстоянием

Например, известно (см. [18]), что все непустые

графы

изоморфны между собой, а также если п делится на 4, то все графы С(Оп,<Л) изоморфны между собой, откуда следует, что х(О:2,й) = 2 и х(О.4,3) = 4 для любого й. Для случая О3 точное значение хроматического числа найти пока не удается. Известно, что х(О3,^) Е {2,3, 4}, но не известно ни одного (1, для которого бы выполнялось х(О3= 3. Более подробно про О3 можно прочитать в работах [20—24].

Мы обобщаем определение дистанционного графа, меняя метрику пространства Оп. А именно для произвольной положительно определенной

квадратичной формы д на п переменных будем измерять расстояние между точками х, у £ Оп по формуле у7д(х — у).

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

Мы изучим основные характеристики полученных графов, используя теорию рациональных квадратичных форм.

Теорема Бекмана — Куорлза

В 1953 году Бекман и Куорлз опубликовали работу [25], в которой доказали теорему, гласящую, что любое отображение из в (п > 1), сохраняющее расстояние 1, является изометрией.

Рациональный аналог этой теоремы заключается в простой переформулировке, заменяющей на Оп. А именно, любое отображение из О^п в о« (п > 1), сохраняющее расстояние 1, является изометрией.

Рациональный аналог активно изучался Д. Заксом, который, в частности, доказал, что он верен для всех четных п и всех п вида 2к2 — 1, где к £ Ж. Более подробно об этом можно прочитать в работах [26—28]. Однако в случае произвольного п аналогичная теорема доказана не была.

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

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

следовать эквивалентность квадратичных форм. Эту гипотезу мы докажем в размерности 2 и для произвольного классического евклидова случая.

Проблема Борсука

Еще одна классическая проблема комбинаторной геометрии, тесно связанная с задачами о хроматических числах пространств, это проблема Борсука о разделении множеств на части меньшего диаметра.

Обозначим Ь(п) минимальное число частей меньшего диаметра, на которые разбивается любое ограниченное множество в Кп. Классическая гипотеза Борсука заключается в том, что Ь(п) = п +1. На данный момент известно, что гипотеза верна при п ^ 3 и неверна при п ^ 64 (см. [29—33]).

Непосредственным рациональным аналогом величины Ь(п) в <п служит величина Ь<(п), равная минимальному числу частей меньшего диаметра, на которые разбивается любое ограниченное множество в <п. Несложно заметить из рассуждений непрерывности, что Ь<(п) = Ь(п), что говорит о необходимости рассмотрения другого определения для рационального случая.

Следуя этой необходимости, можно определить величину / (п) следующим образом:

^ (п) = тах \(А), АСЕ™ А=1

где через х(А) обозначается хроматическое число дистанционного графа, вершинами которого являются точки из множества А, а ребрами соединены точки, находящиеся на расстоянии 1.

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

Sn С Rn+1 диаметра 1 величина х(&п) равна 2, тогда как частей меньшего диаметра нужно п + 2.

Рациональным аналогом величины f (п) служит величина

fq(n) = max х(А).

v AcQ",diam A=1

Рациональный аналог гипотезы Борсука заключается в том, что /<Q>(n) = w(Qn). Как и следовало ожидать, данная гипотеза неверна. В работе Пономаренко и Райгородского [34] доказано, что гипотеза неверна для всех п ^ 946.

Также в работе [34] был сформулирован следующий аффинно-рациональный аналог числа Борсука

/äff Ы) = max х(А).

rn€N,AcQm,affdim A<n,diam A=1

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

Аффинно-рациональным аналогом гипотезы Борсука служит утверждение faff (п) = п + 1. В работе Пономаренко и Райгородского [34] доказано, что эта гипотеза неверна для всех п € [561, 757] U [903,

Мы предложим обобщение рациональной проблемы Борсука на случай произвольной рациональной квадратичной формы, и, используя эти методы, докажем, что аффинно-рациональная проблема Борсука для величины /aff неверна для всех п ^ 65, а для величины /q неверна для всех п ^ 68.

Псевдоевклидово пространство

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

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

Целью данной работы является исследование дистанционных графов в рациональных пространствах.

Научная новизна: исследование дистанционных графов в рациональных пространствах.

Практическая значимость. Диссертация носит теоретический характер.

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

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

2. Найден явный способ вычисления кликового числа дистанционного графа в рациональном пространстве для произвольной рациональной квадратичной формы.

3. Получено улучшение нижней оценки хроматического числа рационального пространства.

4. Сформулирован корректный аналог рациональной задачи Борсука для произвольной рациональной квадратичной формы.

5. Исследованы размерности контрпримеров для рациональной задачи Борсука.

6. Найдена сильная верхняя оценка на диаметры «дистанционных» графов в псевдоевклидовых пространствах.

Достоверность. Все результаты работы строго доказаны.

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

— Международная конференция «2nd Hungarian-Russian Combinatorics workshop», Будапешт, Венгрия, 27-29 июня, 2018.

— «Осенние математические чтения в Адыгее», АГУ, Майкоп, 12-17 октября, 2021.

— Спецсеминар «Дискретная геометрия и геометрия чисел», мехмат МГУ, Москва, 2022.

— Спецсеминар лаборатории комбинаторных и геометрических структур, МФТИ, Москва, 2022.

— Воркшоп по дискретной геометрии и оптимизации, АГУ, Майкоп, 6-12 июля, 2023.

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

Глава 1. Рациональный дистанционный граф с произвольной

квадратичной метрикой

Результаты этой главы опубликованы в работах [38] и [40].

1.1 Основные определения и свойства

Обозначим через Qn множество всех положительно определенных рациональных квадратичных форм от п переменных. Также обозначим

е = 1С=1 с».

Определение 1.1.1. Для каждой квадратичной формы q G определим граф G(Qn, q) = (V,, Е) следующим образом:

V = Е = {(x, y) | q(x- y) = 1}.

Пусть In(x) = x\ + ... + x2n — квадратичная форма, порождающая стандартную евклидову метрику. Тогда G(Qn,In) — стандартный дистанционный граф.

Для произвольного 0 < d G Q граф G(Qn, ^In) является стандартным дистанционным графом с запрещенным расстоянием Vd. Таким образом, введенное определение действительно обобщает стандартные определения дистанционных графов.

Определение 1.1.2. Мы будем писать, что q1 ~ q2, если dim q1 = dim q2 и существует преобразование Т G GL(dim q1, Q) такое, что q1(x) = q2(T x).

Следующая лемма показывает, что изоморфизм квадратичных форм влечет изоморфизм графов.

Лемма 1.1.3. Если qi — q2, то G(Qn,qi) ~ G(Qn,^).

Доказательство. Пусть Т — линейное отображение, переводящее qi в q2. Тогда несложно проверить, что Т является также изоморфизмом соответствующих графов. Действительно,

(x, y) G Ei ^ (x - y) = 1 ^ q2(Tx -Ty) = 1 ^ (Tx,Ty) G E2,

где Ei, E2 — множества ребер графов G(Qn, qi) и G(Qn, q2), соответственно. □

Q

Определение 1.1.4. Мы будем писать, что qi ^ q2, если существует квадратичная форма г G Qdim 92-dim qi такая, что для квадратичной формы h(x, y) := qi(x) + r(y) выполнено h — q2.

Лемма 1.1.5. Если qi Д q2, то G(Qdimqi,qi) С G(Qdimq2,52).

Доказательство. По определению, существует г G Qdimg2-dimqi такая, что для квадратичной формы h(x,y) := gi(x) + r(y) выполнено h — q2. По лемме 1.1.3 G(Qdim42,q2) ~ G(Qdimh,h). Если последний граф ограничить на первые dim qi координат, получится граф G(Qdim 41 ,qi), откуда получается утверждение леммы. □

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

В частности, далее мы будем повсеместно пользоваться леммой А.1.4,

Q

которая утверждает, что если dim q2 — dim qi ^ 3, что qi ^ q2.

1.2 Основные свойства С(Оп,д)

Для доказательства утверждений этого раздела нам понадобится следующая лемма.

Лемма 1.2.1 (Мейер, [35], IV, теорема 3, следствие 2). Рациональная квадратичная форма д(х) ранга п ^ 5 представляет 0 в О (существует нетривиальное рациональное решение д(х) =0) тогда и только тогда, когда она представляет 0 в К (существует нетривиальное вещественное решение я(х) = 0).

Теорема 1.2.2. Для произвольных п ^ 4 и д Е 0,п граф С(Оп,д) непустой.

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

V(X\, ..., Хп, Жп+1) Ц..., Хп) %п+\.

У этой формы ранг ^ 5. Также, поскольку она не является знакоопределенной, то она представляет 0 в К. Таким образом, по лемме 1.2.1, существует нетривиальное рациональное решение (х%,... , хп+х) уравнения г(х\,... ,хп+\) = 0. Заметим, что х2п+1 = 0, и легко видеть, что д( ^-,..., =1. □

^ \Жп+1 ' ' хп+1)

Следующее утверждение показывает точность условия п ^ 4.

Утверждение 1.2.3. Графы С(О2, 2х2 + 3у2) и С(О3, 2х2 + 3у2 + 3^2) пустые.

Доказательство. Покажем, что граф С(О3,2х2 + 3у2 + 3^2) пустой. Предположим противное, то есть что 2х2 + 3у2 + 3^2 = 1 для рациональных х,

у и Приведя к общему знаменателю, получим

2р2 + + 3г2 = й2,

где х = ^, у = - и ^ = - — наименьшие по модулю подходящие целые числа. Тогда 2р2 — 82 делится на 3, следовательно р и й обязаны делиться на 3. Тогда 2р2 — 82 делится на 9, то есть д2 + г2 делится на 3, что влечет делимость всех переменных на 3. Мы получили противоречие с тем, что р, д, г, в минимальные по модулю.

Граф С(О2,2х2 + 3у2) является подграфом С(О3,2ж2 + 3у2 + 3^2), следовательно, тоже пустой. □

Следующая лемма дает четкий критерий непустоты графа С(Оп,д) для произвольного п.

О

Теорема 1.2.4. Граф С(Оп,д) непустой тогда и только тогда, когда 1\ ^ д или, эквивалентно, существует такая квадратичная форма г € 0,п—\, что

д(хЛ, ...,хп) ~ х\ + г(х,2,..., хп).

Доказательство. Если д(х\,...,хп) ~ х2 + г(х2,... ,хп), то по лемме 1.1.3 выполнено С(Оп, (¡) ~ С(Оп, х\ + г(х2,..., хп)), а в последнем найдется ребро между точкаи (0,0,... , 0) и (1, 0,... , 0).

Наоборот, пусть граф С(Оп, (¡) непустой, тогда возьмем V = (у\,у2, ..., уп) — решение уравнения д(х) = 1. Рассмотрим Т € СЬ(п, О) такое, что г(х) =

(¡(Т х) диагональна и равна а^2 + ... + апх1,, Тогда 1 = (¡(у) = г(е\) = а\, что

Г О / \ 1-.

означает, что Я (х). □

В своей статье [15] Киран Чилакамарри, доказал, что графы С(О2,12), С (О3, /3) и С(О4,14) несвязные. В той же статье показано, что при п ^ 5 граф

С(Оп,1п) связный. Ниже мы обобщаем это утверждение на случай произвольной квадратичной формы д.

Теорема 1.2.5. Для произвольного п ^ 5 и квадратичной формы д(х) Е 0,п граф С(Оп,д) связный.

Доказательство теоремы 1.2.5. Рассмотрим Т Е СЬ(п, О) такое, что д(Т х) диагональна. Переопределим д(х) как д(Т х), по лемме 1.1.3 граф от этого не изменится.

Без ограничения общности можно сказать, что квадратичная форма д(х) имеет вид д(х) = ах\ + г(х2,..., хп), а > 0.

Возьмем произвольное рациональное 0 < с < —^ и рассмотрим квадратичную форму ^(х) = г(х2,...,хп) — (1 — ас2)х2. Существует вещественное решение ^ (х) = 0, а, значит, также существует рациональное решение этого уравнения. Поделим это решение на Х\, который, очевидно, ненулевой.

Пусть (х2,...,хп) — рациональное решение уравнения г(х2,... ,хп) = 1 — ас2, которое существует по лемме 1.2.1. Заметим, что точки (0, 0,... , 0), (с,х2,... ,хп) и (2с, 0,... , 0) образуют путь длины 2 в С(Оп,д). Поскольку мы можем взять произвольное достаточно маленькое рациональное с, то можно увидеть, что существует путь из (0,0,..., 0) в (х, 0,..., 0) для любого х Е О.

Применяя эти рассуждения последовательно для каждой координаты, получаем, что можно найти путь из (0, 0,... , 0) до каждой точки из Оп, что и означает связность графа. □

1.2.1 С«п,д) как подмножество Мп

Лемма 1.2.6. Пусть ... ,юп) — базис в такой, что ) € О для любых 1 ^ г,] ^ п, где (х, у) — скалярное произведение векторов х и у. Через

V обозначим множество

V = span<Q)({,Ul,г>2,... ,уп}) := {Ат + ... + | Аг € О}. Граф С(У) определим как граф с множеством вершин V, а вершины соединим ребром, если они находятся на расстоянии 1.

Тогда С(У) ~ С«п,д), где д — квадратичная форма с матрицей

Щ,=1.

Доказательство. Квадрат длины вектора Х\У\ + ... + хпуп € V равен

п

(хгУг + ... + хпуп,хгУ1 + ... + хпуп) = )хгх3 = д(хЛ,... ,хп).

Таким образом несложно видеть, что соответствие

Т : Х1У1 + ... хпуп ^ (х1,...,хп) является изоморфизмом между С(У) и С«п,д). □

1.3 Кликовое число С«п,д)

Этот раздел посвящен вопросу нахождения кликового числа ш(С«п,д)), а именно наибольшего количества вершин графа, попарно соединенных ребрами.

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

. . . , ^п^ ^ ^ .

Матрица этой квадратичной формы имеет 1 на главной диагонали и | вне её. Несложно видеть, что она является матрицей Грама набора ребер правильного симплекса размерности п со стороной 1, исходящих из одной вершины.

В этом разделе мы будем повсеместно использовать определения и теоремы из теории рациональных квадратичных форм, про которые можно прочитать в главе А. Более подробно про теорию рациональных квадратичных форм можно прочитать в книге [35].

1.3.1 Нахождение кликового числа

В этом разделе мы покажем, как для произвольной квадратичной формы д найти ш(С(Оп,д)) и, как следствие, упростим доказательства нескольких утверждений из статьи [18].

Теорема 1.3.1.

и(С(Оп,д)) = п + 1 ^ д — Яп.

Доказательство. Если д — Бп, то С(Оп,д) ~ С(ОП,5П). Осталось проверить, что ш(С(Оп, Зп)) = п + 1. Заметим, что следующий набор точек является в этом графе кликой:

ео = (0, 0,0,..., 0) в! = (1, 0,0,..., 0) е2 = (0,1,0,..., 0)

еп = (0,0,0,..., 1)

Теперь докажем в обратную сторону. Пусть у0 = 0,у1,...,уп — (п + 1)-клика в С(Оп,д). Сделаем такое линейное преобразование Т, что Т е^ = г{ для всех 0 ^ % ^ п. Рассмотрим г(х) = д(Т х) = ^г^-. Видно, что в , г) точки е0, е1,..., еп образуют клику.

Отсюда получаем, что 1 = г(е,ь — е0) = Гц, а также 1 = г(е,ь — е^) = Гц + — Гц, откуда следует, что гг] = 1.

□

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

Теорема 1.3.2.

ш(С(Оп,о)) = 1 + тах{&: Бк Д д] Доказательство. Если Зк Д д, то С(О)к, Зк) С , д), а значит и

ш(в(ОГ,д)) ^ и(С(0.к,Як)) = к + 1.

Наоборот, пусть и(G(Qn,g)) ^ к + 1. Тогда рассмотрим аффинное

подпространство V размерности к, содержащее (к + 1)-клику. Заметим, что по

теореме 1.3.1 в этом подпространстве форма эквивалентна Зк, а значит и О

Д я. □

Теорема 1.3.3. Для любой квадратичной формы д выполнено неравенство

и(С(Оп,д)) ^ п — 2.

О

Доказательство. Используя лемму А.1.4, мы получаем, что Зп—3 Д д. Подставляя это в теорему 1.3.2 получаем, что ш(С(Оп, д)) ^ ш(С(Оп—3, Бп-з)) = п — 2. □

Эта теорема, в частности, является ответом на вопрос, поставленный в статье [18], на который позднее ответил один из авторов в статье [19].

Предыдущие две теоремы предоставляют конкретный алгоритм для вычисления кликового числа ш(С«п,д)); оно может принимать только четыре возможных значения, а проверка вложимости одной квадратичной формы в другую легко осуществляется за конечное время.

Давайте отметим, что результат, получаемый с помощью теоремы 1.3.2 в случае д = 1п, совпадает с известными формулами в работе [36].

Утверждение 1.3.4. Теорема 1.3.2, примененная в случае д = 1п, совпадает с результатом Чилакамарри.

Доказательство этого утверждения будет сильно опираться на утверждения и определения из главы А.

Рассмотрим множество V = {р : р простое} и {то} и для каждого V € V рассмотрим величины (а,Ь)„ — символ Гильберта, О(д) и Е1У (д) — дискриминант и инвариант Хассе-Минковского квадратичной формы д.

Также напомним лемму А.1.1, которая утверждает, что (а, Ь)„ = 1 для всех и € V ^^ уравнение ^2 = ах2 + Ьу2 имеет нетривиальное рациональное решение.

Доказательство. Напомним, что в работе Чилакамарри [15] была классификация с использованием следующего утверждения:

пх2 — 2(п — 1)у2 = г2 имеет решение с х = 0. (1.1)

Заметим, что наличие такого решения эквивалентно наличию нетривиального решения уравнения

х2 = 2п(п — 1)у2 + пх2.

По лемме А.1.1 это эквивалентно тому, что

Уи € V (2п(п — 1), п)^ = 1.

Поскольку (п, —п)^ = (п, 1 — п)„ = 1, утверждение выше эквивалентно тому, что (2,п)„ = 1 для всех и € V.

В работе Чилакамарри была следующая классификация:

п + 1, п четное и п + 1 является квадратом;

w(Qn) =

п, п четное и п + 1 не является квадратом; ^ п + 1, п нечетное, (1.1) выполняется и ^у1 является квадратом; п, п нечетное, (1.1) выполняется и не является квадратом; п — 1, п нечетное, (1.1) не выполняется. Также напомним определение из главы А:

Хп — <

п + 1, п четное; (п + 1) /2, п нечетное.

Также известно (см. главу А), что D (Sn) = Хп mod

и

Ev (Sn) — (п + 1, Xn-\)v — <

(п + 1, -2)^ , п четное; (п + 1, —1)^ , п нечетное.

Случай 1. ш (Оп) = п + 1 ^^ Зп ~ 1п, что эквивалентно выполнению двух пунктов:

- 1 = И(1п) = Я(£„) = Лп mod

— Уи € V выполняется 1 = Еу (1п) = Еу (5П) = (п + 1, Хп—1)1/. Из первого пункта следует, что Хп является квадратом.

Случай 1.1. п четное. В этом случае Хп = п + 1 является квадратом, из-за чего второй пункт автоматически выполняется.

Случай 1.2. п нечетное. В этом случае Хп = ^у1 является квадратом, и тогда (п + 1,Ап-1)^ = (п + 1, _1)^ = (2, _1)^ = 1 для всех V е V.

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

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

1. Soifer, A. The mathematical coloring book: Mathematics of coloring and the colorful life of its creators / A. Soifer. — Springer, 2009.

2. Grey, A. D. de. The Chromatic Number of the Plane Is at least 5 / A. D. de Grey // Geombinatorics. — 2018. — Т. 28. — С. 18.

3. Nechushtan, O. On the space chromatic number / O. Nechushtan // Discrete Mathematics. — 2002. — Т. 256, № 1. — С. 499—507. — URL: https://www. sciencedirect.com/science/article/pii/S0012365X00004064.

4. Radoicic, R. Note on the Chromatic Number of the Space / R. Radoicic, G. Toth // Discrete and Computational Geometry: The Goodman-Pollack Festschrift / под ред. B. Aronov [и др.]. — Berlin, Heidelberg : Springer Berlin Heidelberg, 2003. — С. 695—698. — URL: https://doi.org/10.1007/978-3-642-55566-4_32.

5. Exoo, G. On the Chromatic Number of R4 / G. Exoo, D. Ismailescu, M. Lim // Discrete & Computational Geometry. — 2014. — Т. 52, № 2. — С. 416—423.

6. Upper bounds on chromatic number of En in low dimensions / A. Arman [и др.] // arXiv preprint arXiv:2112.13438. — 2021.

7. Larman, D. G. The realization of distances within sets in Euclidean space / D. G. Larman, C. A. Rogers // Mathematika. — 1972. — Т. 19, № 1. — С. 1—24.

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

9. Bruijn, N. d. A colour problem for infinite graphs and a problem in the theory of relations / N. d. Bruijn, P. Erdos // Indigationes Mathematicae. — 1951. — Т. 13. — С. 371—373.

10. Woodall, D. Distances realized by sets covering the plane / D. Woodall // Journal of Combinatorial Theory, Series A. — 1973. — Т. 14, № 2. — С. 187—200. — URL: https://www.sciencedirect.com/science/article/pii/0097316573900204.

11. Benda, M. Colorings of metric spaces / M. Benda, M. Perles // Geombinatorics. — 2000. — Т. 9, № 3. — С. 113—126.

12. Johnson, P. D. Coloring abelian groups / P. D. Johnson // Discrete Mathematics. — 1982. — Т. 40, № 2/3. — С. 219—223.

13. Fischer, K. G. Additive k-colorable extensions of the rational plane / K. G. Fischer // Discrete mathematics. — 1990. — Т. 82, № 2. — С. 181—195.

14. Cibulka, J. On the chromatic number of real and rational spaces / J. Cibulka // Geombinatorics. — 2008. — Т. 18. — С. 53—66.

15. Chilakamarri, K. B. Unit-distance graphs in rational n-spaces / K. B. Chilakamarri // Discrete mathematics. — 1988. — Т. 69, № 3. — С. 213—218.

16. C. Elsholtz, W. K. Maximal Dimension of Unit Simplices / W. K. C. Elsholtz // Discrete Comput Geom. — 2005. — Т. 34. — С. 167—177.

17. Е.И. Пономаренко, А. Р. О хроматическом числе пространства Qn / А. Р. Е.И. Пономаренко // Труды МФТИ. — 2012. — Т. 4, № 1. — С. 127—130.

18. Bau, S. On single-distance graphs on the rational points in Euclidean spaces / S. Bau, P. Johnson, M. Noble // Canadian Mathematical Bulletin. — 2021. — Т. 64, № 1. — С. 13—24.

19. Noble, M. Embedding euclidean distance graphs in R n and Q n / M. Noble // Aequationes mathematicae. — 2022. — Т. 96, № 5. — С. 927—938.

20. J.Burkett. Explicit colorings of Z3 and Z4 with four colors to forbid arbitrary distances / J.Burkett // Geombinatorics. — 2009. — Т. 18. — С. 149—152.

21. Chow, T. Distances forbidden by two-colorings of Q and An / T. Chow // Discrete mathematics. — 1993. — Т. 115, № 1—3. — С. 95—102.

22. Johnson, P. Bi(Q3) = 4 / P. Johnson, A. Schneider, M. Tiemeyer // Geombinatorics. — 2007. — Т. 16. — С. 356—362.

23. Noble, M. On 4-chromatic subgraphs of G(Q3,d) / M. Noble // Australasian J. Comb. — 2016. — Т. 65. — С. 59—70.

24. Joe, J. A Triangle-free, 4-chromatic Q3 Euclidean Distance Graph Scavenger Hunt! / J. Joe, M. Noble. — 2023. — arXiv: 2303.09513 [math.CO].

25. Beckman, F. S. On isometries of Euclidean spaces / F. S. Beckman, D. A. Quarles // Proceedings of the American Mathematical Society. — 1953. — Т. 4, № 5. — С. 810—815.

26. Zaks, J. A discrete form of the Beckman-Quarles theorem for rational spaces / J. Zaks // Journal of Geometry. — 2001. — Т. 72, № 1. — С. 199—205.

27. Zaks, J. The Beckman-Quarles theorem for rational spaces / J. Zaks // Discrete mathematics. — 2003. — Т. 265, № 1—3. — С. 311—320.

28. Zaks, J. The Beckman-Quarles theorem for rational d-spaces, d even and d ^ 6 / J. Zaks, R. Connelly // Discrete Geometry / под ред. A. Bezdek. — Boca Raton : CRC Press, 2003. — Гл. 13.

29. Raigorodskii, A. M. Coloring distance graphs and graphs of diameters / A. M. Raigorodskii // Thirty essays on geometric graph theory. — 2013. — С. 429—460.

30. Brass, P. Research problems in discrete geometry. Т. 18 / P. Brass, W. O. Moser, J. Pach. — Springer, 2005.

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

32. Raigorodskii, A. M. Cliques and cycles in distance graphs and graphs of diameters. / A. M. Raigorodskii // Discrete geometry and algebraic combinatorics. — 2013. — С. 93—109.

33. Raigorodskii, A. M. Combinatorial geometry and coding theory / A. M. Raigorodskii // Fundamenta Informaticae. — 2016. — Т. 145, № 3. — С. 359—369.

34. Купавский, А. О некоторых аналогах проблемы Борсука в пространстве Qn / А. Купавский, Е. Пономаренко, А. Райгородский // Труды Московского физико-технического института. — 2012. — Т. 4, № 1—13. — С. 81—90.

35. Serre, J.-P. A course in arithmetic / J.-P. Serre. — New York [u.a.] : Springer, 1973. — VIII, 115. — (Graduate texts in mathematics ; 7).

36. Chilakamarri, K. B. Unit-distance graphs, graphs on the integer lattice and a Ramsey type result / K. B. Chilakamarri, C. R. Mahoney // Aequationes Mathematicae. — 1996. — Т. 51, № 1/2. — С. 48—67.

37. Bondarenko, A. On Borsuk's conjecture for two-distance sets / A. Bondarenko // Discrete & Computational Geometry. — 2014. — T. 51, № 3. — C. 509—515.

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

38. Соколов, А. О хроматических числах рациональных пространств / А. Соколов // Математические заметки. — 2018. — Т. 103, № 1. — С. 120—128.

39. Соколов, А. О рациональных аналогах проблем Нелсона-Хадвигера и Борсука / А. Соколов, А. Райгородский // Чебышевский сборник. — 2018. — Т. 19, 3 (67). — С. 270—281.

40. Sokolov, A. On distance graphs in rational spaces / A. Sokolov // Moscow Journal of Combinatorics and Number Theory. — 2023. — Т. 12, № 2. — С. 165—173.

41. Соколов, А. Диаметры дистанционных графов в псевдоевклидовых пространствах / А. Соколов // Труды Московского физико-технического института. — 2023. — Т. 15, № 2. — С. 69—73.

Приложение А Свойства рациональных квадратичных форм

А.1 Основные свойства

Пусть V = {р : р простое} U {то}. Обозначим = R, и Qp — поле р-адических чисел для простого р. Также определим Q* = Q\{0} и

Q^ = {ж2|ж е Q*}.

Пусть А = diag (а1?..., an), где а, е Q и а, > 0. Тогда

n

— D (А) = ^ а, — определитель А

i=1

— Для каждого v е V определим инвариант Хассе - Минковского

Ev (А) = П (^)„ е {±1}

i<j

2

где : (Q*/Q^) ^ {±1} — символ Гильберта в Q^.

Символ Гильберта (а, равен 1 тогда и только тогда, когда z2 = аж2+ имеет нетривиальное решение (ж, у, z) в Q3. Эта величина легко вычислима и имеет следующие свойства [35]:

— ^ = ^ — ^ = К ^ • К с)г/

— = 1 — = (а>

— -«)г, = К 1 - ^ = 1 — П= 1

i/GV

Известно (см. [35]), что D mod Q2 и Ev для и G V единственные инварианты положительно определенных квадратичных рациональных форм, а именно если у двух форм совпадают все инварианты, они эквиваленты.

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

Лемма А.1.1. (Теорема Хассе - Минковского)

(a, b)v = 1 для всех и G V ^^ уравнение z2 = ах2 + by2 имеет нетривиальное рациональное решение.

Лемма А.1.2. Рассмотрим квадратичные формы А и В с сигнатурами (г, s) и (г',s') соответственно. Тогда АчВ тогда и только тогда, когда существует квадратичная форма X такая, что

— sgnX = (г' — r,s' — s)

— dim X = dim В — dim А

— D (X) = D (А) D (В) mod Q^

— для всех v G V выполнено Ev (X) = Ev (В) • Ev (А) • (D (А), — D (В))v

Доказательство. Без ограничения общности предположим, что А = diag (ai,..., an) и В = diag (b1,..., bm). Тогда АчВ тогда и только тогда, когда существует X = diag (хп+1,..., хт) такая что С = diag (ai,... ап, xn+i,... ,Хт) ~В.

Для того, что С ~ В необходимо, чтобы выполнялось два условия:

— D (С) = D (В) mod Q^

— Ev(С) = Ev(В) для всех v G V.

D (С) = D (А) D (X) = D (В) mod Qa а значит D (X) = D (А) D (В) mod Q^.

Тогда для всех v G V выполнено

п т

Ev (В) = Ev (С) = Ц (ai, aj)v •Д П (ai,Xj)v • Ц (Xi,Xj)

i< j^n i=1 j=n+1 n+1< i <j

= Ev (А) • (D (А) ,D (X ))„ •Ev (X)

Е„ (X) = Е„ (А) • Е„ (В) • (В (А), В (А) В (В))„ =

= Еу (А) • Еу (В) • (В (Л), -В (В))„

□

Теперь сформулируем предложение 7 главы 4 в [35].

Утверждение А.1.3. Пусть числа Б, Е„ и (г, й) удовлетворяют следующим условиям:

1. Еу = 1 для почти всех V 6 V и П^у ^ = 1

2. если п = 1, то В^ = 1 или если п = 2 и образ В в Qг//Q2 равен -1.

3. г, s ^ 0 и г + s = п

4. А» = (-1)S, ^ = (-1)s( s-1)/2

Тогда существует квадратичная форма ранга п над Q с инвариантами В, Ev и (г, s), где (г, s) — сигнатура формы X.

Мы будем пользоваться следствием этого предложения, сформулированного в следующем виде.

Лемма А.1.4. Пусть и д2 — квадратичные формы, где dim g2 ^ dim +3,

Q

тогда ^ g2

Доказательство. По лемме А.1.2 необходимо проверить, что существует

квадратичная форма ранга dim g2 — dim g1, удовлетворяющая некоторым

условиям. Заметим, что все эти условия удовлетворяют пунктам 1, 3 и 4 из

предложения выше. А также выполняется пункт 2, поскольку

dim g2 — dim ^ 3. □

А.2 Инварианты Зп

Напомним, что квадратичная форма Зп(х1,... ,хп) равна ^, и матрица этой квадратичной формы совпадает с матрицей Грама правильного симплекса на п + 1 вершине со стороной 1.

Лемма А.2.1.

3, 4,...,

(п + 1)'

Доказательство. Обозначим через Т следующую матрицу:

Т =

1 0 0

0

2 1 0

1 1 1 2 3 1

1 1 \2 3 . .

/

И докажем, что /1 1

1 \2

1 1

= Т

/

100 0 4 0

0 0 I

0 0 0

п+1 2п /

Т

Т

у0 0 0 .

Для этого рассмотрим элемент на г-ой строке и на ]-ом столбце в правом произведении для некоторых % < ]. Он равен

¿-1

е

к=1

1

к + 1

к + 1 2к к + 1

1 , г + 1 + 1

1

2г г + 1

¡-1

Е

к=1

1

1

+ ^Т =

2 к( + 1) 2

(ё 1 к+^

1 _ 1

+ 2 = 2

1

п

1

2

Если i = j, то мы получаем

у1 1 к + 1 1 1 г + 1 1 1

^к + 1 ' 2fc ' fc + 1+ ' 2г ' =2 + 2 =

*=1

□

Для каждого & определим

А* = <

& + 1, & четное;

+ 1) /2, & нечетное;

Несложно видеть, что В (5-) = 1 ■ 4 ■ 4 ■ ... ■ —+1 = -+I = An mod

Лемма А.2.2.

В, (S*) = (fc + 1,А-—1),= ^

+ 1, -2)^ , к четное; (^ + 1, —1)^ , к нечетное.

Доказательство. Докажем это утверждение индукцией по Для к = 1 выполнено Еи ) = 1 и (2, —2)^ = 1.

Далее, для каждого к мы получаем

(6^+1) = Еу ) • (А ( )( )

(а* ,

2 Jv

(fc + 1)(fc + 2)'

= (fc + 1, А*—1), ■ ^А*, = (fc + 1, А*), ■ (fc + 1, А*_1А*), ■ (А

2

(fc + 1)(fc + 2)^

/ к + 2\ Л , к (^ + 1)\ Л к + 2\ /7 ^

= г'/г+1 "2 л=,•(*+12)-=

= (А*,к + 2)„ • (А*,2), • (А; + 1,2) „

Таким образом, нам надо проверить, что для любого к выполнено равенство (А^, 2)^ = + 1, 2)^.

V

Если к четно, то равенство выше выполнено потому, что Хк = к + 1.

Если к нечетно, то (Хк, 2) „ = (к++1, 2)^ = (к + 1, 2)^ • (2, 2)^. Теперь осталось воспользоваться тем, что (2, 2)^ = 1 для всех и € V. Это, с помощью леммы А.1.1, следует из того, что уравнение = 2х2 + 2у2 имеет нетривиальное решение.

□