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

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

1.2) . В последнем параграфе текущего раздела, опишем дальнейшую структуру статьи. 1.1.    История возникновения проблем Грюнбаума и Борсука

Рассмотрим произвольное ограниченное неодноточечное множество У С R+ Диаметром множества У называется величина diamУ = sup p(a, b), a,ber где p(a, b) — евклидово расстояние между векторами.

Представим У в виде

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

Положим f (п) = ™f (У).

Описанная выше конструкция с покрытием множества, кубом и разбиением этого куба, на более мелкие кубики позволяет получить оценку f(п) 6 (f Дп^ + 1)^п. В то же время, взяв в качестве У множество вершин правильного п-мерного симплекса, мы видим, что f (У) = п + 1, и, значит, f (п) > п + 1. Более того, К. Борсук доказал в 1933 году (см. [1]), что f (В^п) = п + 1, где В^п — п-мерный шар. Наконец, очевидно равенство f (1) = 2, и не очень трудно показать, что f (2) = 3. Последний факт также установил Борсук с помощью одного более раннего результата И. Пала (см. [1] и [2]). В итоге Борсук задал вопрос: верно ли. что всегда f (п) = п + 17

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

Проблема Борсука — это одна из основополагающих задач комбинаторной геометрии. В разное время этой проблемой занимались многие известные специалисты. О ней есть книги (см. [3] — [8]) и обзоры (см. [9] — [13]), в которых можно найти подробную историю возникновения и развития проблематики. Здесь мы заметим лишь, что гипотеза Борсука была опровергнута, и сейчас известно, что она верна при п Е {1, 2, 3} и неверна при п >  298 (см. [14] - [21]).

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

Представим V в виде

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

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

д(п) = max g(V),

V ■'

д(п) = max g(V).

V R

Как мы увидим в дальнейшем, есть существенная разница между этими двумя величинами.

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

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

Ясно, что многие результаты в задачах Борсука и Грюнбаума можно получать аналогичными методами. В данной работе изучается проблема Грюнбаума с использованием методов, которые были уже успешно применены для изучения проблемы Борсука в статье [25].

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

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

В случае растущей размерности аналогичными задачами занимался А.М. Райгородский (см. [22], [31]    [34]).

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

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

Е = {{ a , b }| a e V, b EV, p( a , b ) = d}.

Далее назовем графом расстояний множества V с расстоянием в отрезке [l,r] граф G[/,_r](V), вершинами которого являются элементы множества V, а ребрами соединены точки на расстоянии из отрезка [Z, г]. Более формально, граф G[/,_r](V) есть пара, состоящая из множества вершин V и множества ребер

Е = {{ a , b }| a EV, b E V, p( a , b ) E [I, r]}.

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

В работе [25] были получены следующие результаты.

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

/(V) = X (Gdiamv (V)) 6 н + 1. Здесь х ~ это обычное хроматическое число графа.

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

/(V) = X (Gdiamv(V)) 6н +1.

С помощью аналогичных методов были получены новые результаты для проблемы Грюнбаума.

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

Теорема 2. Для любого н 6 7 и для всех V С {0,1}^п выполнено g(V ) 6 н + 1.

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

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

Упомянутый выше подход основан на построении алгоритма, который позволяет осуществить значительное сокращение перебора на множестве всех графов диаметров, которые нас интересуют. Сложность в том, что полный перебор требует порядка 10150 — 10250 операций, что необозримо. Нам удается этого избежать. В последующих разделах докажем теоремы 1—4, описав соответствующий алгоритм.

1.3.    Дальнейшая структура статьи

Оставшаяся часть работы состоит из разделов «Описание алгоритма» и «Работа программы».

В разделе «Описание алгоритма» излагается в подробностях алгоритм, с помощью которого мы доказываем гипотезу Грюнбаума в малых размерностях. Также приводится псевдокод основной функции, использованной в алгоритме. В этом же разделе по ходу описания сформулированы все леммы, на которых основаны производимые в алгоритме действия.

В разделе «Работа программы» будут приведены результаты запуска программы.

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

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

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

Если говорить совсем грубо, нам нужно перебрать все подмножества V‘ множества {0,1}п или все подмножества V‘ множества {—1, 0,1}п и для каждого из таких подмножеств проверить, что g(V‘) 6 н + 1 или что g(V‘) 6 н + 1. Разумеется, полный перебор здесь невозможен. Впоследствии, рассматривая так называемые отсечения (которые и помогут нам значительно сократить перебор), мы, в частности, убедимся в том, что не всегда следует пробегать V = {0,1}п ил и V = {—1, 0,1}п целиком: зачастую достаточно взять некоторое собственное подмножество У С V и только из него извлекать в свою очередь подмножества У‘. Поэтому ниже будем использовать обозначение У вм<'сто V.

Доказательства теорем и перебор мы будем вести для всех допустимых d Е [1, diamУ] отдельно. Для каждого d необходимо будет доказать, что для любого У ‘ СУ с diamУ‘ = d выполнено д(У ‘) 6 п + 1 ил и д(У ‘) 6 п + 1. Нетрудно заметить, что d² является целым числом.

Далее, извлечение У ‘ из У организуем как наращивание множества У ‘ путем последовательного добавления в строящееся множество одной вершины за другой. И иногда мы будем прерывать процесс за счет различных соображений, которые назовём отсечениями перебора. Так или иначе, это будут соображения, которые показывают, что при дальнейшем увеличении множества У ‘ проверяемое нами свойство д(У ‘) 6 п + 1 ил и д(У ‘) 6 п + 1 заведомо выполняется.

Напомним, что подграфом графа G = (У, Е ) называют такой граф G' = (У ',Е ‘), что У ‘ СУ

Е ‘ С {{n,v} Е Е ф Е У ‘, v Е У ‘}.

А индуцированным подграфом графа G = (У, Е ) (индуцированным на множество У ‘ С У) называют подграф, содержащий все ребра из Е, оба конца которых принадлежат У ‘, т.е. G[У ‘] = (У ‘,Е‘)

Е’ = {{n,v} Е Е ф Е У‘,v Е У ‘}.

Также граф G = ( У, Е ) называют пустым, если Е = 0.

Введем некоторые обозначения.

• •    С = п + 1 — максимальное количество шаров, в которые мы хотим поместить рассматриваемое множество;

• •    д(У) Д^ля сокращения записи будет об означать одно из двух значений д(У ) ил и д(У ) в зависимости от доказываемой теоремы;

• •    d~ диаметр рассматриваемых подмножеств У ‘ СУ;

• •    Ед = G[^₊₁,d_iam у ](У) ^— граф запретов. В этом графе ребрами соединены вершины, которые не могут одновременно входить во множество У ‘ С У. При упомянутом выше процессе наращивания множества У‘ мы будем следить за тем, чтобы очередная вершина не образовала ребро в графе запретов с какой-либо из уже выбранных вершин.

В новых обозначениях утверждение diam У‘ = d эквивалентно одновременному выполнению следующих двух условий:

• 1 ) Ед[У‘] — пустой граф:

• 2 ) Go [У‘] — не пустой граф.

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

Когда значение d будет предполагаться фиксированным, мы будем обозначать графы Go, и Ед просто как G и Е соответственно.

Мы уже знаем, что основная функция алгоритма занимается перебором всех подмножеств У ‘ С У. Как было сказано в начале параграфа 2.1, перебор производится путем последовательного добавления в строящееся множество одной вершины за другой. И при добавлении очередной вершины всякий раз нужно, естественно, рассматривать один из двух вариантов:

• 1)    добавить вершину в множество V‘;

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

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

Каждое отсечение будет выглядеть как некоторый отдельный модуль. Обязанностями этого модуля будут:

• 1)    обработка сигналов о совершаемых действиях, предпринимаемых перебором;

• 2)    сообщение перебору о необходимости продолжения;

• 3)    сообщение перебору о выполнении некоторых действий.

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

Кроме этого, модуль может запросить у перебора выполнение следующих действий:

• 1)    включить вершину г во множество V‘;

• 2)    не включать вершину г во множество V‘.

Каждый модуль может за один раз запросить множество таких действий.

Функция 1, которая практически полностью повторяет логику аналогичной функции в [25], будет выполнять перебор и исполнять роль менеджера между модулями отсечений.

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

• •    In — множество вершин, которые должны входить в V‘.

• •    Out — множество вершин, которые не должны входитв в V‘.

• •    Unknown — множество вершин, для которых еще не определено, в какое из множеств In ii.tii Out оіш попадут.

Функция 1. Основной перебор

Добавление во множество In.

7:    In ^ In U {г} 8:    Сообщить всем отсечениям из Cuts, что вершина г добавлена во множество In. 9:    if хотя бы одно отсечение сообщило о прекращении перебора then 10:       Перейти к рассмотрению следующего варианта. 11:    end if 12:    Поместить все действия, которые сообщили модули отсечений, в очередь Events. 13:    while Events = 0 do 14:       Выполнить действие, указанное в начале очереди. 15:       Удалить выполненное действие из очереди. 16:       Сообщить всем отсечениям из Cuts о совершенном действии. 17:       if хотя бы одно отсечение сообщило о прекращении перебора then 18:         Перейти к рассмотрению следующего варианта. 19:        end if 20:       Добавить все вновь сообщенные действия от модулей в очередь Eиen"ts. 21:    end while 22:    if не M ainBruteForce(F, C, Cuts, In, Out) then return 0 23:    end if

Добавление во множество Out выполняется аналогично.

Оба варианта либо были отсечены, либо при дальнейшем рассмотрении вернули 1, поэтому return 1

24:    end procedure

Приведем некоторые отсечения, которые с минимальными изменениями взяты из статьи [25].

2.3.    Отсечение пустоты подграфа Ғд

Отсечение следит за тем, чтобы в генерируемое множество не попало две смежные в графе Ғд вершины.

При получении информации о добавлении во множество новой вершины и отсечение проверяет, что в In нет вершин, смежных сив Ғд. Также отсечение сообщает, что все смежные с и вершины должны немедленно отправиться в Out.

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

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

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

Лемма 1. Пусти А С В С V и diam А = diam В, тогда д(А) 6 д(В).

Вершину будем называть потенциально из In, если она не принадлежит Out. Положим Potential = {и : и Е V \ Out}.

При поступлении информации о том, что вершина и добавляется в Out, отсечение проверяет, что и смежна в Ғд с вершиной потенциально из In. Если это условие не выполнено, то по окончании перебора во множество In будет возможно добавить вершину и, а следовательно, In не будет максимальным по включению. Поэтому продолжение перебора не требуется. Информация о том, что вершина добавляется в In, никак не используется.

Это отсечение (равно как и предыдущее) очень просто в реализации и почти не требует вычислительных ресурсов. Однако количество отсеченных ветвей вполне существенно.

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

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

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

Определение 1. Пусть, как и прежде, p(a, b ) — расстояние между точками а и Ь. Рассмотрим два множества точек V{ = { g i ,..., g _m} и V > = { h i ,..., h _m}. Если существует такая биекпия f : V{ < —> V2. что всегда p ( a, b ) = p(f ( a ) , f ( b )). то будем говорить, что V’ пзометріічпо Vm Отображение f назовём изометрией множеств V/ ii V2.

Определение 2. Будем называть / глобальной изометрией множества V, если она является изометрией для множества V на это же множество V.

Справедлива следующая очевидная лемма.

Лемма 2. Если / является глобальной изометрией множества V , переводящей V 1‘ С V в V 2 С V, то g(Vl_ ) = g( V ’).

Благодаря этому утверждению достаточно рассматривать только одно множество V‘ из каждого класса изометричных множеств. Ниже мы скажем, какое именно. Далее будем говорить только о глобальных изометриях множества Rn.

Определение 3. Введем лексикографический порядок на множестве всех подмножеств V‘ данного множества V. При этом элементы множества V мы считаем занумерованными, т.е. само множество V заранее упорядочено — например, лексикографически. Пусть, стало быть, V’ = { a _i, а ₂,..., а /} и V2 = { b i, b ₂,..., b _m} — подмножества множества V, причем a i <  а ₂< ... <  а / и b i <  b ₂< ... <  b_m. Будем говорить, что V/ <  V2,, если существует такой номер г, что a i = b i,..., а ^ = b j, a ^+i <  b ₊i ил и l <  m и a i = b i,..., а / <  b /.

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

Далее имеет место следующее простое утверждение.

Лемма 3. Пусть множества V i‘ , V 2 изометричны и V ^      <     П/.

Пусть V’     =     { b i , b ₂ ,..., b _m }. Рассмотрим произвольное множество

• V ₂" = { b _i , b ₂ ,..., b _m , b _m+_i ,..., b _m+t }, полученное в результате пополнения множества, V^. Тогда сутдствуст мноыссство V". которое изомстрично множеству V2’ и лексикографически меньше него.

Лемма 3 позволяет прекратить перебор, как только обнаружится, что текущее множе ство In лексикографически больше некоторого пзометрпчпого ему множества In ’.

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

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

Один из примеров биекции /, которая сохраняет расстояние, — это отражение. В следующих леммах, поясняющих, что мы имеем в виду под отражением, отдельно рассмотрим случаи V = {0,1}^п и V = {-1, 0,1}^п.

Лемма 4. Пусть а = ( ai,..., а_п), а ^ Е { 0 , 1 }. Пусть ж G R. Положим

{ d(0, ж ) = ж, d (1 , ж ) = 1 - ж.

Тогда отображение fa, переводят, ее каждый x =   ( жі,...,ж „ ), ж ^    Е    R, в

(d(ai, ж ₁) , ..., d(a_n, ж „)), является глобалиной изометрией Rⁿ и [0 , 1]^п.

Лемма 5. Пусти a = (щ,..., a_n), сц Е {0,1}. Пусти х Е R. Полосисим

{ d(0, х) = х, d(1, х) = —х.

Тогда отобрасисение fa, переводят, ее камсдый х = (хі, ...,х_п), Хг Е R, в (d(ai,xi), ..., d(a_n,x_n )), является глобалиной изометрией Rⁿ и [—1,1]^п.

В статье [25] приведены функции, которые позволяют определить наличие изометрии такого вида.

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

Имеет место следующая очевидная лемма.

Лемма 6. Пусти р = {р1,... ,р_п} ~ перестлановка чисел от 1 д on их = (х1,..., х_п), х_г Е {0,1}. Тогда от обращение f_p(x) = (х_Р1,...,х_Рп) является глобальной изометрией для любого множества S , где S С Rⁿ.

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

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

Целью перебора является проверка всех подмножеств диаметра d множества У на вло-жимость в С шаров диаметра d. При некоторых принятых решениях в переборе точки из множества FoZentiaZ уже можно поместить в необходимое количество шаров. Если такое произошло, то продолжение перебора не требуется.

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

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

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

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

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

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

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

На каждой стадии алгоритма необходимо поместить р точек в к шаров. Перебираем все шары, которые покрывают как минимум [р/к], и переходим к размещению оставшихся точек в к — 1 шар.

Для ускорения этого алгоритма рассматривались не все шары с полуцелыми координатами, а только шары, которые содержат ровно d2 координат 2 для замкнутых шаров и d2 — 1 координат 2 для открытых шаров.

3. Работа программы

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

Вообще говоря, программа корректно работает для любых размерностей, однако количество вариантов растет сверхэкспоненциально с ростом размерности. Поэтому разумного времени работы при текущих отсечениях удалось добиться только для размерностей, указанных в теоремах 1-4.

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

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