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

На ирамах рукописи

Гольдштейн Виталий Борисович

Оценки чисел Борсука и Грюнваума

для (ОД)- и (-1,0,1)-многогранников в пространствах малой размерности

Специальность 01.01.09 дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2013

2 6 СЕН 2013

005533825

Работа выполнена на кафедре анализа данных факультета инноваций и высоких технологий Федерального государственного образовательного учреждения высшего профессионального образования «Московский физико-технический институт (государствен! i ы й университет)»

Научный руководитель: доктор физико-математических наук, профессор Рай-городскнй Андрей Михайлович. Место работы: Федеральное государственное образовательное учреждение высшего профессионального образования «Московский государствен н ы й у н и верситет». Официальные оппоненты:

• д. ф.-м. н., профессор Кабатяпский Григорий Анатольевич. Место работы: Федеральное государственное бюджетное учреждение науки Институт Проблем Передачи Информации имени A.A. Харкевича Российской академии паук.

• к. ф.-м. п., Митричева Ирина Михайловна. Место работы: Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования «Финансовый университет при Правительстве Российской Федерации».

Ведущая организация: Хабаровское отделение Федерального государственного бюджетного учреждения пауки Института прикладной математики Дальневосточного отделения Российской академии наук.

Защита диссертации состоится 2U па заседании диссертационного совета Д 002.U17.U2 при Федеральном государственном бюджетном учреждении пауки «Вычислительный центр им. A.A. Дородницына Российской академии паук» по адресу: Российская Федерация, 119333, Москва, Вавилова, 40. С диссертацией можно ознакомиться в библиотеке ВЦ РАН. Автореферат разослан с? н т si^O2 Ъ_•

Ученый секретарь диссертационного совета Д 002.017.02 при Федеральном государственном бюджетном учреждении науки «Вычислительный центр им. A.A. Дородницына Российской академии наук» доктор физико-математических наук, профессор

Рязанов Владимир Васильевич

Общая характеристика работы

Актуальность темы

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

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

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

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

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

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

3 Н. Hadwiger, Kleine Studie zur kombinatorischen Geometrie der Sphäre // Nagoya Math. J. - 1955. - V. 8. - P. 45-48.

4 H. Hadwiger, Eulers Charakteristik und kombinatorische Geometrie // J. Reine Angew. Math. - 1955. - V. 194. - P. 101-110.

идет о хроматическом числе метрического пространства — величине P-.Á), равной минимальному количеству цветов, в которые можно так покрасить все точки М, чтобы между точками одного цвета не было расстояния из множества А С R+:

Х(М,р,Л) = min{x : М = Мг U ... U Мх, Vi Vx,yeM¡ р(х, у) & А}.

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

Рассмотрим произвольное ограниченное неодноточечное множество V С К". Диаметром множества V называется величина

diainV= sup р(а, b),

a,beV

где р(а, Ь) — евклидово расстояние между векторами. Представим V в виде

V = Vil)V2U...UVf,

где каждое множество V¿ имеет диаметр, строго меньший диаметра V. Это всегда возможно, поскольку любое множество может быть заключено в n-мерный куб со стороной diam V, который в свою очередь можно разделить на конечное число кубиков произвольно малого наперед заданного диаметра. Таким образом, корректно определена величина f(V), равная минимальному числу / частей меньшего диаметра, па которые можно разбить множество V. Положим

fin) = max f(V).

Описанная выше конструкция с покрытием множества кубом и разбиением этого куба на более мелкие кубики позволяет получить оценку/(п) < ] + 1)™. В то же время, беря в качестве V множество вершин правильного n-мерного симплекса, мы видим, что f(V) — п-f 1, и, значит, /(n) > п +1. Более того, К. Борсук доказал в 1933 году 5, что f(Bn) =n-fl, где Вп — n-мерный шар. Наконец, очевидно

5 К. Borsuk, Drei Sátze über die n-dimensionale euklidische Sphare // Fundamenta Math. - 1933. - V. 20. - P. 177-190.

равенство /(1) = 2, и не очень трудно показать, что /(2) = 3. Последний факт также установил Борсук с помощью одного более раннего результата Й. Пала6. В итоге Борсук задал вопрос: верно ли, что всегда f(n) = п + 1?

Впоследствии большинство специалистов в области верило в то, что ответ на вопрос Борсука должен быть положительным. И потому довольно быстро появился термин "гипотеза Борсука". Естественно, гипотеза гласила, что f(n) = п + 1. хотя сам Борсук столь определенных предположений не делал. В 1993 году Дж. Кан и Г. Калаи 7 опровергли гипотезу и размерности 2015. В дальнейшем был получен ряд усилений этих оценок8' 9,ю,и,12,13_ ДуЧШИд на данный момент результат, который получили А. Хинрихс и X. Рихтер14 в 2003 году, опровергает гипотезу в размерности 298. Доказать или опровергнуть гипотезу Борсука в размерностях от 4 до 297 до сих пор не удалось. Более того, для растущего п известны лишь оценки

(1.225 ... + о(1))^ < f(n) < (1.224... + о(1))и,

6 J. Pál, Uber ein elementares Variationsproblem // Danske Videnskab. Selskab., Math.-Fys. Meddel. - 1920. - V. 3, N2.

7 J. Kahn, G. Kalai, A counterexample to Borsuk's conjecture // Bulletin (new series) of the AMS. - 1933. - V. 29, N 1. - P. 60-62.

8 A. Nilli, On Borsuk's problem // Contemporary Mathematics. — 1994. — V. 178. — P. 209- 210.

9 J. Grey, B. Weissbach, Ein weiteres Gegenbeispiel zur Borsukschen Vermutung // Univ. Magdeburg, Fakultát für Matliematik. — 1997. — Preprint 25.

10 A.M. Райгородский, О размерности в проблеме Борсука // Успехи матем. наук. - 1997. - Т. 52, Выи. б. - С. 181-182.

11 В. Weissbach, Sets with large Borsuk number // Beitráge zur Algebra und Geometrie. - 2000. - V. 41. - P. 417- 423.

12 A. Hinrichs, Spherical codes and Borsuk's conjecture // Discr. Math. — 2002. —

V. 243. - P. 253- 256.

13 0. Pikhurko, Borsuk's conjecture fails in dimensions 321 and 322. —

arXiv:math.CO/0202112.

14 A. Hinrichs, C. Richter, New sets with large Borsuk numbers. —

http://www.minet.unijena.de/ hinrichs/paper/18/borsuk.pdf.

зазор между которыми крайне велик15,16. Поэтому многие специалисты продолжают работу над проблемой Борсука.

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

У = Vi U V2 U ... U Vg,

где каждое множество Vi можно заключить в шар с диаметром, равным диаметру V. Будем называть такие множества вложенными в шар диаметра d = diam V. Обозначим Са замкнутый шар диаметра d. Аналогичный открытый шар обозначим С,;. Введем функцию g(V), равную минимальному числу д частей, вложенных в Cd, на которые можно разбить множество V. Функцией g(V) будем обозначать минимальное число д частей, вложенных в Cd, на которые можно разбить множество V.

По аналогии с f(n) введем

д(п) = max g(V), д{п) = maxg(V).

КСК vСК

Проблема Грюнбаума, возникшая в 50-е годы прошлого века, сводится как раз к отысканию величин д(п) и д(п).

Видно, что задачи Борсука и Грюнбаума тесно связаны. Например, для любого V выполнено f(V) < (п + l)g(V) (ср. упомянутый выше результат Борсука о разбиении шара), а для любого конечного V выполнено f(V) < g(V). Грюнбаум предположил, что справедлива гипотеза, более сильная, нежели гипотеза Борсука: д(п) = п + 1 Разумеется, это предположение было опровергнуто еще быстрее, и

"A.M. Райгородский, Об одной оценке в проблеме Борсука // Успехи матем. наук.

- 1999. - Т. 54, Вып. 1. - С. 185-186.

16 О. Schramm, Illuminating sets of constant width // Mathematika. — 1988. — V. 35.

- P. 180-189.

17 Райгородский A. M. Проблемы Борсука, Грюнбаума и Хадвигера для некоторых классов многогранников и графов // Доклады РАН. — 2003. — Т. 388, G. — С. 738- 742.

сейчас известно, что18'

(1.067... + о(1))" < д(п) < (1.224... + о(1))п, (1.067... + о(1))п < д(п) < (1.224 ... + o(l))n.

Цель работы

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

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

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

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

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

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

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

18 L. Danzer, On the /с-tli diameter in Ed and a problem of Grunbaum // Proc.

Colloquium on Convexityio — 1965. — P. 41.

19 J. Doitrgain, J. Lindenstrauss. On covering a set in R'' by balls of the same diameter

// Geometric Aspects of Functional Analysis, Lecture Notes in Math. — 1991. — V. 1469.

- P. 138-144.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации

Результаты по теме диссертации опубликованы в 5 работах автора. Список работ приведен в конце автореферата. Работы [1-3J опубликованы в журналах из списка ВАК. Работы [4-5] опубликованы в сборниках тезисов конференций.

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

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

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

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

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

Напомним основные моменты истории, имеющие непосредственное отношение к диссертации, и введем необходимые обозначения.

В 1999 году Г.М. Циглер начал изучение задачи Борсука для (0,1)-многогранников в малых размерностях. Совместно с учениками он показал, что такие многогранники допускают разбиение нап + 1 часть меньшего диаметра при

всех п < 920.21.22.23, Иными словами, если и существуют контрпримеры к гипотезе Борсука в размерностях п < 9, то они не могут быть получены с помощью упомянутых конструкций.

В случае растущей размерности аналогичными задачами занимался A.M. Рай-городский24.

Поскольку разбиение многогранника на части равносильно разбиению множества его вершин (диаметры достигаются только на парах вершин), то можно работать только с конечными множествами V С {0,1}" и V С {—1,0,1}™. Дадим несколько определений.

Графом расстояний множества К С К" с расстоянием d называется граф Gd(V), вершинами которого являются элементы множества V, а ребрами соединены точки на расстоянии d. Более формально, граф Gu(V) есть пара, состоящая из множества вершин V и множества ребер

Е = {{а, Ь}| a G V, Ъ € V, p(a, b) = d}.

Вместе с тем иод графом диаметров множества V мы понимаем граф расстояний с расстоянием, равным величине diam V. Будем обозначать граф диаметров через Gd-mmV(V).

Во второй главе рассматривается проблема Борсука. С помощью нетривиального алгоритма перебора (см. раздел 2.1 диссертации) всех многогранников были доказаны следующие теоремы.

Теорема 1. Для любого п < 9 и для всех V С {0,1}п выполнено

. 20 G.M. Ziegler, Lectures on 0/1-polytopes // Polytopes — Combinatorics and Computation (G. Kalai and G.M. Ziegler, eds.) // DMV-seminar. — 2000. — V. 29.

- P. 1-44.

21 G.M. Ziegler, Coloring Hamming graphs, optimal binary codes, and the 0/1-Borsuk

problem in low dimensions // Lect. Notes Comput. Sei. - 2001. — V. 2122. - P. 159-171.

22 F. Schiller, Zur Berechnung und Abschätzung von Färbungszahlen und der i)-

Funktion von Graphen // Diplomarbeit. — Berlin: TU, 1999.

23 J. Petersen, Färbung von Borsuk-Graphen in niedriger Dimension. — Diplomarbeit.

- TU Berlin, 1998.

24 A.M. Райгородский, Проблемы Борсука и Грюнбаума для решетчатых многогранников // Известия РАН. - 2005. - Т. 69, 3. - С. 81-108.

НУ) — X (Счнату(У)) < п + 1. Здесь \ ~ это обычное хроматическое число графа.

Теорема 2. Для любого п < 6 и для всех V С { — 1,0,1}п выполнено 1(У) = х(С^ту(У))<П+1.

Чтобы такой перебор стал возможен за разумное время, было применено множество соображений, которые мы называем "отсечениями перебора" (описание этого "термина" дается в параграфе 2.1.2 диссертации). Основная функция алгоритма занимается перебором всех подмножеств V' С {0,1}™ фиксированного диаметра (Р. Перебор производится путем последовательного добавления в строящееся множество одной вершины за другой. И при добавлении очередной вершины всякий раз нужно, естественно, рассматривать одни из двух вариантов:

1. добавить вершину в множество У;

2. не добавлять вершину в множество V'.

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

Важная идея перебора заключается в порядке перебора. Перебор осуществляется отдельно для каждого возможного диаметра. Благодаря этому становится возможным применить отсечение "максимальности по включению" (описано в параграфе 2.1.4 диссертации), позволяющее не рассматривать множества, являющиеся подмножествами других множеств такого же диаметра.

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

Для проверки гипотезы был осуществлен перебор с описанными методами отсечений. Программа была реализованна на языке программирования С++ для минимизации второстепенных накладных расходов.

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

Запуск программы производился на компьютере с частотой процессора 3.2 Ггц. Программа работала на одном процессоре и не использовала параллельных вычислений. Благодаря большому количеству различных отсечений все варианты стало возможно рассмотреть за несколько минут. Время работы программы при использовании всех отсечений указано в таблице.

Таблица 1

Множество V Время работы

{0,1}", п < б меньше секунды

{ОД}7 5 секунд

{0,1}8 10 секунд

{0,1}9 20 минут

{-1,0,1}", п < 6 меньше секунды

{-1,0,1}", п = 6 18 минут

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

Теорема 3. Для любого п <9 и для всех V С {0,1}п выполнено д(У) < п + 1. Теорема 4. Для любого п <7 и для всех V С {0,1}" выполнено д(У) < п + 1.

Теорема 5. Для любого п < 5 и для всех V С { — 1,0,1}" выполнено д(У) < п +1. Теорема 6. Для любого п < 4 и для всех УС {—1,0,1}п выполнено д(У) < п + 1.

Для больших размерностей программа была запущена на кластере из 30 компьютеров, в каждом из которых 12 ядер. Проверка для размерности п = 9 утверждения д(У) < 10 для подмножеств V С {0,1}9 потребовала чуть больше 8 дней, тогда как на одном персональном компьютере процесс занял бы около 7 лет.

Без использования компьютера были доказаны более слабые оценки для теорем 3 и 4 (описано в разделе 3.2 диссертации).

Теорема 7. Для любого п <7 и для всех V С {0,1}" выполнено д(У) < п + 1. Теорема 8. Для любого п < 5 и для всех V С {0,1}" выполнено д(У) < п + 1.

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

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

Работы автора по теме диссертации

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

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

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

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

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

Подписано в печать 11.09.2013. 60x90/16. Усл. печ. л. 1,25. Тираж 100 Экз. Типография ООО "Ай-клуб" (Печатный салон МДМ) 119146, г. Москва, Комсомольский проспект, д.28 Тел. 8-495-782-88-39

Федеральное государственное образовательное учреждение высшего профессионального образования «Московский физико-технический институт (государственный университет)»

На правах рукописи

04201362772

Гольдштейн Виталий Борисович

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

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

01.01.09 - Дискретная математика и математическая кибернетика

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель --д.ф.-м.н. А.М. Райгородский

Москва, 2013

Оглавление

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

Введение 6

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.4 Обозримое доказательство в случае (0,1)-многогранников ... 44 3.4.1 Доказательства вспомогательных лемм..........44

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложение 65

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

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

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

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

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

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

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

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

хуг (или 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 страниц.

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

Глава 1

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

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

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

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

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

Рассмотрим произвольное ограниченное неодноточечное множество V С Диаметром множества V называется величина

сНат1/= вир р(а, Ь),

где р(а, Ь) — евклидово расстояние между векторами. Представим V в виде

V = ^ и ¥2 и ... и V/,

где каждое множество Vi имеет диаметр, строго меньший диаметра V. Это всегда возможно, поскольку любое множество может быть заключено в п-мерный куб со стороной diamF, который в свою очередь можно разделить на конечное число кубиков произвольно малого наперед заданного диаметра. Таким образом, корректно определена величина /(V), равная минимальному числу / частей меньшего диаметра, на которые можно разбить множество V.

Положим

f(n) — max f(V).

J v ' FcM" v 1

Описанная выше конструкция с покрытием множества кубом и разбиением этого куба на более мелкие кубики позволяет получить оценку f(n) < (\\/п\ + 1)п. В то же время, беря в качестве V множество вершин правильного n-мерного симплекса, мы видим, что /(V) = п+1, и, значит, f(n) > n+ 1. Более того, К. Борсук доказал в 1933 году (см. [18]), что f(Bn) = п + 1, где Вп — n-мерный шар. Наконец, очевидно равенство /(1) = 2, и не очень трудно показать, что /(2) = 3. Последний факт также установил Борсук с помощью одного более раннего результата Й. Пала (см. [18] и [19]). В итоге Борсук задал вопрос: верно ли, что всегда f(n) = п + 1?

Впоследствии большинство специалистов в области верило в то, что ответ на вопрос Борсука должен быть положительным. И потому довольно быстро появился термин "гипотеза Борсука". Естественно, гипотеза гласила, что f(n) = n+ 1, хотя сам Борсук столь определенных предположений не делал.

Проблема Борсука — это одна из основополагающих задач комбинаторной геометрии. В разное время ей занимались многие известные специалисты. О ней есть книги (см. [6], [20], [21]) и обзоры (см. [13], [14], [22], [23], [24]), в которых можно найти подробную историю возникновения и развития проблематики. В следующем параграфе мы остановимся на наиболее важном для нас аспекте: речь пойдет о контрпримерах к гипотезе Борсука.

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

В течение шестидесяти лет гипотеза Борсука оставалась ни доказанной, ни опровергнутой. Был получен ряд промежуточных результатов. Например, в 1945 году Г. Хадвигер показал, что любое множество с гладкой границей допускает разбиение на нужное число частей (см. [25]). А на рубеже 1980-х 90-х гг. О. Шрамм (см. [26]) и Ж. Бурген-Й. Линденштраусс

(см. [27]) установили самую лучшую из известных верхних оценок для f{n): f{n) < (1.224.. .+о(1))п. С одной стороны, результат Хадвигера кажется чем-то очень близким к доказательству гипотезы: аппроксимируем произвольное множество гладким, и все получится. С другой стороны, экспоненциальная верхняя оценка выглядит слишком далекой от истины, если верить в гипотезу-

И все-таки гипотеза оказалась неверна. В 1993 году Дж. Кан и Г. Калаи построили первый контрпример к ней. Они доказали, что /(тг) > (1.203 ... + о(1))^ и что эта оценка превосходит п+ 1, начиная с размерности 2015 (см. [28]). В дальнейшем был получен ряд усилений этого результата. Эти усиления мы укажем в таблице 1.1.

Таблица 1.1

Авторы публикации Год Ссылка Размерность контрпримера к гипотезе п >

Дж. Кан, Г. Калаи 1993 [28] 2015

А. Нилли 1994 [29] 946

Б. Вайссбах, Й. Грей 1997 [30] 903

А. М. Райгородский 1997 [31] 561

Б. Вайссбах 2000 [32] 560

А. Хинрихс 2001 [33] 324

О. Пихурко 2002 [34] 323

А. Хинрихс, X. Рихтер 2003 [35] 298

Вместе с тем известно, что гипотеза верна при п < 3 (см. [18], [36]-[40]). Наконец, асимптотическая нижняя оценка Кана Калаи была уточнена А. М. Райгородским (см. [41]) в 1999 году. И теперь мы знаем, что

(1.2255 ... + о( 1))^ < f(n) < (1.224 ... + о(1))п,

/(п) =72+1 При П < 3,

f{n) > п + 1 при п > 298.

Отметим, что все нижние оценки для /(п), а также практически все контрпримеры к гипотезе Борсука получены с помощью построения множеств V С {0,1}п и У С {—1,0,1}п. Выпуклые оболочки таких множеств принято называть (0,1)-многогранниками и (—1, 0,1)-многогранниками. Послед-

ние иногда называют еще кро