Доклады Российской академии наук. Математика, информатика, процессы управления, 2021, T. 499, № 1, стр. 44-48
О ПОКРЫТИИ ПЛОСКИХ МНОЖЕСТВ
А. Д. Толмачев 1, *, Д. С. Протасов 1, **
1 Московский физико-технический институт (национальный исследовательский университет)
Долгопрудный, Московская обл., Россия
* E-mail: tolmachev.ad@phystech.edu
** E-mail: dmitry.protasov@gmail.com
Поступила в редакцию 22.04.2021
После доработки 22.04.2021
Принята к публикации 02.05.2021
Аннотация
В статье предлагаются методы улучшения верхних и нижних оценок для различных покрытий множеств на плоскости. Приведены новые оценки для различного количества частей разбиения, а также предложения по обобщению представленных методов.
1. ВВЕДЕНИЕ И ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ
Пусть F – произвольное ограниченное множество на плоскости, $n \in \mathbb{N}$. Определим следующую величину:
Другими словами, среди всех покрытий множества F некоторыми $n$ множествами ${{F}_{1}}, \ldots ,{{F}_{n}}$ мы хотим выбрать покрытия, состоящие из множеств как можно меньшего диаметра.
Заметим, что величина ${{d}_{n}}(F)$ не изменится, если потребовать, чтобы все множества покрытия были выпуклыми и замкнутыми. Это следует из того, что диаметр замыкания выпуклой оболочки произвольного множества F совпадает с диаметром F.
Заметим, что для произвольного F последовательность ${{d}_{n}}(F)$ является невозрастающей, поскольку в классе всех покрытий n + 1 множествами существует подкласс, для которого ${{F}_{{n + 1}}} = \emptyset $, совпадающий с классом всех покрытий $n$ множествами.
Определим величину ${{d}_{n}} = sup{{d}_{n}}(F)$, где супремум берется по всем множествам F единичного диаметра на плоскости. Из сделанного выше замечания ясно, что последовательность dn не возрастает.
Исследование величин dn глубоко мотивировано классической проблемой Борсука о разбиении множеств на части меньшего диаметра (см. [1–4]). В разные годы Х. Ленц (см. [5]), М. Дембиньски и М. Лассак (см. [6]), В. Филимонов (см. [7]), Д. Белов и Н. Александров (см. [8]), В. Коваль (см. [9]) оценивали величину dn для различных значений $n$. Нам удалось существенно усилить многие из предшествующих результатов. Новые результаты мы приведем в разделе 2, а ниже дадим еще несколько определений, важных для формулировок и их доказательств.
Определение 1. Множество $\Omega \subset {{\mathbb{R}}^{2}}$ называется универсальной покрышкой, если любое плоское множество $F$ единичного диаметра может быть полностью накрыто $\Omega $ (т.е. на плоскости существует множество ${{\Omega }_{0}}$, конгруэнтное $\Omega $, такое что $F \subset {{\Omega }_{0}}$).
В 1920 г. Й. Пал доказал [10], что правильный шестиугольник со стороной $\tfrac{1}{{\sqrt 3 }}$ является универсальной покрышкой. Введем для него обозначение ${{\Omega }_{6}}$. Приведем еще одно определение.
Определение 2. Система множеств S = = ${{\{ {{\Omega }_{\alpha }}\} }_{{\alpha \in I}}}$ называется универсальной покрывающей системой, если любое плоское множество F единичного диаметра может быть полностью накрыто одним из множеств ${{\Omega }_{\alpha }}$. Здесь $I$ – некоторый (возможно, бесконечный) набор индексов.
Рассмотрим произвольное множество F единичного диаметра. Накроем его множеством ${{\Omega }_{6}}$ и проведем все шесть прямых, которые перпендикулярны отрезкам, соединяющим центр шестиугольника со всеми его вершинами, и отстоят от центра на расстояние $\frac{1}{2}$. Эти прямые отсекают от ${{\Omega }_{6}}$ шесть треугольников. Очевидно, для каждой пары треугольников, содержащих противоположные вершины, хотя бы один из них не содержит внутренних точек F (поскольку расстояние между этими треугольниками равно единице). Назовем такой треугольник отсеченным. Далее покрышку с тремя подряд такими отсеченными уголками обозначим ${{\Omega }_{{6,2}}}$, а покрышку с тремя отсеченными через один уголками обозначим ${{\Omega }_{{6,1}}}$. Несложно видеть, что $\{ {{\Omega }_{{6,1}}},{{\Omega }_{{6,2}}}\} $ – универсальная покрывающая система.
Заметим, что правильный шестиугольник со стороной $\tfrac{1}{{\sqrt 3 }}$ (т.е. покрышка ${{\Omega }_{6}}$) с двумя отсеченными указанным выше способом уголками при вершинах, идущих через одну, тоже является универсальной покрышкой, потому что им можно накрыть и ${{\Omega }_{{6,1}}}$, и ${{\Omega }_{{6,2}}}$. Обозначим такую универсальную покрышку ${{\Omega }_{2}}$.
Кроме того, будем рассматривать величину
Далее определим величину $d_{n}^{'} = supd_{n}^{'}(F)$, где супремум берется по всем множествам F единичного диаметра на плоскости. Ясно, что последовательность $d_{n}^{'}$ невозрастающая. Более того, $d_{n}^{'} = 0$ при всех натуральных $n \geqslant 7$ как следствие известной оценки $\chi ({{\mathbb{R}}^{2}}) \leqslant 7$ для хроматического числа плоскости (см. [11]).
В следующем разделе мы приведем формулировки новых результатов и их сопоставление с ранее известными, а также вкратце обсудим идеи доказательств.
2. УЛУЧШЕННЫЕ РЕЗУЛЬТАТЫ
2.1. Формулировки
Приведем таблицу улучшенных результатов для элементов последовательности ${{d}_{n}}$ при $1 \leqslant n \leqslant 30$ (табл. 1). В столбце “комментарий” указано, на сколько процентов уменьшился “зазор” между верхней и нижней оценкой в результате предложенных в данной работе улучшений. В последнем столбце указан список фигур, рассматриваемых в качестве универсальной покрывающей системы для доказательства оценки сверху.
Таблица 1.
n | Новая оценка снизу | Старая оценка снизу | Старая оценка сверху | Новая оценка сверху | Коммен-тарий | Используемая УПС |
---|---|---|---|---|---|---|
1 | – | 1.0000 | 1.0000 | – | точная | – |
2 | – | 1.0000 | 1.0000 | – | точная | – |
3 | – | 0.8660 | 0.8660 | – | точная | – |
4 | – | 0.7071 | 0.7071 | – | точная | – |
5 | – | 0.5877 | 0.6020 | 0.5953 | 47% | ${{\Omega }_{{6,2}}},{{\Omega }_{{6,1.1}}},{{\Omega }_{{6,1.2.1}}},$${{\Omega }_{{6,1.2.2}}},{{\Omega }_{{6,1.2.3}}}$ |
6 | – | 0.5051 | 0.5344 | – | – | – |
7 | – | 0.5000 | 0.5000 | – | точная | – |
8 | – | 0.4338 | 0.4456 | – | – | – |
9 | – | 0.3826 | 0.4047 | – | – | – |
10 | 0.3667 | 0.3420 | 0.4012 | – | 41% | – |
11 | 0.34201) | 0.3333 | 0.3970 | 0.3942 | 19% | ${{\Omega }_{2}}$ |
12 | – | 0.3333 | 0.3660 | – | – | – |
13 | – | 0.3333 | 0.3660 | 0.3550 | 33% | ${{\Omega }_{2}}$ |
14 | – | 0.3090 | 0.3324 | – | – | – |
15 | – | 0.2928 | 0.3324 | 0.3226 | 24% | ${{\Omega }_{2}}$ |
16 | – | 0.2817 | 0.3324 | 0.3191 | 26% | ${{\Omega }_{6}}$ |
17 | – | 0.2701 | 0.3324 | 0.3010 | 48% | ${{\Omega }_{2}}$ |
18 | – | 0.2588 | 0.3324 | 0.29892) | 46% | ${{\Omega }_{6}}$ |
19 | – | 0.2500 | 0.2857 | – | – | – |
20 | – | 0.2500 | 0.2857 | – | – | – |
21 | – | 0.2393 | 0.2857 | 0.2723 | 29% | ${{\Omega }_{2}}$ |
22 | – | 0.2323 | 0.2857 | 0.2650 | 39% | ${{\Omega }_{2}}$ |
23 | – | 0.2225 | 0.2857 | 0.2650 | 33% | ${{\Omega }_{2}}$ |
24 | – | 0.2167 | 0.2849 | 0.2610 | 35% | ${{\Omega }_{{6,1}}},{{\Omega }_{{6,2}}}$ |
25 | – | 0.2079 | 0.2776 | 0.2610 | 24% | ${{\Omega }_{{6,1}}},{{\Omega }_{{6,2}}}$ |
26 | – | 0.2030 | 0.2709 | 0.2610 | 15% | ${{\Omega }_{{6,1}}},{{\Omega }_{{6,2}}}$ |
27 | – | 0.2000 | 0.2646 | 0.2610 | 5% | ${{\Omega }_{{6,1}}},{{\Omega }_{{6,2}}}$ |
28 | – | 0.2000 | 0.2587 | 0.2500 | 15% | ${{\Omega }_{2}}$ |
29 | – | 0.1950 | 0.2531 | 0.2500 | 5% | ${{\Omega }_{2}}$ |
30 | – | 0.1939 | 0.2479 | – | – | – |
1) Точное значение полученной нижней оценки для d11 равно sin(π/9). 2) Точное значение полученной верхней оценки для d18 равно $\sqrt {\frac{{2 - \sqrt 3 }}{3}} $. |
На рис. 1 изображены все покрывающие множества, используемые для получения верхних оценок. Разбиения для доказательства верхних оценок приведены в [18]. В доказательствах нижних оценок величин ${{d}_{{10}}}$, ${{d}_{{11}}}$ и ${{d}_{{54}}}$ в качестве множества диаметра 1 был рассмотрен круг единичного диаметра.
Все константы приведены с четырьмя верными знаками после запятой. Кроме улучшений, показанных в таблице, доказаны оценки $\tfrac{1}{{\sqrt {52} }} \leqslant {{d}_{{54}}}$ и $d_{6}^{'} \leqslant 0.5.$
2.2. Идеи доказательств
Для доказательства того, что ${{d}_{n}} \leqslant \rho $, где $\rho $ – некоторое фиксированное число, рассмотрим некоторую универсальную покрывающую систему $S$ и разобьем каждое из множеств, входящих в нее, на n частей, диаметр каждой из которых не превосходит $\rho $. В табл. 1 в столбце “используемая УПС” приведена универсальная покрывающая система, используемая в доказательстве указанной верхней оценки величины dn для соответствующего значения $n$.
Разбиения элементов универсальной покрывающей системы на n частей диаметра ρ для всех улучшенных оценок мы не будем подробно описывать в данной работе, однако рассмотрим одно из наиболее красивых разбиений, которое значительно улучшает верхнюю оценку величины ${{d}_{{18}}}$.
Положим $\rho = \sqrt {\tfrac{{2 - \sqrt 3 }}{3}} \approx 0.2989$ и будем доказывать, что ${{d}_{{18}}} \leqslant \rho $. Рассмотрим универсальную покрывающую систему S, состоящую из одного множества – универсальной покрышки ${{\Omega }_{6}}$.
На рис. 2 правильный шестиугольник $ABCDEF$ со стороной $\tfrac{1}{{\sqrt 3 }}$ соответствует покрышке ${{\Omega }_{6}}$. Окружность $\omega $ вписана в этот шестиугольник. Отрезок AO пересекает окружность $\omega $ в точке N, а перпендикуляр к прямой AO, проходящий через точку N, пересекает отрезки AB и AF в точках ${{A}_{1}}$ и ${{A}_{2}}$ соответственно. Аналогично получим точки ${{B}_{1}},{{B}_{2}}$, ..., F1, F2. Можно показать, что двенадцатиугольник ${{F}_{1}}{{F}_{2}}...{{B}_{1}}{{B}_{2}}{{A}_{1}}{{A}_{2}}$ является правильным. Тогда разобьем исходный шестиугольник на 6 равных четырехугольников $O{{A}_{2}}A{{B}_{2}}$, $O{{B}_{2}}B{{C}_{2}}$, …, $O{{F}_{2}}F{{A}_{2}}$. Рассмотрим один из этих четырехугольников и покажем, как его разбить на три части диаметра в точности, $\rho $, откуда будет следовать, что исходный шестиугольник можно разбить на 18 частей диаметра $\rho $. Без ограничения общности будем рассматривать четырехугольник $O{{D}_{2}}D{{E}_{2}}$, который является вписанным, так как $\angle {{E}_{2}}O{{D}_{2}} = 60^\circ $ и $\angle {{E}_{2}}D{{D}_{2}} = 120^\circ $. Пусть $\gamma $ – описанная около $O{{D}_{2}}D{{E}_{2}}$ окружность, а $S$ – центр $\gamma $. Можно показать, что радиус окружности $\gamma $ равен в точности $\rho \, = \,\sqrt {\tfrac{{2 - \sqrt 3 }}{3}} $. Окружность радиуса $\rho $ с центром в точке ${{D}_{1}}$ пересекает отрезки $O{{E}_{2}}$ и $O{{D}_{2}}$ вточках U и V соответственно. Тогда четырехугольник $O{{D}_{2}}D{{E}_{2}}$ разбивается на два четырехугольника $OUSV$, $US{{D}_{1}}{{E}_{2}}$ и один пятиугольник $D{{D}_{1}}SV{{D}_{2}}$, диаметр каждого из которых равен $\rho $. На рис. 2 длины отрезков, выделенных жирным пунктиром, равны $\rho $. Тем самым показано, что шестиугольник $ABCDEF$ можно разбить на 18 частей, диаметр каждой из которых равен $\rho $. На рис. 2 выделены части данного разбиения.
Выше мы показали, как получается верхняя оценка на примере оценки величины d18. Также важно отметить, что эта оценка – единственная, которую удалось точно выразить в радикалах среди всех полученных в данном исследовании оценок.
Список литературы
Borsuk K. Drei Sätze über die n-dimensionale euklidische Sphäre // Fundamenta Math. 1933. V. 20. P. 177–190.
Raigorodskii A.M. Coloring Distance Graphs and Graphs of Diameters // Thirty Essays on Geometric Graph Theory. J. Pach ed. Springer. 2013. P. 429–460.
Райгородский А.М. О разбиении множеств на части меньшего диаметра // Доклады РАН. Математика, информатика, процессы управления. 2020. Т. 495. С. 74–77.
Berdnikov A.V., Raigorodskii A.M. Bounds for Borsuk’s numbers using special distance graphs // submitted to Information Transmission Problems.
Lenz H. Zerlegung ebener Bereiche in konvexe Zellen von möglichst kleinem Durchmesser // Jber. Deutsch. Math. Verein. 1956. V. 58. P. 87–97.
Dembiński M., Lassak M. Covering plane sets with sets of three times less diameter // Demonstratio Math. 1985. V. 18. № 2. P. 517–526.
Филимонов В.П. О покрытии плоских множеств // Матем. сборник. 2010. Т. 201. № 8. С. 127–160.
Белов Д., Александров Н. О разбиении плоских множеств на шесть частей малого диаметра // Труды МФТИ. 2012. Т. 4. № 1. С. 11–13.
Коваль В.О. О разбиении плоских множеств на 6 частей малого диаметра // Зап. научн. сем. ПОМИ. 2020. Т. 497. С. 100–123.
Pal J. Uber ein elementares Variationsproblem // Danske Videnskab. Selskab. Math.-Fys. Meddel. 1920. V. 3. № 2.
Райгородский А.М. Проблема Борсука и хроматические числа метрических пространств // Успехи матем. наук. 2001. Т. 56. № 1. С. 107–146.
Просанов Р.И. Контрпримеры к гипотезе Борсука, имеющие большой обхват // Матем. заметки. 2019. Т. 105. № 6. С. 890–898.
Боголюбский Л.И., Райгородский А.М. Замечание о нижних оценках хроматических чисел пространств малой размерности с метриками ${{l}_{1}}$ и ${{l}_{2}}$ // Матем. заметки. 2019. Т. 105. № 2. С. 187–213.
Raigorodskii A.M., Koshelev M.M. New bounds on clique-chromatic numbers of Johnson graphs // Discrete and Applied Math. 2020. V. 283. P. 724–729.
Райгородский А.М., Кошелев М.М. Новые оценки клико-хроматических чисел графов Джонсона // Доклады РАН. Математика, информатика, процессы управления. 2020. Т. 490. С. 78–80.
Prosanov R. A new proof of the Larman–Rogers upper bound for the chromatic number of the Euclidean space // Discrete Applied Mathematics. 2020. №. 276. P. 115–120.
Купавский А.Б., Сагдеев А.А. Теория Рамсея в пространстве с чебышевской метрикой // Успехи матем. наук. 2020. Т. 75. № 5. С. 191–192.
Разбиения для верхних оценок. https://github.com/Vosatorp/Partitions
Дополнительные материалы отсутствуют.
Инструменты
Доклады Российской академии наук. Математика, информатика, процессы управления