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

• Боголюбский Лев Игоревич
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Боголюбский Лев Игоревич

при росте размерностей

Глава 3. Об измеримом хроматическом числе пространства

размерности п ^ 24 и пространства растущей размерности

3.1. Плотности измеримых множеств без расстояния

3.2. Дистанционные графы с вершинами в { —1,0,1}п и их применение в задаче об измеримом хроматическом числе

3.2.1. Конструкция Москвы

3.2.2. Конструкция Любимова

3.2.3. Численные результаты в «малых» размерностях

3.3. Случай растущей размерности: методы получения нижних оценок хроматических чисел

3.4. Случай растущей размерности: старая гипотеза и новые оценки 85 Заключение

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

n — множество натуральных чисел;

z — множество целых чисел;

2z — множество чётных целых чисел;

q — множество рациональных чисел;

r — множество действительных чисел;

[а] — (нижняя) целая часть числа а;

а! — факториал целого числа а;

(П) — число сочетаний из п по к;

\А\ — мощность конечного множества А;

x, у,... — n-мерные векторы с координатами х\,у\,..x = ..., хп),

у = (yi,... ,Уп), ...;

\ x\ — длина вектора x; ||x|| — норма вектора x;

(x, у) — евклидово скалярное произведение векторов x и у;

Ii — манхэттенская метрика;

¿2 — евклидова метрика;

V(G) — множество вершин графа G;

Е(G) — множество рёбер графа G;

a(G) — число независимости графа G;

x(G) — хроматическое число графа G;

Xm(G) — измеримое хроматическое число графа G;

f (d) — число Борсука пространства r;

ß(S) — мера Лебега множества S;

lim sup — верхний предел;

inf — нижняя грань;

sup — верхняя грань;

A u В — дизъюнктное объединение множеств А и В;

а(п) ~ Ь(п) — эквивалентность последовательностей а(п) и Ь(п)

при п ^ ж;

К[xi,..., хп] — кольцо многочленов от переменных xi,... ,х

с коэффициентами из поля К; dim V — размерность линейного пространства V; diam V — диаметр множества V.

п

Введение диссертации (часть автореферата) на тему «Задачи о раскрасках и разбиениях в комбинаторной геометрии»

Введение

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

В диссертации рассматривается ряд задач экстремальной комбинаторной геометрии, мотивированных такими классическими сюжетами, как проблема Нелсона-Эрдёша-Хадвигера и проблема Борсука.

Классическая проблема Нелсона—Эрдёша—Хадвигера, поставленная на рубеже 40-х и 50-х годов ХХ века, состоит в отыскании величины х(^п), называемой хроматическим числом пространства и равной наименьшему количеству цветов, в которые можно так покрасить все точки чтобы между точками одного цвета не было расстояния 1 (см. [1-3], [4], [5], [6], [7]):

х(кп) = шт{х : = VI и ... и Ух, v г v х, у е V- |х — у| = 1}.

Сейчас задача о хроматическом числе — одна из центральных в комбинаторной геометрии (см. [1], [2], [4-6], [8]).

Для величины х(^п) получено множество различных оценок как при конкретных значениях п (см. [9], [10-21]), так и в асимптотике (см. [8], [22], [23]). В частности, наилучшие известные асимптотические оценки имеют вид

(1.239 ... + о(1))п < х(^п) < (3 + о(1))п (0.0.1)

(нижняя оценка получена в [8], а верхняя — в [22]).

Естественным обобщением поставленной задачи служит аналогичная проблема для пространств с другими метриками, а также для случая нескольких расстояний, которым запрещено достигаться между точками одного цвета (см. [24-43]). Одной из наиболее исследованных является ситуация, когда метрика манхэттенская. Напомним, что манхэттенской называется метрика в задаваемая формулой

¿1 (х, у) = |ж1 — у11 + ... + 1хп — уп1

Обозначим соответствующее хроматическое число х(^п,11). В этом контексте

х(кп)= Х^л),

где 12 — обычная евклидова метрика.

Для метрики 11 известны асимптотические оценки (см. [38], [39], [44])

(1.366 ... + о(1))п < х(^п) < (4 + о(1))п.

Однако в «малых» размерностях никакие результаты ранее получены не были.

В то же время исключительно важную роль играет вариант задачи, в рамках которого рассматриваются только раскраски измеримыми по Лебегу цветами (множества VI,... ,УХ измеримы). В этом случае искомая величина обозначается Хт(^п) и называется измеримым хроматическим числом пространства. В диссертации рассматриваются как нижние оценки измеримых хроматических чисел пространств «малой» размерности, так и аналогичные оценки в случае растущей размерности.

Ситуация в «малых» размерностях следующая. Очевидно, что Хт(^1) = 2. Фалконер показал (см. [45]), что Хт(^2) ^ 5. Далее, Хт(^3) ^ 7 (см. [46]). Наконец, наилучшие известные автору нижние оценки величины Хт(^п) в размерностях п £ {4,..., 24} принадлежат авторам статьи [47]:

п 4 5 6 7 8 9 10 11 12 13 14

Хш ^ 10 15 21 37 52 69 90 116 164 254 334

п 15 16 17 18 19 20 21 22 23 24 25

Хт ^ 413 619 906 1178 1341 2132 3182 4062 4712 5424 —

Отметим, что неизвестно, верно ли, что х(^п) = Хт(^п). Однако нижние оценки этих величин сильно разнятся. Так, в [47] было показано (ср. с (0.0.1)), что

(1.268 ... + о(1))п ^ Хт(^п) ^ (3 + о(1))п.

Но, возможно, это лишь временное явление?

Помимо задач о раскрасках в диссертации рассматриваются задачи о разбиениях.

Проблема Борсука — вопрос в комбинаторной геометрии, посвящённый исследованию справедливости следующего утверждения. Дано евклидово пространство ^ и произвольное множество диаметра 1 в этом пространстве. Гипотеза такова: возможно разбить это множество на не более чем ^ +1

подмножество, каждое из которых будет иметь диаметр менее 1. Эквивалентно: любое ограниченное множество в ^ можно разбить на не более, чем й +1 подмножество меньшего диаметра.

Гипотеза, ошибочно называемая гипотезой Борсука (сам Борсук такого утверждения не делал — он лишь задал вопрос!), в действительности неверна. Это было доказано Каном и Калаи в 1993 году в [48]. Интерес, однако, представляет дальнейшее изучение величины / (д) — минимального числа подмножеств меньшего диаметра, на которые можно разбить произвольное множество в евклидовом пространстве ^, в зависимости от размерности в,. В этих терминах опровергнутое предположение имеет вид

/(с£) < А +1 УсI е n. (0.0.2)

Утверждение гипотезы (0.0.2) справедливо в некоторых частных случаях, например, при = 2 (это доказал сам Борсук в 1932 г. в [49]), при = 3 (Перкал в 1947 г. в [50]), для выпуклых тел с гладкой границей при всех А (доказано Хадвигером в [51] в 1946 г.), для всех центрально-симметричных тел при всех А (доказано Рислингом в [52] в 1971 г.), для всех тел вращения при всех А (доказано Декстером в [53] в 1995 г.), для множеств, инвариантных под действием группы симметрии ¿-симплекса (доказано Роджерсом в [54] в 1971 г.).

Однако же в 1993 году Кан и Калаи показали [48], что /(1325) > 1326, что опровергло (0.0.2). Далее события развивались следующим образом. В 1994 году Алон (под псевдонимом Нилли) нашёл [55] контрпример при А = 946. В 1997 году Райгородский уточнил [56] нижнюю грань размерности до 561. Затем в 2000 году Вайссбах понизил её [57] до 560. Далее, в 2002 году, последовали результаты Хинрикса [58] для А = 323 и Пихурко [59] для А = 321; в 2003 году Хинрикс и Рихтер опубликовали доказательство [60] следующего уточнениия: /(298) > 298+ 11. В 2014 г. Бондаренко опроверг [61] гипотезу для в, ^ 65, и, наконец, в том же году Йенрихом была получена [62] наилучшая известная на текущий момент нижняя грань, А = 64.

Более подробно с историей проблемы можно ознакомиться в [2], [4], [7], [63], [64].

Число /(д) изучалось не только в «малых» размерностях, но и в асимптотике (й, ^ ж). Известны как оценки сверху — например, в [65] показано, что

/(¿) ^ (1.224... + о(1))*

так и оценки снизу:

/(^ ^ (1.203... + о(1))^ (Кан и Калаи, 1993, [48]),

/(г!) ^ (1.2255 ... + о(1))^3 (Райгородский, 1999, [66]). (0.0.3)

Интересен следующий факт. Наилучшая известная на текущий момент нижняя оценка (0.0.3) числа Борсука /(г!) в асимптотике была получена с помощью исследования серии дистанционных графов (см. раздел 1.1) с вершинами в { —1, 0, 1}п с С другой стороны, при некоторых «малых» (1 (й, = 561, см. [56]) аналогичный подход даёт лучшие результаты за счёт дистанционных графов с вершинами в { — 1, 1}п (что эквивалентно использованию {0,1}-дистанционных графов). Кроме того, авторы последних работ, посвящённых «малым» размерностям, оперируют вовсе не дистанционными графами: в статьях [58] и [60] для получения результатов использовались решётки, а в статьях [61] и [62] — сильно регулярные графы.

В какой момент с ростом (1 устанавливается «доминирование» { — 1, 0,1}-дистанционных графов над { — 1,1}-дистанционными графами? Как влияет добавление третьего возможного типа координат векторов — вершин графов — на оценки при «малых» (1 > 561, то есть какие наилучшие оценки можно получить с использованием { — 1, 0, 1}-графов, { — 1,1}-графов, когда предпочтительны какие из них? В диссертации мы исследуем эти вопросы, используя методы, сходные с методами, применяемыми нами к смежной проблеме комбинаторной геометрии — задаче Нелсона—Эрдёша—Хадвигера о хроматическом числе пространства.

Цель работы и задачи исследования Целью настоящей работы является получение нижних оценок измеримых хроматических чисел в двух случаях: для пространств «малых» размерностей и для случая растущей размерности пространства; получение нижних оценок хроматических чисел пространств с евклидовой и манхэттенской метриками; получение нижних оценок чисел Борсука евклидовых пространств; получение верхних оценок чисел независимости некоторых конечных дистанционных графов.

Научная новизна Полученные в диссертации результаты являются новыми.

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

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

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

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

1. Сформулирован и доказан в общем виде ряд теорем, касающихся применения линейно-алгебраического метода к оцениванию сверху чисел независимости конечных дистанционных графов в пространствах с метриками 1\ и ¿2.

2. Для манхэттенской метрики получены нижние оценки хроматических чисел пространств «малой» размерности. Для евклидовой метрики получены новые оценки: х(^22Л) ^ 139, х(^23Л) ^ 171, х(^24Л) ^ 209; устранена неточность в известной оценке при п = 16; а также численно определён момент начала доминирования оценок, связанных с {-1, 0,1}-векторами.

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

4. Получены оценки чисел Борсука ряда пространств следующие из доказанных оценок чисел независимости дистанционных графов специального вида. Численно определён момент, начиная с которого устанавливается «доминирование» { — 1, 0, 1}-графов над {-1,1}-графами.

5. Указан способ уточнения нижних оценок измеримых хроматических чисел пространств , п = 12,..., 24, путём предъявления верхних оценок чисел независимости серии конечных дистанционных графов.

Степень достоверности и апробация результатов

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

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

• научный семинар «Вероятностные и алгебраические методы в комбинаторике» на кафедре математической статистики и случайных процессов механико-математического факультета МГУ под руководством доктора физико-математических наук А. М. Райгородского (2015 г.);

• научный семинар «Современные проблемы теории чисел» в Математическом институте им. В. А. Стеклова Российской академии наук под руководством доктора физико-математических наук, академика РАН С. В. Ко-нягина и доктора физико-математических наук, члена-корреспондента РАН И. Д. Шкредова (2015 г.);

• спецсеминар «Экстремальная комбинаторика и случайные структуры» на кафедре теории вероятностей механико-математического факультета МГУ под руководством доктора физико-математических наук Д. А. Шабанова (2015 г.);

• кафедральный семинар кафедры дискретной математики МФТИ (2015— 2019 гг., неоднократно);

• аспирантский коллоквиум кафедры теории вероятностей механико-математического факультета МГУ (2018 г.).

Публикации

Результаты диссертации опубликованы в работах [67], [68], [69], [70], указанных в списке литературы. Все работы представлены в журналах из перечней ВАК, RSCI и РИНЦ, две из них — в журналах из перечня Scopus. Все результаты, приведённые в диссертации, были получены её автором самостоятельно, включая результаты, опубликованные в совместных работах. А. М. Райго-родский предложил сюжеты для разработки, оказал автору помощь в составлении обзоров актуальных смежных результатов и в написании введения, а также вносил правки в некоторые доказательства.

Благодарности

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

Краткое содержание работы

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

В первой главе рассмотрен класс оценок, связанных с проблемой Нел-сона—Эрдёша—Хадвигера. Для двух типов пространств, евклидовых и с метрикой 11, изучены некоторые серии дистанционных графов в «малых» размерностях. Посредством использования линейно-алгебраического метода и некоторых комбинаторных наблюдений доказаны оценки чисел независимости таких графов; как следствие, получены некоторые нижние оценки хроматических чисел упомянутых пространств, а также для каждого случая указана серия графов, позволяющая прийти к наиболее сильным результатам.

Структура первой главы следующая. В разделе 1.2 описаны известные результаты для «малых» размерностей, сформулированы некоторые новые утверждения. В разделе 1.3 в общих чертах описан метод доказательства. Далее, в разделе 1.4, сформулирован и доказан ряд общих теорем. В разделе 1.5 даны нетривиальные уточнения этих теорем в широком классе случаев. В разделе 1.6 получены численные следствия для нижних оценок хроматических чисел пространств. В разделе 1.7 приведены некоторые замечания, связанные с доказанными результатами.

Во второй главе изучены различные оценки, связанные с проблемой Бор-сука. Рассмотрены некоторые серии дистанционных графов и индуцированные ими двойственные конфигурации в пространствах «малых» размерностей и при росте размерности. К графам применена модификация линейно-алгебраического метода, в результате получены нижние оценки /(г!) — минимального числа частей множеств «меньшего диаметра» из проблемы Борсука в ^.

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

двойственного перехода и обобщённого двойственного перехода и описаны свойства этих отображений. В разделе 2.4 сформулированы и доказаны нужные для получения оценок утверждения, специфичные для конкретных рассматриваемых серий дистанционных графов. Наконец, в разделах 2.5 и 2.6 окончательно сформулированы оценки для каждой из серий, описана схема вычислений и приведены численные результаты.

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

Далее, в разделе 3.4, сначала упомянут результат работы [71] о том, что в рамках метода, дающего оценку обычного хроматического числа, есть шанс получить неравенства

Хт(МГ) ^ х(М") ^ (1.30 ... + о(1))п,

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

^ (1.28 ... + о(1))п.

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

Глава 1.

О нижних оценках хроматических чисел пространств «малой» размерности с метриками 1\ и 12

1.1. Главные определения

Определим ключевые для всех глав диссертации понятия.

Говоря о графах, мы рассматриваем исключительно неориентированные графы без петель и кратных рёбер, то есть такие пары С = (V, Е), где V — произвольное (чаще — конечное и непустое) множество, а Е — подмножество декартового произведения V х V, не содержащее элементов вида (у, у), но всегда содержащее элемент (и, у) одновременно с любым (у, и), где и, у £ V.

Числом независимости графа С = (V, Е) называется а(С) — наибольшая возможная мощность такого подмножества вершин и С V, что никакие две из них не соединены ребром, то есть (и х и) ПЕ = 0. Сами подмножества и с таким свойством называются при этом независимыми.

Хроматическим числом графа С = (V, Е) называется х(^) — наименьшее возможное количество цветов, в которые можно раскрасить вершины V таким образом, чтобы никакое ребро из Е не соединяло две вершины одного цвета.

Для хроматического числа любого конечного графа С = (V, Е) имеем неравенство

Х(С) > ^. а(и)

Аналогично определяется величина х(^п, р), называемая хроматическим числом пространства и равная наименьшему количеству цветов, в которые можно так покрасить все точки чтобы между точками одного цвета не

было р-расстояния 1.

Дистанционным графом в пространстве rn, наделённом некоторой метрикой, мы называем такой граф G = (V., Е), что его вершины из V могут быть одновременно отождествлены с некоторыми точками rn таким образом, чтобы множество рёбер Е совпало со множеством пар вершин, отстоящих друг от друга на некоторое запрещённое расстояние рсгц > 0:

У С rn, Е = {{x, y} : |x - y| = pcrU}.

Перейдём теперь к обсуждению известных результатов.

1.2. Известные оценки в «малых» размерностях и формулировки некоторых новых результатов

Что касается хроматических чисел x(rn, li) в «малых» размерностях, нам неизвестны работы, посвящённые оценке этих величин. Мы впервые предлагаем, например, следующие результаты:

x(r5,li) ^ 8,x(r6,li) ^ 14,x(r7,li) ^ 20, x(r8,li) ^ 28,x(r9,li) ^ 38,...,

подлежащие, видимо, дальнейшему улучшению.

В случае же метрики ¿2 ситуация в «малых» размерностях, напротив, хорошо изучена. Особенно подробно были исследованы размерности п ^ 12. В таблицу 1.1 сведены наилучшие известные автору результаты в этих размерностях с указанием источника для каждого результата.

Таблица 1.1. Наилучшие известные автору нижние оценки %(Rra),n = 2... i2

п х№пЛ) ^ источник

2 4 [1,3]

3 6 [18]

4 9 [14]

5 9 [10]

6 12 [13]

7 16 [13]

8 19 [15]

9 21 [16]

Таблица 1.1. Наилучшие известные автору нижние оценки %(Мга),п = 2... 12

п х(мпЛ) ^ источник

10 30 [19]

11 35 [19]

12 37 [19]

Отметим сразу, что полученные нашим методом результаты в размерностях п ^ 12 слабее представленных выше лучших известных. Так, например, в числе лучших наших результатов оценки х(мп) ^ 19, х(м12) ^ 22.

Однако и при п > 12 хроматическое число также исследовалось. Здесь сведения несколько более разрозненны. Некоторые результаты были резюмированы в виде таблицы в работе [6]. В таблице 1.2 мы сравниваем эти результаты для п = 13,..., 24 с аналогичными нашими.

Таблица 1.2. Сравнение наилучших известных нижних оценок х(Кга) с нашими оценками, п = 13... 24

п оценка по [6]: х(^п,12) ^ наша оценка: х(^п,12) ^

13 31 26

14 35 31

15 37 37

16 67 46

17 56 56

18 68 68

19 82 82

20 97 97

21 114 114

22 133 139

23 154 171

24 178 209

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

х(М22л) ^ 139,х(Ж23л) ^ 171,х(М24,12) ^ 209.

15

Также была устранена неточность при п = 16 (очевидно, х(^17) ^ Х(^16)).

Результаты из [6] были получены с помощью так называемых {0, 1}-век-торов (см. раздел 1.6). В нашей работе мы также провели исследование с {0, 1}-векторами; более того, мы обобщили его на { — 1, 0, 1}-векторы и сравнили полученные результаты в «малых» размерностях. Последнее не делалось ранее никогда.

Важно, что в диссертации был найден момент (см. таблицу 1.4), начиная с которого лучшими в евклидовом случае становятся оценки, связанные с { —1, 0, 1}-векторами. Это абсолютно ожидаемо, так как в асимптотике именно эти векторы дают лучший результат (см. [8]); однако ранее момент, когда при росте размерности пространства наступает доминирование { —1, 0, 1}-векторов, не изучался.

Многие из рассмотренных в настоящей диссертации величин ) при

п > 24, по-видимому, оцениваются впервые. Это стало возможно благодаря тому, что предложенный метод легко масштабируется на различные размерности.

Результаты во многих «малых» размерностях далее в диссертации сведены в подразделах 1.6.2 и 1.6.4 в таблицы, соответствующие метрикам £1 и 12.

Результаты этой главы были сформулированы и доказаны в работе [67].

1.3. Общая идея получения нижних оценок хроматических чисел метрических пространств

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

Во-первых, рассмотрим некоторый граф С = (V, Е). Легко видеть, что при любой раскраске, исключающей рёбра между одноцветными вершинами графа, множества одноцветных вершин являются независимыми множествами в графе С. Минимальное количество таких «цветовых кластеров» в фиксированной раскраске и максимальный размер кластера связаны тогда соотношением, которое во введённых терминах записывается так:

х(С) > -И.. (1.3.1)

а(и)

Во-вторых, пусть теперь С вложен в пространство наделённое метрикой, то есть, пусть С — дистанционный граф: его вершины из V отождествлены с некоторыми точками пространства, а множество его рёбер Е при этом

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

X(Rn) ^ X(G). (1.3.2)

Объединяя (1.3.1) с (1.3.2), имеем

x(rn) ^ , (1.3.3)

a(G)

где подразумевается x(rn) = x(rn,P) для метрики пространства р, а вложенный в пространство граф мы вольны выбирать.

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

Итак, мы только что пояснили, как задача нижней оценки хроматического числа пространства сводится к задаче верхней оценки чисел независимости конечных графов. В диссертации к этой задаче применяется классический линейно-алгебраический метод в комбинаторике (см., например, [1, 72]), к подробному рассказу о котором мы теперь и переходим.

1.4. Линейно-алгебраический метод 1.4.1. Случай манхэттенской метрики 1\

Теорема 1.4.1. Пусть р — простое число, п £ n. Рассмотрим произвольную совокупность векторов £ С { — 1, 0,1}п такую, что

Vx, y £ £ : li(x, y) £ 2z,

и подсовокупность T С £ такую, что для некоторого а £ n и любых x и y из T справедлива эквивалентность

l1(x, y)/2 = 0 mod р° ^^ x = y,

причём

п ^ ра - 1.

Тогда

■ра-1

И <512'

,t0, W

Более того, в случае, если И С £ С {0,1}п,

та=0 4 х

Доказательство. Для фиксированного вектора x £ £ определим следующую функцию векторов y £ £:

&(у) = "7 П (* - li(x, у)/2), р i=i

здесь Р £ z^o - максимальная степень вхождения р в (ра - 1)! - то есть, Р таково, что (ра - 1)!- натуральное число, не делящееся на р.

Покажем, что для любых x, y £ £ выполнено ^x(y) £ z и что, более того, справедлива следующая

Лемма 1.4.2.

£x(y) = 0 mod р ^^ l1(x, y)/2 ^ 0 mod р°.

Доказательство. Пусть l1(x, y)/2 = 0 mod ра. Тогда ^x(y) ^ 0 mod р по построению.

Пусть, напротив, l1(x, y)/2 ^ 0 mod ра. Убедимся в том, что в этом случае £x(y) = 0 mod р. Для этого достаточно показать, что

ра-1

/+1 I П (г - li(x, у)/2).

i=i

В случае, если l1(x, y)/2 £ {1,... ,ра - 1}, утверждение тривиально — произведение попросту обращается в ноль. Будем считать, что li(x, y)/2 > ра. Сравним максимальные степени Р и /3 вхождения р в числа (ра - 1)! и

- l1 (x, y)/2) соответственно. Пусть Dq(S) — количество чисел, кратных Q £ z, среди элементов множества целых чисел S. Заметим, что если L,R, А £ z, L < R, L - 1 = 0 mod Q, то справедливо

DQ([L + A,R + А]) ^ DQ([L,R]),

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

ж

р = Е^ (t1 - y)/2; ра -1 - y)/2]) ^

7=1 а

> ^ Djn ([1 - li(x, y)/2; ра - 1 - li(x, y)/2]) =

7=1 a-1

= ^ Dp-у ([1 - li(x, y)/2; pa - 1 - li(x, y)/2]) + 1 ^

7=1

a-1

^ £ Dp, ([1; pa - 1]) + 1 = P + 1.

7=1

В рассуждении выше мы учли тот факт, что при l1(x, y)/2 ^ 0 mod ра в отрезке [1 - l1(x, y)/2; р° - 1 - l1(x, y)/2] обязательно содержится целое число, кратное р .

Мы получили, что /3 > Р, и это влечёт требуемое соотношение ^x(y) = 0 mod р. Лемма доказана.

□

Заметим, что при фиксированном x = (х1,..., хп) £ Е функция I1 (x, y) = 1x1 - y1l + ... + lxn - ynl

может быть рассмотрена как чётнозначная функция п целых аргументов yj £ {-1, 0, 1} - координат вектора y £ Е. При этом каждое из слагаемых вида Iхj - УзI, 1 ^ j ^ п, может быть заменено на многочлен не более чем второй степени следующим образом:

i1 - Уз, хз = 1, Ixj - yjI = ly2, х, =0, (1.4.3)

U + Уз, хз = -1,

при yj £ {-1, 0,1}.

Заменяя таким образом li(x, y)/2 на сумму многочленов qx. от переменных yj в определении функции ^x(y), мы получим следующий многочлен из

Q[yi,.. .,Уп ]:

1 ра-1

Vx(У) = -р П (i - [qxi (У1) + ... + Vxn (Уп)]) . р i=i

Рассмотрев произвольный аргумент y £ £, заметим, что по построению ^x(y) = Px(y); раскрыв скобки в выражении для многочлена, мы получим, что "Px(y) может быть представлен как линейная комбинация мономов, в каждый из которых входит не более ра - 1 различных переменных yj.

Далее воспользуемся тем фактом, что у3 = yj для y £ £. Заменяя в "Px(y) каждую натуральную степень вхождения переменной S на 2 - (S mod 2), приходим к новым многочленам 7->x(y) :

^(У) = Л £ U...JU $ , (1.4.4)

где 7ji...jm £ z. Каждая переменная yj входит в одночлены построенного многочлена в степенях, не больших 2, а всего в каждый из одночленов входит не более ра-1 различных переменных. Кроме того, по построению, многочлен Px и функция совпадают по значению на векторах y £ £. Тем самым, все утверждения, в которых фигурируют значения переносятся естественным образом на модифицированные многочлены "Px.

Лемма 1.4.5. Пусть некоторые различные векторы x1,...,xs £ £ таковы, что yi,j,i = j : l1(x^, xj)/2 ^ 0 mod pa. Тогда соответствующие этим векторам многочлены Vxi,..., "Pxs линейно независимы над полем q.

Доказательство. Предположим противное: пусть для некоторых с[,... ,с'а £ q, не равных нулю одновременно,

c'i^xi + ... + c'sVxs = 0.

Тогда для всех y £ £ справедливо равенство

c'iPxi (y) + ... + ¿¿Px. (у) = 0.

Аналогичное равенство справедливо и для некоторых ci,... ,cs £ z таких, что хотя бы одно из этих чисел не делится на р:

ciPx, (y) + ... + csVxs (y) =0.

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

Список литературы диссертационного исследования кандидат наук Боголюбский Лев Игоревич, 2020 год

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

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

2. Raigorodskii A. Thirty Essays on Geometric Graph Theory // / ed. by J. Pach. Springer, 2013. Chap. Coloring Distance Graphs and Graphs of Diameters.

3. Soifer A. The Mathematical Coloring Book. Springer, 2009.

4. Raigorodskii A. Cliques and cycles in distance graphs and graphs of diameters // Contemporary Mathematics. 2014. Vol. 625. P. 93-109.

5. Brass P., Moser W., Pach J. Research problems in discrete geometry. Springer, 2005.

6. Szekely L. Erdos on unit distances and the Szemeredi-Trotter theorems //J. Bolyai Math. Soc. 2002. Vol. 11. P. 649-666.

7. Raigorodskii A. Combinatorial geometry and coding theory // Fundamenta Informatica. 2016. Vol. 145, no. 3. P. 359-369.

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

9. Любимов В., Райгородский А. О нижних оценках чисел независимости некоторых графов расстояний с вершинами в {-1, 0,1}га // Доклады РАН. 2009. Т. 427, № 4. С. 458—460.

10. Cantwell K. Finite Euclidean Ramsey theory //J. Combin. Theory A. 1996. Vol. 73, no. 2. P. 273-285.

11. Chilakamarri K. The unit-distance graph problem: a brief survey and some new results // Bull. Inst. Comb. Appl. 1993. Vol. 8, no. 39. P. C60.

12. Cibulka J. On the chromatic number of real and rational spaces // Geombinatorics.

2008. Vol. 18, no. 2. P. 53-65.

13. Exoo G., Ismailescu D. On the Chromatic Number of Rn for Small Values of n. 2018. URL: http://arxiv.org/pdf/1408.2002v1.pdf.

14. Exoo G., Ismailescu D., Lim M. On the Chromatic Number of R4 // Discrete Computational Geometry. 2014. Vol. 52, no. 2. P. 416-423.

15. Kahle M., Taha B. New lower bounds on x(Rd), d = 8,..., 12 // Geombinatorics. 2015. Vol. 24, no. 3. P. 109-116.

16. Kupavskiy A., Raigorodskii A. On the chromatic number of R9 // J. of Math. Sci.

2009. Vol. 163, no. 6. P. 720-731.

17. Nagy Z. A certain constructive estimate of the Ramsey number // Matematikai Lapok. 1972. Vol. 23, no. 301-302. P. 26.

18. Nechushtan O. On the space chromatic number // Discrete mathematics. 2002. Vol. 256, no. 1-2. P. 499-507.

19. Черкашин Д., Райгородский А. О хроматических числах пространств малой размерности // Доклады РАН. 2017. Т. 472, № 1. С. 11—12.

20. О числах независимости графов расстояний с вершинами в {-1, 0,1}га / А. Гутер-ман, В. Любимов, А. Райгородский, А. Усачев // Матем. заметки. 2009. Т. 86, № 5. С. 794—796.

21. Raigorodskii A., Kupavskii A. On the chromatic numbers of small-dimensional Euclidean spaces // Electronic Notes in Discrete Mathematics. 2009. Vol. 34. P. 435439.

22. Larm,an D., Rogers C. The realization of distances within sets in Euclidean space // Mathematika. 1972. Vol. 19. P. 1-24.

23. Frankl P., Wilson R. Intersection theorems with geometric consequences // Combina-torica. 1981. Vol. 1, no. 4. P. 357-368.

24. Benda M., Perles M. Colorings of metric spaces // Geombinatorics. 2000. Vol. 9, no. 3. P. 113-126.

25. Kang J.-H., Furedi Z. Distance graphs on Zn with ^-norm // Theoretical Comp. Sci. 2004. Vol. 319, no. 1-3. P. 357-366.

26. Katznelson Y. Chromatic numbers of Cayley graphs on Z and recurrence // Combina-torica. 2001. Vol. 21, no. 2. P. 211-219.

27. Купавский А. О раскрасках сфер, вложенных в Мга // Матем. сб. 2011. Т. 202, № 6. С. 83—110.

28. Купавский А. О поднятии оценки хроматического числа Rn в большую размерность // Доклады Академии наук. 2009. Т. 429, № 3. С. 305—308.

29. Райгородский А. О хроматическом числе пространства с двумя запрещенными расстояниями // Доклады РАН. 2006. Т. 408, № 5. С. 601—604.

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

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

32. Райгородский А., Шитова И. О хроматическом числе евклидова пространства и о проблеме Борсука // Математические заметки. 2008. Т. 83, № 4. С. 636—639.

33. Оценка хроматических чисел евклидова пространства методами выпуклой минимизации / Е. Горская, И. Митричева, В. Протасов, А. Райгородский // Математический сборник. 2009. Т. 200, № 6. С. 3—22.

34. Райгородский А. О хроматических числах сфер в евклидовом пространстве // Доклады РАН. 2010. Т. 432, № 2. С. 174—177.

35. Raigorodskii A. On the chromatic numbers of spheres in Rra // Combinatorica. 2012. Vol. 32, no. 1. P. 111-123.

36. Костина О., Райгородский А. О нижних оценках хроматического числа сферы // Доклады РАН. 2015. Т. 463, № 6. С. 639—641.

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

38. Kupavskii A. On the chromatic number of Rra with an arbitrary norm // Discrete Math. 2011. Vol. 311, no. 6. P. 437-440.

39. Kupavskii A. The chromatic number of Rra with a set of forbidden distances // Doklady Math. 2010. Vol. 82, no. 3. P. 963-966.

40. Пономаренко Е., Райгородский А. Новая нижняя оценка хроматического числа рационального пространства с одним и двумя запрещенными расстояниями // Ма-тем. заметки. 2015. Т. 97, № 2. С. 255—261.

41. Канель-Белов А., Воронов В., Черкашин Д. О хроматическом числе плоскости // Алгебра и анализ. 2017. Т. 29, № 5. С. 68—89.

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

43. Berdnikov A. Chromatic number with several forbidden distances in the space with the £q-metric // Journal of Mathematical Sciences. 2017. Vol. 227, no. 4. P. 395-401.

44. Райгородский А. О хроматическом числе пространства с Iq-нормой // Успехи математических наук. 2004. Т. 59, № 5. С. 161—162.

45. Falconer K. The realization of distances in measurable subsets covering Rra // J. Com-bin. Theory A. 1981. Vol. 31. P. 187-189.

46. Oliveira Filho F. de, Vallentin F. Fourier analysis, linear programming, and densities of distance avoiding sets in Rra // J. Eur. Math. Soc. 2010. Vol. 12. P. 1417-1428.

47. Bachoc C., Passuello A., Thiery A. The Density of Sets Avoiding Distance 1 in Euclidean Space // Discrete Computational Geometry. 2015. Vol. 53, no. 4. P. 783808.

48. Kahn J., Kalai G. A counterexample to Borsuk's conjecture // Bulletin of the American Mathematical Society. 1993. Vol. 29, no. 1. P. 60-62.

49. Borsuk K. Drei Sätze über die n-dimensionale euklidische Sphäre // Fundamenta Ma-thematicae. 1933. Jg. 20, Nr. 1. S. 177-190.

50. Perkal J. Sur la subdivision des ensembles en parties de diamètre inférieur // Colloquium Mathematicum. 1947. T. 1, n0 1. P. 45.

51. Hadwiger H. Überdeckung einer Menge durch Mengen kleineren Durchmessers // Com-mentarii Mathematici Helvetici. 1945. Jg. 18, Nr. 1. S. 73-75.

52. Riesling A. Borsuk's problem in three-dimensional spaces of constant curvature // Ukr. Geom. Sbornik. 1971. Vol. 11. P. 78-83.

53. Dekster B. The Borsuk conjecture holds for bodies of revolution // Journal of Geometry. 1995. Vol. 52, no. 1-2. P. 64-73.

54. Rogers C. Symmetrical sets of constant width and their partitions // Mathematika. 1971. Vol. 18, no. 1. P. 105-111.

55. Nilli A. On Borsuk's problem // Contemporary Mathematics. 1994. Vol. 178. P. 209.

56. Райгородский А. О размерности в проблеме Борсука // УМН. 1997. Т. 52, 6(318). С. 181—182.

57. Weifibach B. Sets with large Borsuk number // Beitrâge zur Algebra und Geometrie. 2000. Jg. 41, Nr. 2. S. 417-423.

58. Hinrichs A. Spherical codes and Borsuk's conjecture // Discrete Math. 2002. Vol. 243, no. 1-3. P. 253-256.

59. Pikhurko O. Borsuk's conjecture fails in dimensions 321 and 322. 2002. URL: https: //arxiv.org/abs/math/0202112.

60. Hinrichs A., Richter C. New sets with large Borsuk numbers // Discrete Mathematics. 2003. Vol. 270, no. 1-3. P. 137-147.

61. Bondarenko A. On Borsuk's Conjecture for Two-Distance Sets // Discrete Computational Geometry. 2014. Vol. 51, no. 3. P. 509-515.

62. Jenrich T., Brouwer A. A 64-Dimensional Counterexample to Borsuk's Conjecture // The Electronic Journal of Combinatorics. 2014. Vol. 21, no. 4. #P4.29.

63. Райгородский А. Вокруг гипотезы Борсука // Современная математика. Фундаментальные направления. 2007. Т. 23. С. 147—164.

64. Raigorodskii A. Three lectures on the Borsuk partition problem // London Mathematical Society Lecture Note Series. 2008. Vol. 347. P. 202-248.

65. Schramm O. Illuminating sets of constant width // Mathematika. 1998. Vol. 35, no. 2. P. 180-189.

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

67. Боголюбский Л., Райгородский А. Замечание о нижних оценках хроматических чисел пространств малой размерности с метриками 1\ и // Математические заметки. 2019. Т. 105, № 2. С. 187—213.

68. Боголюбский Л., Райгородский А. Об оценках в проблеме Борсука // Труды МФТИ. 2019. Т. 11, № 3. С. 20—49.

69. Боголюбский Л., Райгородский А. Об измеримом хроматическом числе пространства размерности п ^ 24 // Доклады РАН. 2015. Т. 7, № 3. С. 5—10.

70. Боголюбский Л., Райгородский А. Об измеримом хроматическом числе пространства растущей размерности // Труды МФТИ. 2015. Т. 27, № 3.

71. Райгородский А., Харламова А. О совокупностях (-1, 0,1)-векторов с запретами на величины попарных скалярных произведений // Труды по векторному и тензорному анализу. 2013. Т. 29. С. 130—146.

72. Babai L., Frankl P. Linear algebra methods in combinatorics, Preliminary version 2. Department of Computer Science, The University of Chicago, 1992.

73. Bogolubsky L. 2017. URL: https://github.com/LevBogolubsky/chrom_lower_ linear_algebra.

74. Райгородский А. Гипотеза Кнезера и топологические методы в комбинаторике. М.: МЦНМО, 2011.

75. Райгородский А. Линейно-алгебраический метод в комбинаторике. М.: МЦНМО, 2015.

76. Гервер М. О разбиении множеств на части меньшего диаметра: теоремы и контрпримеры // Математическое просвещение. 1999. Т. 3. С. 168—183.

77. Bogolubsky L. 2019. URL: https://github.com/LevBogolubsky/Borsuk_lower_ linear_algebra.

78. Croft H. Incident incidents. Eureka (Cambridge), 1967. P. 22-26.

79. Купавский А., Райгородский А., Титова М. О плотнейших множествах без расстояния единица в пространствах малых размерностей // Труды МФТИ. 2012. Т. 4, № 1. С. 111—121.

80. О числах независимости графов расстояний с вершинами в {-1, 0,1}"": оценки, гипотезы и приложения к задачам Борсука и Нелсона-Эрдёша-Хадвигера / А. Гутерман, В. Любимов, А. Райгородский, А. Усачев // Итоги науки и техники, Сер. "Современная математика". 2009. Т. 65. С. 82—100.

81. Москва В., Райгородский А. Новые нижние оценки чисел независимости дистанционных графов с вершинами в {-1, 0,1}га // Матем. заметки. 2011. Т. 89, № 2. С. 319—320.

82. Andersen M., Dahl J., Vandenberghe L. CVXOPT: A Python package for convex optimization. 2013. URL: https://cvxopt.org/.

83. Bogolubsky L. 2020. URL: https : / / github . com / LevBogolubsky / chrom _ measurable_lower_optimization_small.

84. Пономаренко Е., Райгородский А. Новые верхние оценки чисел независимости графов с вершинами в {-1, 0,1}"" и их приложения в задачах о хроматических числах дистанционных графов // Матем. заметки. 2014. Т. 96, № 1. С. 138—147.

85. Bogolubsky L. 2020. URL: https : / / github . com / LevBogolubsky / chrom _ measurable_lower_optimization_growing.