Оценки чисел Борсука и Грюнбаума для (0,1)- и (-1, 0, 1)-многогранников в пространствах малой размерности тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Гольдштейн, Виталий Борисович

• Гольдштейн, Виталий Борисович
• кандидат физико-математических наук
• 2013

Оглавление диссертации кандидат физико-математических наук Гольдштейн, Виталий Борисович

Оглавление

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

Введение

1 История проблем Борсука и Грюнбаума

1.1 История проблемы Борсука

1.1.1 Возникновение гипотезы Борсука

1.1.2 Опровержение гипотезы

1.2 История возникновения проблемы Грюнбаума

1.3 Постановка задачи и формулировки результатов

2 О проблеме Борсука для (0,1)- и (—1,0,1)-многогранников

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

2.1 Описание алгоритма

2.1.1 Устройство алгоритма

2.1.2 Отсечения перебора

2.1.3 Отсечение пустоты подграфа Ей

2.1.4 Отсечение максимальности по включению

2.1.5 Отсечения, связанные с симметрией

Изометрическое преобразование

Отсечение изометрии отражения

Отсечение изометрии перестановки координат

2.1.6 Отсечение раскраски графа

Отсечение жадной раскраски

Отсечение раскраски табу

2.1.7 Дополнительные отсечения

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

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

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

2.3 Работа программы

3 О проблеме Грюнбаума для (0,1)- и (—1, 0,1)-многогранников

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

3.1 Описание алгоритма

3.1.1 Устройство алгоритма

3.1.2 Отсечения перебора

3.1.3 Отсечение пустоты подграфа Fd

3.1.4 Отсечение максимальности по включению

3.1.5 Отсечения, связанные с симметрией

3.1.6 Отсечение помещения в шары

Отсечение жадным алгоритмом помещения в шары

Отсечение переборным алгоритмом помещения в шары

3.2 Работа программы

3.3 Замечание о покрытии (0,1)-многогранников шарами с с?2 полуцелыми координатами центров

3.4 Обозримое доказательство в случае (0,1)-многогранников

Лемма о множествах диаметра 1

Леммы о множествах больших диаметров

Леммы о покрытии замкнутыми шарами множеств диаметра л/2 и их следствия

Леммы о покрытии открытыми шарами множеств диаметра л/2 и их следствия

3.4.2 Доказательства основных лемм

Лемма о покрытии замкнутыми шарами (0, 1)-

многранников в размерности б

Лемма о покрытии замкнутыми шарами (0, 1)-

многранников в размерности 7

Лемма о покрытии открытыми шарами (0, 1)-

многранников в размерности 5

Заключение и открытые проблемы

Список использованных источников

Приложение

Общий исходный код для двух программ

Исходный код алгоритма в проблеме Борсука

Исходный код алгоритма в проблеме Грюнбаума

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

N — множество натуральных чисел; Ж — множество действительных чисел; \А\ — мощность конечного множества А;

С?[У] — подграф графа С, индуцированный на множество V; х(@) ~~ хроматическое число графа;

А \ В — множество элементов, входящих в Л, но не входящих в В; [а] — целая часть числа а;

р(х, у) — евклидово расстояние между точками х и у\ сНат V — диаметр множества У;

хуг (или 0^1) — сокращенная запись вектора с координатами х, у иг.

Введение диссертации (часть автореферата) на тему «Оценки чисел Борсука и Грюнбаума для (0,1)- и (-1, 0, 1)-многогранников в пространствах малой размерности»

Введение

Комбинаторная геометрия, двум классическим проблемам которой посвящена настоящая работа, — это сравнительно молодая, но очень бурно развивающаяся дисциплина. Различные задачи, которые сейчас принято относить к области комбинаторной геометрии, были, конечно, известны задолго до начала XX века. Например, комбинаторикой разбиений, упаковок и покрытий пространств занимались в XIX веке Вороной, Золотарев, Минковский и др. (см. [1]). Тем не менее, в самостоятельную науку комбинаторная геометрия превратилась, по-видимому, только к середине прошлого столетия. Даже сам термин "комбинаторная геометрия" обычно приписывают Хадвигеру, который употребил его впервые в 1955 году (см. [2], [3], [4]).

В целом, комбинаторная геометрия — это наука о взаимном расположении некоторых геометрических объектов. Одними из первых задач современной комбинаторной геометрии являются проблемы типа Хелли (см. [2]), источником которых служит утверждение, доказанное Хелли в 1912 году: если в пространстве Еп даны выпуклые множества ..., Ат, т > п + и любые п + 1 множеств среди них имеют непустое пересечение, то и все эти множества имеют непустое пересечение.

Еще одна важная задача комбинаторной геометрии, сыгравшая значительную роль в формировании всей дисциплины, — это проблема Гохберга-Болтянского-Маркуса-Хадвигера об освещении границы выпуклого тела (см. [5]). Говорят, что точка х Е д£1 границы выпуклого тела О освещается в направлении /, если прямая тг, проходящая через х в направлении проходит также через внутренность О, причем по данному направлению х — первая точка из Г2 на прямой 7Г. Гипотеза о том, что для освещения всех точек границы П С Еп всегда хватит 2П направлений (наихудший случай — параллелепипед), до сих пор не доказана и не опровергнута (см. [5], [б]).

Исключительную роль в комбинаторной геометрии играют задачи, имею-

щие "метрический" характер. В более или менее общей постановке соответствующие вопросы звучат так: каково наименьшее число частей (цветов), на которые можно так разбить (в которые можно так покрасить) некоторые подмножества данного метрического пространства, чтобы внутри каждой части (среди точек одного цвета) не было каких-то расстояний?

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

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

тт{х : М = Мг и ... и Мх, V г V х, у е М{ р(х, у) £ £?}.

О хроматическом числе имеется огромная литература (см. [7]-[15]).

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

К проблеме Борсука тесно примыкает и проблема Грюнбаума — вторая центральная задача нашей работы. Она сводится к нахождению минимального количества шаров диаметра 1, которыми покрывается любое множество диаметра 1 в Мп. О ней мы подробнее расскажем в первой и третьей главах диссертации.

Имеется огромное количество других важных задач в области. Приведем некоторые примеры.

1. Проблемы типа Эрдеша—Секереша. Здесь речь идет об отыскании наименьшего числа точек общего положения на плоскости (или в пространстве иной размерности), среди которых с гарантией есть вершины выпуклого п-угольника (выпуклого многогранника с п вершинами), удовлетворяющего тем или иным дополнительным ограничениям (см. [16]). В частности, можно говорить просто о выпуклых п-угольниках (многогранниках), можно обсуждать выпуклые п-угольники (многогранники) с не более к точками внутри, можно рассматривать выпуклые п-угольники

(многогранники), в которых число внутренних точек делится на некоторое д, и т.д.

2. Задачи о дистанционных графах. Эти задачи глубоко мотивированы проблемой Нелсона-Эрдеша-Хадвигера. Граф называется дистанционным, если его вершины — точки пространства, а ребра — отрезки определенной длины. По сути, проблема Нелсона-Эрдеша-Хадвигера — это задача о хроматическом числе дистанционного графа, у которого множество вершин — все М. Однако есть масса вопросов о дистанционных графах, которые интересны сами по себе: как много может быть у них ребер, треугольников, клик произвольного размера, циклов? как устроены независимые множества вершин в них (т.е. множества, внутри которых нет ребер)? и т.д. Об этом можно прочесть в книге [9].

3. Задачи о замощениях, упаковках, покрытиях и пр. Здесь основная постановка звучит примерно так: как устроены фигуры (тела), с помощью которых можно так или иначе заполнить пространство, и как ведут себя сами заполнения? Заполнения называются упаковками, если множества, из которых они состоят, не перекрываются, но не факт, что при этом каждая точка пространства хотя бы одному из них принадлежит. Заполнения называются покрытиями, если, напротив, множества могут перекрываться и при этом все точки пространства задействованы. Ставятся вопросы о форме и плотности "плотнейших" упаковок и "редчайших" покрытий. Есть и многочисленные постановки иного типа (см.

[17])-

Цель работы

1. Разработать подход для анализа задач Борсука и Грюнбаума с помощью компьютерного перебора.

2. Проверить гипотезу, что при малых п всякий (0,1)- и (-1,0,1)-многогранник в п-мерном пространстве можно разбить на п + 1 часть меньшего диаметра.

3. Проверить гипотезу, что при малых п всякий (0,1)- и (-1,0,1)-многогранник в п-мерном пространстве можно покрыть п+1 открытыми или закрытыми шарами такого же диаметра.

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

1. Разработан алгоритмический подход для анализа задач Борсука и Грюн-баума с помощью компьютерного перебора.

2. Доказано, что любой (0,1)- и (—1, 0,1)-многогранник в п-мерном пространстве можно разбить на п + 1 часть меньшего диаметра при п < 9 и п < 6 соответственно.

3. Доказано, что любой (0,1)- и (—1, 0,1)-многогранник в п-мерном пространстве можно покрыть п + 1 замкнутым шаром такого же диаметра при п < 9 и п < 5 соответственно.

4. Доказано, что любой (0,1)- и (—1, 0,1)-многогранник в п-мерном пространстве можно покрыть п + 1 открытым шаром такого же диаметра при п < 7 и п < 4 соответственно.

5. Без использования компьютера было доказано, что любой (0,1)-многогранник в п-мерном пространстве можно покрыть п+1 замкнутым шаром такого же диаметра при п < 7 и п + 1 открытым шаром такого же диаметра при п < 5.

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

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

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

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

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

Результаты имеют теоретическое значение. Они подтверждают невозможность опровержения гипотез Борсука и Грюнбаума в малых размерностях

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

Апробация работы

Результаты диссертации докладывались:

• в разные годы на кафедральном семинаре кафедры дискретной математики ФИВТ МФТИ иод руководством профессора A.M. Райгородского,

• в 2012 году на 54й научной конференции МФТИ,

• в 2012 году на научно-исследовательском спецсеминаре "Дискретная математика и математическая кибернетика" кафедры математической кибернетики факультета ВМК МГУ под руководством профессоров В.Б. Алексеева, А.А. Сапоженко и С.А. Ложкина.

• в 2012 году на четвертой Польской Конференции по Комбинаторике, Бедлево, Польша.

• в 2012 и 2013 годах на научном семинаре отдела Интеллектуальных систем ВЦ РАН под руководством К. В. Рудакова.

Публикации

Результаты по теме диссертации опубликованы в 5 работах автора. Работы [55], [56] и [57] опубликованы в журналах из списка ВАК. Работы [58], [59] опубликованы в сборниках тезисов конференций.

Структура и объем диссертации

Диссертационная работа состоит из введения, 3 глав, заключения и приложения. Список использованных источников включает 59 наименований. Общий объем диссертации составляет 138 страниц.

Благодарности. Автор признателен профессору Андрею Михайловичу Райгородскому за постановку задач и неоценимую помощь в работе.

Список литературы диссертационного исследования кандидат физико-математических наук Гольдштейн, Виталий Борисович, 2013 год

Список использованных источников

[1] Г.Ф. Вороной, Собрание сочинений, Киев, 1952-1953.

[2] Л. Данцер, Б. Грюнбаум, В. Кли, Теорема Хелли, Москва, "Мир", 1968.

[3] Н. Hadwiger, Kleine Studie zur kombinatorischen Geometrie der Sphäre, Nagoya Math. J, 8 (1955), 45-48.

[4] H. Hadwiger, Eulers Charakteristik und kombinatorische Geometrie, J. Reine Angew. Math, 194 (1955), 101-110.

[5] V.G. Boltyanski, H. Martini, P.S. Soltan, Excursions into combinatorial geometry, Berlin, Universitext Springer, 1997.

[6] В.Г. Болтянский, И.Ц. Гохберг, Теоремы и задачи комбинаторной геометрии, Москва, "Наука", 1965.

[7] A. Soifer, The Mathematical Coloring Book, Springer, 2009.

[8] L.A. Szekely, Erdos on unit distances and the Szemeredi - Trotter theorems, Paul Erdos and his Mathematics, Bolyai Series Budapest, J. Bolyai Math. Soc., Springer, 11 (2002), 649-666.

[9] P. Brass, W. Moser, J. Pach, Research problems in discrete geometry, Springer, 2005.

[10] P.K. Agarwal, J. Pach, Combinatorial geometry, New York, John Wiley and Sons Inc., 1995.

[11] V. Klee, S. Wagon, Old and new unsolved problems in plane geometry and number theory, Math. Association of America, 1991.

[12] A.M. Райгородский, Линейно-алгебраический метод в комбинаторике, Москва, МЦНМО, 2007.

13] A.M. Raigorodskii, Coloring distance graphs and graphs of diameters, collection of papers, ed. J. Pach, 2012.

14] A.M. Райгородский, Проблема Борсука и хроматические числа метрических пространств, Успехи матем. наук, 56 (2001), N1, 107—146.

15] A.M. Райгородский, Хроматические числа, Москва, МЦНМО, 2003.

161 W. Morris, V. Soltan, The Erdos-Szekeres problem on points in convex position, Bulletin (new series) of the Amer. Math. Soc., 37 (2000), N4, 437 — 458.

171 Дж. Конвей, H. Слоэн, Упаковки шаров, решетки и группы, Москва, "Мир", 1990.

18] К. Borsuk, Drei Sätze über die n-dimensionale euklidische Sphäre, Fundamenta Math., 20 (1933), 177-190.

191 J. Pal, Uber ein elementares Variationsproblem, Danske Videnskab. Selskab., Math.-Fys. Meddel, 3 (1920), N2.

20] A.M. Райгородский, Проблема Борсука, Москва, МЦНМО, 2006.

21] A.M. Райгородский, Системы общих представителей в комбинаторике и их приложения в геометрии, Москва, МЦНМО, 2010.

221 A.M. Raigorodskii, Three lectures on the Borsuk partition problem, London Mathematical Society Lecture Note Series, 347 (2007), 202-248.

23] A.M. Raigorodskii, The Borsuk partition problem: the seventieth anniversary, Mathematical Intelligencer, 26 (2004), N3, 4—12.

241 A.M. Райгородский, Вокруг гипотезы Борсука, Итоги науки и техники, Сер. "Современная математика", 23 (2007), 147—164.

25] Н. Hadwiger, Uberdeckung einer Menge durch Mengen kleineren Durchmessers, Comm. Math. Helv., 18 (1945/46), 73—75; Mitteilung betreffend meine Note: Uberdeckung einer Menge durch Mengen kleineren Durchmessers, Comm. Math. Helv., 19 (1946/47), 72-73.

[26] O. Schramm, Illuminating sets of constant width, Mathematika, 35 (1988), 180-189.

[27] J. Bourgain, J. Lindenstrauss, On covering a set in Rd by balls of the same diameter, Geometric Aspects of Functional Analysis (J. Lindenstrauss and V. Milman, eds.), Lecture Notes in Math. Berlin Springer-Verlag, 1469 (1991), 138-144.

[28] J. Kahn, G. Kalai, A counterexample to Borsuk's conjecture, Bulletin (new series) of the AMS, 29 (1933), N1, 60-62.

[29] A. Nilli, On Borsuk's problem, Contemporary Mathematics, 178 (1994), 209— 210.

[30] J. Grey, B. Weissbach, Ein weiteres Gegenbeispiel zur Borsukschcn Vermutung, Univ. Magdeburg, Fakultät für Mathematik, 25 (1997).

[31] A.M. Райгородский, О размерности в проблеме Борсука, Успехи матем. наук, 52 (1997), N6, 181-182.

[32] В. Weissbach, Sets with large Borsuk number, Beiträge zur Algebra und Geometrie, 41 (2000), 417-423.

[33] A. Hinrichs, Spherical codes and Borsuk's conjecture, Discrete Math, 243 (2002), 253-256.

[34] O. Pikhurko, Borsuk's conjecture fails in dimensions 321 and 322, arXiv:math.CO /0202112.

[35] A. Hinrichs, C. Richter, New sets with large Borsuk numbers, Discrete Math, 270 (2003), 137-147.

[36] H.G. Eggleston, Covering a three-dimensional set with sets of smaller diameter, J. London Math. Soc., 30 (1955), 11—24.

[37] A. Heppes, Terbeli ponthalmazok felosztdsa kisebb ätmeröjü reszhalmazok összegäre, A magyar tudomanyos akademia, 7 (1957), 413—416.

[38] B. Grünbaum, A simple proof of Borsuk's conjecture in three dimensions, Proc. Cambridge Philos. Soc, 53 (1957), 776-778.

[39] B.B. Макеев, Об аффинных образах ромбододекаэдра, описанных вокруг трехмерного выпуклого тела, Зап. научн. семин. ПОМИ, 246 (1997), 191-195.

[40] B.B. Макеев, Аффинно-вписанные и аффинно-описанные многоугольники и многогранники, Зап. научн. семин. ПОМИ, 231 (1996), 286—298.

[41] A.M. Райгородский, Об одной оценке в проблеме Борсука, Успехи матем. наук, 54 (1999), N2, 185-186.

[42] A.M. Райгородский, Проблемы Борсука, Грюнбаума и Хадвигера для некоторых классов многогранников и графов, Доклады РАН, 388 (2003), N6, 738—742.

[43] L. Danzer, On the k-th diameter in Ed and a problem of Grünbaum, Proc. Colloquium on Convexity, Copenhagen, 41 (1965).

[44] G.M. Ziegler, Lectures on 0/1-polytopes, Polytopes, Combinatorics and Computation (G. Kalai and G.M. Ziegler, eds.), DMV-seminar, BirkhäuserVerlag Basel, 29 (2000), 1-44.

[45] G.M. Ziegler, Coloring Hamming graphs, optimal binary codes, and the 0/1-Borsuk problem in low dimensions, Lect. Notes Computer Science, 2122 (2001), 159-171.

[46] F. Schiller, Zur Berechnung und Abschätzung von Färbungszahlen und der d-Funktion von Graphen, Diplomarbeit, TU Berlin, 1999.

[47] J. Petersen, Färbung von В orsuk- Graphen in niedriger Dimension, Diplomarbeit, TU Berlin 1998.

[48] A.M. Райгородский, Проблема Борсука для (0,1)-многогранников и кросс-политопов, Доклады РАН, 371 (2000), 600—603.

[49] A.M. Райгородский, Проблема Борсука для (0,1)-многогранников и кросс-политопов, Доклады РАН, 384 (2002), 593—597.

[50] A.M. Райгородский, Проблема Борсука для целочисленных многогранников, Матем. сборник, 193 (2002), N10, 139-160.

[51] A.M. Райгородский, Проблемы Борсука и Грюнбаума для решетчатых многогранников, Известия РАН, 69 (2005), N3, 81—108.

[52] A. Hertz, D. Werra, Using tabu search techniques for graph coloring, Computing, 39 (1987), N4, 345-351.

[53] J. Dean, S. Ghemawat, MapReduce: Simplified Data Processing on Large Clusters, Symposium on Operating System Design and Implementation, San Francisco, 2004.

[54] В.П. Филимонов, О покрытии плоских множеств, Матем. Сборник, 201 (2010), N8, 127-160.

[55] В.Б. Гольдштейн, О проблеме Борсука для (0,1)- и (—1,0,1)-многогранпиков в пространствах малой размерности, Труды МФТИ, 4 (2012), N1, 91-110.

[56] В.Б. Гольдштейн, О проблеме Грюнбаума для (0,1)- и (-1,0,1)-многогранников в пространствах малой размерности, Труды МФТИ, 4 (2012), N4, 41-50.

[57] В. Б. Гольдштейн, О проблеме Борсука и Грюнбаума для (0,1)- и (—1,0,1)-многогранников в пространствах малой размерности // Доклады РАН , 448 (2013), N2, 131-132.

[58] В.Б. Гольдштейн, О проблеме Борсука для (0,1)-многогранников и кросс-политопов // Сборник тезисов 54-ой научной конференции МФТИ, 2012.

[59] V.B. Goldshteyn, A.M. Raigorodskii, The Borsuk and Griinbaum problems for (0, 1)- and (—1,0, l)-polyhedra in low dimensions // A collection of the abstracts of 4th Polish Combinatorial Conference, 2012.