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

• Голованов Александр Игоревич
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Голованов Александр Игоревич

Введение

Глава 1. Равноудалённые вправо последовательности в £ж и £\

1.1 Доказательство верхней оценки в теореме

1.2 Доказательство нижней оценки в теореме

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

1.4 Дальнейшие вопросы

Глава 2. Обобщённое контактное число плоскости для п слоёв

2.1 Асимптотически наибольшая упаковка

2.1.1 Верхняя оценка

2.1.2 Мельницы

2.1.3 Построение желаемой упаковки

Глава 3. Обобщённое контактное число плоскости для трёх слоёв

3.1 Доказательство теоремы 7 через ключевые леммы

3.1.1 Определения

3.1.2 Набросок доказательства теоремы

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

3.3 Построение кривой из леммы

3.3.1 Доказательство утверждения

3.4 Вывод леммы 5 из локального неравенства

3.4.1 Угловая нотация

3.4.2 Скачки направлений

3.5 Доказательство утверждения

3.5.1 Случай к =

3.5.2 Случай к = 1, общие наблюдения

3.5.3 Случай к = 1, завершение доказательства

3.6 Обсуждение

Заключение

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

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

Введение

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

Считается, что современная комбинаторная геометрия окончательно сформировалась в первой половине XX в. Во-первых [1], работы Ласло Фей-еш Тота и Клода Амброза Роджерса предложили новые подходы к уже известным задачам Ньютона, Гаусса, Минковского, Гильберта и Туэ, таким образом заложив фундамент современной теории упаковок и покрытий. Во-вторых, круг венгерских математиков поднял ряд новых комбинаторно-геометрических вопросов. Один из первых таких вопросов сейчас известен как теорема Эрдёша-Секереша [2], которая утверждает, что для любого к > 4 найдётся такое число N (к), что среди любых N (к) точек общего положения на плоскости можно выбрать к точек, являющихся вершинами выпуклого многоугольника.

Что касается задач о расстояниях между точками, они часто тесно связаны с задачами об их расположении. В 1946 году Эрдёш опубликовал работу [3], в которой, в частности, поднял следующие вопросы:

— Если расположить п точек на плоскости, какое наибольшее число пар из них может находиться на расстоянии 1?

— Чему равно наименьшее возможное число различных расстояний между этими точками?

Эта работа Эрдёша задала вектор развития геометрии расстояний на годы вперёд. В той же статье Эрдёш доказал, что если через /(п) обозначено наибольшее возможное число пар точек на расстоянии 1, то /(п) = 0(п3/2). Это следует из того, что дистанционный граф (то есть граф на п вершинах, где пара вершин соединяется ребром тогда и только тогда, когда соответствующая пара точек находится на расстоянии 1 друг от друга) такой конфигурации не содержит подграфа К32. Этот пример, в частности, показывает тесную связь

комбинаторной геометрии с теорией графов. Лучшей оценкой на данный момент является f (п) = 0(п4/3), улучшающая предыдущую оценку [4; 5].

Однако задачу о наибольшем возможном числе точек с попарно единичным расстоянием можно обобщить и иным способом. Например, расстояние между точками можно задать по-разному. Например, если х £ Rn — вектор в n-мерном пространстве, а р £ [1, ж) — вещественное число, то р-нормой вектора х называют

IMIp :=(ЫР + ... + WP)1/p .

Можно заметить, что при р ^ ж данное выражение имеет предел, равный

II^11ос max

|. Пространство Rn, снабжённое такой нормой, обозначают через R£. '

Для всякого метрического пространства назовём его равносторонней размерностью (equilateral dimension) наибольшее количество точек, находящихся на попарно единичном расстоянии. Известно [6], что равносторонняя размерность пространства R2 есть п + 1, а равносторонняя размерность R^ равна 2П. Более того, в этой же работе показано, что равносторонняя размерность всякого n-мерного нормированного пространства не превосходит 2П, причём равенство достигается тогда и только тогда, когда единичный шар является параллелепипедом. Однако про Ш™ известно намного меньше, когда р = 2, ж. Например, для Манхеттенской метрики 11 Алон и Пудлак [7] показали, что равносторонняя размерность пространства R не превосходит сп log п для некоторой положительной константы с, в то время, как наилучшая известная нижняя оценка 2п получается из рассмотрения вершин стандартного кроссполитопа (то есть точек, у которых все координаты нулевые, кроме одной, равной ±1). Существует гипотеза [6] о том, что равносторонняя размерность всякого n-мерного нормированного пространства не меньше п + 1. Каснер [8] выдвинул гипотезу о том, что равносторонняя размерность пространства R™ равна 2п. Эта гипотеза была подтверждена лишь для п = 3 в работе [9] и для п = 4 в работе [10]. Лучшие известные оценки для других значений р на данный момент можно найти в работах Алона и Пудлака [7], Смита [11], Сванепула [12] и Сванепула и Вильи [13].

Что же касается второй из приведённых задач Эрдёша из работы [3], оценка на число расстояний, порождаемых п точками на плоскости, менялась в работах Мозера [14], Бека [15], Чанга [16; 17] и Шекели [18] до ft(n0'8641). В 2015 году

Гут и Кац показали [19], что это число расстояний всегда асимптотически не меньше, чем п/ log п, таким образом почти устранив промежуток между нижней и верхней оценками, поскольку пример на 0(п/\/log п) различных расстояний представляет собой квадратная решётка, которую предъявил ещё Эрдёш в [3]. Несмотря на то, что формально асимптотика наименьшего числа различных расстояний неизвестна, работа Гута и Каца была значительным прорывом в этом вопросе, поскольку разрыв между оценками теперь лишь у/log п вместо бывшего пс+о(1). С другой стороны, при d > 3 Эрдёш [3] предположил, что в d-мерном евклидовом пространстве минимальное число различных расстояний между п точками есть 0(n2/d). Известно также [20], что в пространстве R множество с к расстояниями содержит не больше (k+d) точек. Для произвольного нормированного пространства Сванепул [21] выдвинул гипотезу о том, что максимальное число точек, порождающее к расстояний в d-мерном пространстве, не превосходит (к + 1)d, причём равенство достигается лишь в случае, если единичный шар аффинно эквивалентен кубу. Подробнее об этой задаче можно узнать в его обзоре [22].

Эта задача тесно связана с задачей о наибольшей последовательности, равноудалённой вправо. Мы будем говорить, что последовательность различных точек х1, ..., хт пространства равноудалена вправо, если каждая точка равноудалена от всех последующих точек последовательности, то есть для всех i < j < к выполнено \\xi — Xj|| = \\xi — Xk||.

Полянский [23] доказал, что во всяком нормированном пространстве размерности d размер наибольшей равноудалённой вправо последовательности не превосходит 0(3dd). Это улучшение предыдущего результата от Насоди, Паха и Сванепула [24, Следствие 14].

Позднее Насоди и Сванепул [25] предоставили альтернативное доказательство этого факта. Из этого результата следует, что максимальное число точек, порождающее к расстояний в d-мерном пространстве, не превосходит k°(d3d).

Нетрудно видеть, что максимальный размер равноудалённой вправо последовательности в евклидовом пространстве R равен п + 2. В самом деле, это можно доказать индукцией по п. Иные результаты для других пространств R пока неизвестны.

В данной работе получено точное значение размера наибольшей равноудалённой вправо последовательности для пространства R^, а также нижняя

оценка на размер наибольшей равноудалённой вправо последовательности в пространстве

Несмотря на то, что значительная часть комбинаторной геометрии появилась в XX веке, задачи из этой области существовали ещё в XVII веке, когда Иоганн Кеплер [26] выдвинул гипотезу о том, как выглядит плотнейшая упаковка шаров в трёхмерном пространстве. Плотность его упаковки составляет ^/3л/2. Эту гипотезу позднее доказал Томас Хейлс [27] при помощи компьютерного перебора. Плотность же любого размещения равных кругов на плоскости не превосходит как показал Аксель Туэ [28].

Задачи о плотнейших упаковках тесно связаны с задачей о контактном числе. Контактным числом выпуклого тела С С Щ называют наибольшее число его неперекрывающихся конгруэнтных копий, которые можно расположить так, чтобы каждая из них касалась С. Широко известен спор между Исааком Ньютоном и Дэвидом Грегори о том, чему равняется контактное число трёхмерного шара. Шютте и ван дер Варден [29] показали, что это контактное число есть 12. Также известно [30; 31], что контактное число единичного шара в Щ4 есть 24, а в Щ8 ив Щ24 оно равно соответственно 240 и 196 560.

Л. Фейеш Тот и А. Хеппеш [32] рассмотрели обобщение задачи о контактном числе. Пусть в Щ дан шар и семейство шаров того же размера, касающихся исходного (будем называть это семейство первым слоем). Добавим ещё одно семейство шаров того же размера, касающихся хотя бы одного из уже имеющихся (второй слой). Никакие два шара в полученном наборе не должны пересекаться по внутренности. Необходимо найти наибольшее число шаров Т^, не считая исходного, в полученном наборе. Фейеш Тот и Хеппеш показали, что Т2 = 18, а также привели нижние оценки на Т3 и Т4. З. Фюреди и П. А. Лёб [33, последний абзац раздела 6] приписывают Л. Фейеш Тоту и А. Хеппешу следующую гипотезу: всякая подобная конфигурация для трёх слоёв на плоскости содержит не больше 36 дисков, не включая исходного.

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

Все вышеперечисленные оценки достигаются при плотнейшей упаковке дисков, хоть это и не единственная упаковка с таким свойством. Гексагональная упаковка с п слоями представляет пример на 3п(п + 1) дисков. В данной

работе доказана гипотеза Фейеш Тота и Хеппеша об обобщённом контактном числе плоскости для трёх слоёв, а также показана асимптотика обобщённого контактного числа для п слоёв — на самом деле гексагональная упаковка не всегда позволяет расположить наибольшее число дисков в п слоёв.

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

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

1. Найден размер наибольшей равноудалённой вправо последовательности точек пространства .

2. Построена нижняя оценка на размер наибольшей равноудалённой вправо последовательности точек пространства

3. Найдено обобщённое контактное числа плоскости для трёх слоёв.

4. Найдено асимптотическое поведение обобщённого контактного числа плоскости для п слоёв.

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

Научная и практическая значимость: диссертация носит теоретический характер.

Степень достоверности полученных результатов обеспечивается приведёнными строгими доказательствами.

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

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

— «64-я научная конференция МФТИ», МФТИ, Долгопрудный, 2021.

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

Публикации. Результаты диссертации опубликованы в 3 работах, представленных в конце списка литературы. Все эти работы входят в перечень ВАК, две из этих работ опубликованы в журналах, индексируемых базой Scopus.

Благодарности. Автор благодарит своего научного руководителя Александра Полянского за бесчисленные обсуждения и постоянную поддержку в научной работе, Алексея Балицкого за многократную вычитку текста и комментарии, Илью Богданова за упрощение доказательства леммы о равноудалённых вправо последовательностях, Андрея Купавского за упрощение исходной упаковки с асимптотически оптимальной плотностью и Андрея Сергунина за помощь в преодолении гексагонального барьера.

Объем и структура работы. Диссертация состоит из введения, четырёх глав, заключения и двух приложений. Полный объём диссертации составляет 66 страниц с 16 рисунками и 0 таблицами. Список литературы содержит 40 наименований.

Глава 1. Равноудалённые вправо последовательности в 1ж и

Для метрического пространства M назовём его равносторонней размерностью наибольшее число равноудалённых друг от друга точек в M, и обозначим это число через e(M). Эта величина активно изучалась для пространств R при 1 < р < ж. Напомним, что 1^-расстояние между двумя точками х, y £ Rn определяется по формуле

Ух - y||p = Цхг - у1Г + ... + к - Уп1Р)1/Р для любого вещественного р > 1, а в случае р = ж — по формуле

||х - y||ж = max Ixi - yil

%

Нетрудно проверить (см. [6]), что в евклидовом случае e(R^) = п + 1, а в случае максимальной нормы ) = 2П. Нижние оценки представляются соответственно вершинами правильного тетраэдра и гиперкуба. Последовательность х(1),... ,х(т) £ R назовём равноудалённой вправо, если Цх^ - х(г)||р = ||хС?2) -х(г)||р для всех 1 < i < j1 < j2 < т. Неформально говоря, каждая точка равноудалена от всех последующих.

Полянский [23] показал справедливость следующей теоремы, улучшив предыдущий результат от Насоди, Паха и Сванепула [24, Следствие 14]:

Теорема 1. Во всяком нормированном пространстве размерности п размер наибольшей равноудалённой вправо последовательности не превосходит 0(3пп).

Позднее Насоди и Сванепул [25] предоставили альтернативное доказательство этого факта. Этот результат можно применить, в частности, для доказательства верхней оценки на размер множества с к различными расстояниями.

Нетрудно видеть, что максимальный размер равноудалённой вправо последовательности в евклидовом пространстве R равен п + 2. В самом деле, это можно доказать индукцией по п. В качестве примера такой последовательности можно привести центр правильного тетраэдра, после которого идут вершины

тетраэдра в произвольном порядке1. Иные результаты для других пространств Щ пока неизвестны.

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

Теорема 2. Для любого п € N максимальный размер равноудалённой вправо последовательности точек из равен 2П+1 — 1.

Теорема 3. Для любого п € N существует равноудалённая вправо последовательность из 4п — 1 точки в

1.1 Доказательство верхней оценки в теореме 2

Напомним, что частично упорядоченным множеством (сокращённо чум) называется пара V = (Б, где Б есть множество, а ^ — рефлексивное антисимметричное транзитивное отношение на его элементах. Назовём х,у € Б сравнимыми, если х ^ у или у х. В противном случае будем называть их несравнимыми. Множество попарно сравнимых элементов будем называть цепью, а попарно несравнимых — антицепью. Будем называть длиной и шириной множества V соответственно размер наибольшей цепи и антицепи в V. Обозначим длину и ширину чума V соответственно через ¿(V) и и)(Р).

При доказательстве верхней оценки нам понадобится теорема Дилворта.

Теорема 4 (Теорема Дилворта [34]). Пусть V = (Б, — произвольный чум. Тогда ширина т(Р) равна наименьшему числу цепей, на которые можно разбить V. В частности, 1 < ¿(V)т(Р).

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

Для всякого х = (х1,..., хп) € Мп, положим х := (х~\^,..., хп—1) € Мп—1. Определим отношение ^ на следующим образом:

х ^ у тогда и только тогда, когда х = у или ||у — х||то < уп — %п (1.1)

хЭтот пример не единственен. Более того, существует континуально много попарно неизометричных последовательностей максимального размера.

для всех х, у € Мп. В частности, если х ^ у и х = у, то — <уп — хп для всех % € [п — 1].

Строгость этого неравенства сыграет свою роль в будущем. Легко проверить, что (М^, является чумом. В самом деле, рефлексивность и антисимметричность немедленно следуют из определения. Транзитивность же этого отношения следует из неравенства треугольника. Несложно видеть, что верно следствие:

Утверждение 1. Если х, у € Мп сравнимы отношением (1.1), то ||у — х||то = |Уп — %п|. Если же они несравнимы, то ||у — х||то = ||у — х||то.

Мы готовы доказать верхнюю оценку теоремы 2. Зафиксируем равноудалённую вправо последовательность х(1),..., х(т) точек из пространства . Мы докажем индукцией по п, что т < /(п) := 2П+1 — 1.

Во-первых, случай п =1 тривиален. В самом деле, для любых различных х,у € М найдётся единственное х = у (а именно, ^ = 2х — у), для которого — ж| = 1у — ж|. Таким образом, в этом случае т < 3. Перейдём к шагу индукции.

Зафиксируем п > 1. Обозначим через V чум (Б, где Б = {х(1),... , х(т)}, и частичный порядок ^ задан правилом (1.1). Для произвольной пары элементов у, ъ € Б будем говорить, что у встречается раньше ъ, если у = х(г), ъ = х^, и при этом г < ].

Лемма 1. £(Р) < /(1) = 3.

Доказательство. Предположим, элементы х(п),... ,х(ч) попарно сравнимы2. Легко заметить, что данная последовательность также является равноудалённой вправо. Согласно следствию 1 последовательность чисел, соответствующих последним координатам точек этой последовательности также равноудалена вправо. Значит, к < /(1) =3 по базе индукции. □

Лемма 2. п)(Т) < /(п — 1).

Доказательство. Легко заметить, что всякое подмножество А множества Б представляет равноудалённую вправо последовательность, если рассматривать

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

его элементы в порядке их вхождения в х(г). Более того, если А является антицепью, то, согласно следствию 1 множество

А = {X : х е А} с К;

п—1

'00

также представляет равноудалённую вправо последовательность. Таким образом, |А| = |А| < /(п — 1) по предположению индукции. □

Лемма 3. Любые две цепи длины 3 чума V имеют общий элемент.

Доказательство. Предположим противное. Пусть у(1) ^ у(2) ^ у(3) и 7(1) ^

2(2) ^ 2(3) — две цепи, все шесть элементов которых различны. Тогда верны

(1) ^ (2) (3) и (¿) (а )|| (]) (г)

цепочка неравенств уп <Уп < Уп и серия равенств ||у(<) — уи^ = уп — Уп

для всех 1 < г < ] < 3. Такие же ограничения распространяются и на цепь 7(г).

Заметим, что у(2) встречается в равноудалённой вправо последовательности раньше, чем у(1) и у(3). В самом деле, у(1) не может встретиться раньше других двух элементов цепи, поскольку ||у(2) — у(1)||то < ||у(3) — у(1)^ по следствию 1. То же верно и для у(3). Аналогично, 7(2) встречается в последовательности раньше, чем 7(1) и 7(3).

Без ограничения общности3, будем считать, что точка у(1) встречается в последовательности раньше, чем у(3), 7(1) и 7(3). Утверждается, что для всякой

точки V е Б, которая встречается позже у(1) (и, следовательно, позже у(2)),

(3)

верно равенство уп = уп .

В самом деле, положим <1 := ||у(1) — у(2)||то = Уп2 — Уп2. Заметим, что ||у(3) — у(1)И = ^п3) — Уп2 = 2<1 Следовательно, верно равенство IV — у(1)||то = 2(1, поскольку Б представляет равноудалённую вправо последовательность. Аналогично, 11V — у(2) || = ||у(1) — у(2) || = d. С другой стороны,

||V — у(1)|| < ||V — у(2)|| + ||у(2) — у(1)|| < й + ||у(2) — у(1)|| < 2(1,

II ^ 11то — М ^ 11то II*7 ^ 11то — II*7 ^ 11то '

где последнее строгое неравенство следует из того, как отношение порядка у(1) < у(2) было определено4. Таким образом,

2(1 = ||v — у(1)|1 = I Уп — ^ I .

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

4Это единственное место, где мы опираемся на строгость неравенства из определения (1.1).

Если уп = уп1 — 2(1, то уп^ — уп = 3(1, что противоречит неравенству 11V — у (2) || = й. Значит, было получено желаемое неравенство

уп = у^ +2(1 =

Подставив вместо V точки ъ(1) и ъ(3), получим, что Хп1 = ^п3 = уп \ что противоречит условию ъ(1) ^ ъ( 3). □

Рассмотрим произвольное разбиение 5 на наименьшее число непересекающихся цепей. Теорема 4 утверждает, что это число равняется ширине чума, которая не превосходит /(п — 1) по лемме 2. Помимо этого, леммы 1 и 3 влекут, что в этом разбиении максимум одна цепь имеет размер 3, а размеры всех остальных цепей не превосходят 2. Стало быть,

т = |5|< 3 + 2(/(п — 1) — 1) = /(п), что завершает доказательство индукционного перехода.

1.2 Доказательство нижней оценки в теореме 2

Пусть 5 есть семейство всех непустых подмножеств множества [п]. Более формально, положим

5 = {0,1}И\{0}.

Зафиксируем упорядочение (51, Б2,..., 52«—1) множества 5, удовлетворяющее следующему свойству: всякое множество встречается в этой последовательности после всех своих надмножеств — например, для этого можно упорядочить все множества по невозрастанию их размеров, или в порядке убывания чисел, двоичная запись которых задаётся индикаторной функцией этих множеств. Для всех г Е [2П — 1], обозначим через v(г) индикаторный вектор множества Si, то есть для всех к Е [п] положим = 1, если к Е Si, и 0 иначе.

Для всех г Е [2п — 1] определим х(2г—1) := 2—Мг) и х(2) := 21—Мг). Наконец, положим х(2"+1—1) := 0 Е Жп. Мы утверждаем, что последовательность 2п+1_1

(х(г)) ,=1 равноудалена вправо в М^.

В самом деле, положим сг равным ||х(г)|| — то есть 0 для г = 2п+1 — 1, равным 2—(г+1)/2 для всех остальных нечётных г, и 21—/2 для всех чётных г. Мы утверждаем, что |х(^) — х(г)| = ^ для всех 1 < г < ] < 2п+1 — 1. Чтобы это

доказать, рассмотрим три случая.

Рисунок 1.1 — Равноудалённая вправо последовательность точек в К

3

00

Если \г/2~\ = \]/2~\, то х^ = 2х(г), и, следовательно,

I II оо II 11 оо

|х«|| = а.

I II оо ''

Если \г/2] < \]/2~\ < 2п, то выполнено

() _ х«

— ^ < тах|— у| : у е {0,с^},^ е {0,с^}} = тах{} = о,.

С другой стороны, поскольку S\j/2■\ не может являться надмножеством ¿\/2]: найдётся такое к е [п], что к е ¿\/2]\ з/2~\. Значит,

|хСЛ _ х(0|| >| х^ - Х(г)\ I 11 оо — I к к |

= 1 0 — Сг 1 = С;

Наконец, если п = 2п+1 — 1, то Цх(г) — х^У = Цх(г) — 0У = с;, что

тото

завершает доказательство.

На рис. 1.1 приведён пример равноудалённой вправо последовательности точек в , имеющей длину 15. На каждом шаге изображено геометрическое множество возможных расположений всех последующих точек.

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

Обозначим через ^(1),...,v(2n)) вершины стандартного единичного п—мерного кроссполитопа, сдвинутого на вектор е1, упорядоченные следующим образом: скажем, что для вершин с нечётными номерами верно V1*2 г_1) := е1 + е, а для вершин с чётными номерами верно v(2 г) := е1 — еп+1—1 для всех г Е [п], где через е ^ обозначен г-й стандартный базисный вектор.

Затем, как и в предыдущем доказательстве, для всех % Е [2п— 1] определим х(2 г-1) := 2—Vм, а также х(2 г) := 21—гv(г). Наконец, положим х(4п_11 := v(2n) = 0. Мы утверждаем, что последовательность (х(г))4= 11 равноудалена вправо в

В самом деле, положим сг := 11х(г) 11. Утверждается, что Цх^1 — х(г )|1 = сг для всех 1 < %< 2 < 4п — 1. Чтобы показать это, рассмотрим три случая. Если \г/2~\ = \]/2~\, то х^ = 2х(г), и, следовательно,

||х(Я — х(* ) || = ||2х(^ — х(^ || = ||х(^ || = а. Предположим, \г/2] < \^/2] < 2п. Заметим, что если для некоторого

к Е [2,п] у векторов x(i) and x^ обе к-е координаты ненулевые, то |x;/ — xi' | =

М Лз)\

1хк^1 + I |. Если одна из координат х^, х^) равна 0, то это равенство также выполнено. Получаем, что

Е

п

= Л) _ Лз) + V ( I Лз) I + I т(г) I А = Х1 Х1 + ' + 7 к=2

п

_ ) _ гт(3) Л- \ Л

— "Г "Г 7

,Х(Я_ Х«ц = vi x(j) - х(г)\ |x x 'll = Z^ lXk xk

k=1

k=2

( ) ( ) ( ) ( ) k=2

1 Xl + Xl +7 \Xk 1 -

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

Наконец, если п = 4п — 1, то Ух(г) — х^У = Ух(г ) — 0У = с;, что

™ ° ' II 11 то II 11 то '

завершает доказательство.

На рис. 1.2 приведён пример равноудалённой вправо последовательности точек в имеющей длину 11. На каждом шаге изображено геометрическое множество возможных расположений всех последующих точек.

Рисунок 1.2 — Равноудалённая вправо последовательность точек в

1.4 Дальнейшие вопросы

Схожесть двух конструкций наталкивает на вопрос:

Вопрос 1. Верно ли, что для всякого нормированного пространства размерности п размер любой равноудалённой вправо последовательности не превосходит ) — 1 ?

Глава 2. Обобщённое контактное число плоскости для п слоёв

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

Одним из понятий, связанных с локальной структурой упаковки шаров, является контактное число. Напомним, что контактным числом пространства называется наибольшее число ^-мерных шаров одинакового размера без общих внутренних точек, которые могут касаться заданного шара того же радиуса.

Л. Фейеш Тот и А. Хеппеш [32] рассмотрели обобщение задачи о контактном числе. Пусть в дан шар и семейство шаров того же размера, касающихся исходного (будем называть это семейство первым слоем). Добавим ещё одно семейство шаров того же размера, касающихся хотя бы одного из уже имеющихся (второй слой). Никакие два шара в полученном наборе не должны пересекаться по внутренности. Необходимо найти наибольшее число шаров Т^, не считая исходного, в полученном наборе. Фейеш Тот и Хеппеш показали, что Т2 = 18, а также привели нижние оценки на Т3 и Т4. З. Фюреди и П. А. Лёб [33, последний абзац раздела 6] приписывают Л. Фейеш Тоту и А. Хеппешу следующую гипотезу: всякая подобная конфигурация для трёх слоёв на плоскости содержит не больше 36 дисков, не включая исходного.

Введём формальные определения. Для любых двух дисков А и В упаковки V на плоскости назовём контактным расстоянием между А и В такое наибольшее п, что найдётся последовательность дисков И0, И1, ..., Ип е V, для которой А = По, В = Ип, и любые два диска 1 и касаются друг друга. Скажем, что упаковка V имеет контактный радиус п, если найдётся такой диск И е V, называемый исходным, что контактное расстояние между диском И и любым другим диском из V не превосходит п. Обозначим через /(п) наибольшее возможное число дисков в упаковке с контактным радиусом п.

Гексагональная упаковка дисков даёт нижнюю оценку /(п) — 3п(п + 1) + 1, однако существуют упаковки с п слоями, дающие лучшие оценки, нежели гексагональная. Мы докажем следующую теорему.

2п

Теорема 5. /(п) = (1 + о(1))п2.

3

В следующей секции мы сначала покажем справедливость приведённой верхней оценки на /(п). Затем мы введём определение (а, Ъ)-мельницы, и, наконец, покажем, как с помощью мельниц построить упаковки, дающие желаемую нижнюю оценку обобщённого контактного числа.

Список литературы диссертационного исследования кандидат наук Голованов Александр Игоревич, 2022 год

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

1. Pach J., Agarwal P. K. Combinatorial geometry. — John Wiley & Sons, 2011.

2. Erdos P., Szekeres G. A combinatorial problem in geometry // Compositio Mathematica. — 1935. — Vol. 2. — P. 463-470.

3. Erdos P. On Sets of Distances of n Points // The American Mathematical Monthly. — 1946. — t. 53, № 5. — c. 248—250.

4. Jozsa S., Szemeredi E. The number of unit distances on the plane // Infinite and Finite Sets. — 1973. — t. 2. — c. 939—950.

5. Beck J., Spencer J. Unit distances // Journal of Combinatorial Theory, Series A. — 1984. — t. 37, № 3. — c. 231—238.

6. Petty C. Equilateral sets in Minkowski spaces // Proceedings of the American Mathematical Society. — 1971. — t. 29, № 2. — c. 369—374.

7. Alon N., Pudlak P. Equilateral sets in // Geometric & Functional Analysis GAFA. — 2003. — t. 13, № 3. — c. 467—482.

8. Guy R. K. An olla-podrida of open problems, often oddly posed // The American Mathematical Monthly. — 1983. — t. 90, № 3. — c. 196—200.

9. J Bandelt H., Chepoi V., Laurent M. Embedding into rectilinear spaces // Discrete & Computational Geometry. — 1998. — t. 19, № 4. — c. 595—604.

10. Koolen J., Laurent M., Schrijver A. Equilateral dimension of the rectilinear space // Designs, Codes and Cryptography. — 2000. — t. 21, № 1. — c. 149— 164.

11. Smyth C. Equilateral sets in Idp // Thirty Essays on Geometric Graph Theory, ed. J. Pach, Springer, New York. — 2013. — c. 483—488.

12. Swanepoel K. J. A problem of Kusner on equilateral sets // Archiv der Mathematik. — 2004. — t. 83, № 2. — c. 164—170.

13. Swanepoel K. J., Villa R. Maximal equilateral sets // Discrete & Computational Geometry. — 2013. — t. 50, № 2. — c. 354—373.

14. Moser L. On the different distances determined by n points // The American Mathematical Monthly. — 1952. — t. 59, № 2. — c. 85—91.

15. Beck J. On the lattice property of the plane and some problems of Dirac, Motzkin and Erdos in combinatorial geometry // Combinatorica. — 1983. — т. 3, № 3. — с. 281—297.

16. Chung F. R. The number of different distances determined by n points in the plane // Journal of Combinatorial Theory, Series A. — 1984. — т. 36, № 3. — с. 342—354.

17. Chung F. R., Szemeredi E., Trotter W. T. The number of different distances determined by a set of points in the Euclidean plane // Discrete & Computational Geometry. — 1992. — т. 7, № 1. — с. 1—11.

18. Szekely L. A. Crossing numbers and hard Erdos problems in discrete geometry // Combinatorics, Probability and Computing. — 1997. — т. 6, № 3. — с. 353—358.

19. Guth L, Katz N. H. On the Erdos distinct distances problem in the plane // Annals of mathematics. — 2015. — с. 155—190.

20. Bannai E., Bannai E., Stanton D. An upper bound for the cardinality of an s-distance subset in real euclidean space, II // Combinatorica. — 1983. — т. 3, № 2. — с. 147—152.

21. Swanepoel K. J. Cardinalities of ^-distance sets in Minkowski spaces // Discrete Mathematics. — 1999. — т. 197. — с. 759—767.

22. Swanepoel K. J. Combinatorial Distance Geometry in Normed Spaces // New Trends in Intuitive Geometry / под ред. G. Ambrus [и др.]. — Berlin, Heidelberg : Springer Berlin Heidelberg, 2018. — с. 407—458. — ISBN 978-3-662-57413-3. — DOI: 10.1007/978-3-662-57413-3_17.

23. Polyanskii A. Pairwise intersecting homothets of a convex body // Discrete Mathematics. — 2017. — т. 340, № 8. — с. 1950—1956.

24. Naszodi M, Pach J., Swanepoel K. Arrangements of homothets of a convex body // Mathematika. — 2017. — т. 63, № 2. — с. 696—710.

25. Naszodi M, Swanepoel K. J. Arrangements of homothets of a convex body II // Contributions to Discrete Mathematics. — 2018. — т. 13. — с. 116—123.

26. Kepler J. Strena seu de nive sexangula. — Frankfurt: Tampach, 1611.

27. Hales T. C. A proof of the Kepler conjecture // Annals of mathematics. — 2005. — c. 1065—1185.

28. Thue A. Über die dichteste Zusammenstellung von kongruenten Kreisen in einer Ebene. — J. Dybwad, 1911.

29. Schutte K., Waerden B. L. van der. Das problem der dreizehn Kugeln // Mathematische Annalen. — 1952. — t. 125, № 1. — c. 325—334.

30. Musin O. R. The problem of the twenty-five spheres // Russian Mathematical Surveys. — 2003. — aBr. — t. 58, № 4. — c. 794—795. — DOI: 10.1070/ rm2003v058n04abeh000651.

31. Odlyzko A. M, Sloane N. J. New bounds on the number of unit spheres that can touch a unit sphere in n dimensions // Journal of Combinatorial Theory, Series A. — 1979. — t. 26, № 2. — c. 210—214.

32. Toth L. F., Heppes A. A Variant of the Problem of the Thirteen Spheres // Canadian Journal of Mathematics. — 1967. — t. 19. — c. 1092—1100. — DOI: 10.4153/CJM-1967-100-x.

33. Füredi Z., Loeb P. A. On the best constant for the Besicovitch covering theorem // Proc. Amer. Math. Soc. — 1994. — t. 121. — c. 1063—1073. — DOI: https://doi.org/10.1090/S0002-9939-1994-1249875-4.

34. Dilworth R. P. A decomposition theorem for partially ordered sets // Classic Papers in Combinatorics. — Springer, 2009. — c. 139—144.

35. Folkman J. H, Graham R. L. A packing inequality for compact convex subsets of the plane // Canadian Mathematical Bulletin. — 1969. — t. 12, № 6. — c. 745—752.

36. Musin O. R. Properties of the Delaunay triangulation // Proceedings of the thirteenth annual symposium on Computational geometry. — https://arxiv.org/pdf/math/0312050.pdf, 1997. — c. 424—426.

37. Edelsbrunner H. Alpha shapes - a survey // Tessellations in the Sciences. — 2010. — t. 27. — c. 1—25.

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

38. Golovanov A., Kupavskii A., Sagdeev A. Odd-distance and right-equidistant sets in the maximum and Manhattan metrics // European Journal of Combinatorics. — 2023. — т. 107. — с. 103603.

39. Голованов А. Обобщённое контактное число плоскости для нескольких сло-ёв // Труды МФТИ. — 2022. — т. 14, № 3. — с. 111—116.

40. Golovanov A. On the maximum size packings of disks with kissing radius 3 // Moscow Journal of Combinatorics and Number Theory. — 2022. — т. 11, № 3. — с. 263—286.