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

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

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

для (0,1)- и (1, 0, 1)-многогранников

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

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

АВТОРЕФЕРАТ

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

Москва — 2013

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

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

Научный руководитель:

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

Официальные оппоненты:

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

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

Хабаровское отделение Федерального государственного

Ведущая организация:

бюджетного учреждения науки Института прикладной математики Дальневосточного отделения Российской академии наук.

Защита диссертации состоится на заседании диссертационного совета Д 002.017.02 при Федеральном государственном бюджетном учреждении науки «Вычислительный центр им. А.А. Дородницына Российской академии наук» по адресу: Российская Федерация, 119333, Москва, Вавилова, 40.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

Автореферат разослан.

Ученый секретарь диссертационного совета Д 002.017.02 при Федеральном государственном бюджетном учреждении науки «Вычислительный центр им. А.А.

Дородницына Российской академии наук» доктор физико-математических наук, профессор Рязанов Владимир Васильевич

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

Актуальность темы Комбинаторная геометрия, двум классическим проблемам которой посвящена настоящая работа, — это сравнительно молодая, но очень бурно развивающаяся дисциплина. Различные задачи, которые сейчас принято относить к области комбинаторной геометрии, были, конечно, известны задолго до начала ХХ века.

Например, комбинаторикой разбиений, упаковок и покрытий пространств занимались в XIX веке Вороной, Золотарев, Минковский и др.1 Тем не менее, в самостоятельную науку комбинаторная геометрия превратилась, по-видимому, только к середине прошлого столетия. Даже сам термин “комбинаторная геометрия” обычно приписывают Хадвигеру, который употребил его впервые в 1955 году.

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

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

Среди метрических задач особенно выделяются две — задача Нелсона–Эрдеша– Хадвигера и задача Борсука. В случае задачи Нелсона–Эрдеша–Хадвигера речь Г.Ф. Вороной, Собрание сочинений, Киев, 1952–1953.

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

3 H. Hadwiger, Kleine Studie zur kombinatorischen Geometrie der Sphare // 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.

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

(,, ) = min{ : = 1..., x, y (x, y) }.

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

Рассмотрим произвольное ограниченное неодноточечное множество R.

Диаметром множества называется величина где (a, b) — евклидово расстояние между векторами.

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

Положим Описанная выше конструкция с покрытием множества кубом и разбиением этого куба на более мелкие кубики позволяет получить оценку () ( + 1). В то же время, беря в качестве множество вершин правильного -мерного симплекса, мы видим, что ( ) = + 1, и, значит, () + 1. Более того, К. Борсук доказал в 1933 году 5, что ( ) = + 1, где — -мерный шар. Наконец, очевидно K. Borsuk, Drei Stze uber die -dimensionale euklidische Sphre // Fundamenta Math. — 1933. — V. 20. — P. 177–190.

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

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

Калаи опровергли гипотезу в размерности 2015. В дальнейшем был получен ряд усилений этих оценок8, 9,10,11,12, получили А. Хинрихс и Х. Рихтер14 в 2003 году, опровергает гипотезу в размерности 298. Доказать или опровергнуть гипотезу Борсука в размерностях от 4 до 297 до сих пор не удалось. Более того, для растущего известны лишь оценки J. Pl, 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, Fakultt fr Mathematik. — 1997. — Preprint 25.

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

— 1997. — Т. 52, Вып. 6. — С. 181–182.

11 B. Weissbach, Sets with large Borsuk number // Beitrge 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.

O. Pikhurko, Borsuk’s conjecture fails in dimensions 321 and 322. — arXiv:math.CO/0202112.

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

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

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

Обозначим замкнутый шар диаметра. Аналогичный открытый шар обозначим. Введем функцию ( ), равную минимальному числу частей, вложенных в, на которые можно разбить множество. Функцией ( ) будем обозначать минимальное число частей, вложенных в, на которые можно разбить множество По аналогии с () введем Проблема Грюнбаума, возникшая в 50-е годы прошлого века, сводится как раз к отысканию величин () и ().

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

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

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

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

— P. 180–189.

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

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

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

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

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

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

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

L. Danzer, On the -th diameter in and a problem of Grnbaum // Proc.

Colloquium on Convexityю — 1965. — P. 41.

19 J. Bourgain, 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.

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

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

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

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

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

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

в разные годы на кафедральном семинаре кафедры дискретной математики ФИВТ МФТИ под руководством профессора А.М. Райгородского, в 2012 году на 54й научной конференции МФТИ, в 2012 году на научно-исследовательском спецсеминаре “Дискретная математика и математическая кибернетика” кафедры математической кибернетики факультета ВМК МГУ под руководством профессоров В.Б. Алексеева, А.А.

Сапоженко и С.А. Ложкина.

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

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

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

Структура и объем диссертации Диссертационная работа состоит из введения, 3 глав, заключения и приложения.

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

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

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

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

В 1999 году Г.М. Циглер начал изучение задачи Борсука для (0,1)многогранников в малых размерностях. Совместно с учениками он показал, что такие многогранники допускают разбиение на + 1 часть меньшего диаметра при всех 920,21,22,23. Иными словами, если и существуют контрпримеры к гипотезе Борсука в размерностях 9, то они не могут быть получены с помощью упомянутых конструкций.

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

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

Графом расстояний множества R с расстоянием называется граф ( ), вершинами которого являются элементы множеcтва, а ребрами соединены точки на расстоянии. Более формально, граф ( ) есть пара, состоящая из множества вершин и множества ребер Вместе с тем под графом диаметров множества мы понимаем граф расстояний с расстоянием, равным величине diam. Будем обозначать граф диаметров через diam ( ).

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

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. Sci. — 2001. — V. 2122. — P. 159–171.

22 F. Schiller, Zur Berechnung und Abschtzung von Frbungszahlen und der a a Funktion von Graphen // Diplomarbeit. — Berlin: TU, 1999.

23 J. Petersen, Frbung von Borsuk-Graphen in niedriger Dimension. — Diplomarbeit.

— TU Berlin, 1998.

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

( ) = (diam ( )) + 1. Здесь — это обычное хроматическое число графа.

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

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

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

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

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

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

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

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

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

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

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

С помощью адаптированного метода были доказаны следующие теоремы.

Теорема 3.

Теорема 4.

Теорема 5.

Теорема 6.

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

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

Теорема 7.

Теорема 8.

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

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

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

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

[2] В.Б. Гольдштейн, О проблеме Борсука для (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 Grnbaum problems for (0, 1)- and (1, 0, 1)-polyhedra in low dimensions // A collection of the abstracts of 4th Polish Combinatorial Conference, 2012.