авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Современная математика. Фундаментальные направления. Том 23 (2007). С. 147–164

УДК 514.11

ВОКРУГ ГИПОТЕЗЫ БОРСУКА

А. М. РАЙГОРОДСКИЙ

c 2007 г.

АННОТАЦИЯ. Обсуждается одна из центральных проблем комбинаторной геометрии, поставленная

К. Борсуком в 1933 г.

СОДЕРЖАНИЕ Введение........................................... 147 1. Обозначения и различные варианты формулировки проблемы............ 148 2. Универсальные покрышки................................. 148 3. Универсальные покрывающие системы.......................... 4. Усечения октаэдра..................................... 5. Сферические у.п.с. в размерности 3........................... 6. Множества постоянной ширины............................. 7. Покрытие множеств шарами................................ 8. Специальные классы множеств.............................. 9. Контрпримеры к гипотезе Борсука............................ 10. Проблемы Борсука, Грюнбаума и Нелсона—Эрдеша—Хадвигера для решетчатых многогранников и графов................................. 11. Хроматические числа конечных геометрических графов и связь между проблемами Борсука и Нелсона—Эрдеша—Хадвигера........................ Список литературы....................................... Введение. В настоящей работе речь пойдет об одной из центральных проблем комбинаторной гео метрии, а именно, о проблеме, поставленной К. Борсуком в 1933 г. Рассмотрим произвольное огра ниченное неодноточечное множество Rn и попытаемся представить его в виде = 1 · · · f, где каждое множество i имеет диаметр, строго меньший диаметра. Определим f () как мини мальное число f, при котором упомянутое представление существует. Иными словами, мы стре мимся разбить фиксированное нами множество на минимальное число частей меньшего диаметра.

Положим f (n) = max f (). Здесь максимум берется по всем Rn, обладающим указанными выше свойствами. Понятно, что величина f (n) определена корректно, хотя, вообще говоря, она может оказаться равной бесконечности. По сути же, f (n) есть минимальное количество частей меньшего диаметра, на которые разбивается произвольное ограниченное неодноточечное мно жество в евклидовом пространстве размерности n.

Мы только что сказали, что, в принципе, ничто не мешает величине f (n) обратиться в беско нечность. Однако довольно легко понять (и позже мы обсудим это), что f (n) ограничена. Более того, различные соображения наводят на мысль, что f (n) = n + 1. Эта мысль впервые как раз и пришла в голову Борсуку, который в [56] задал вопрос: верно ли, что всякое ограниченное множество в Rn допускает разбиение на n + 1 частей меньшего диаметра? Хотя сам Борсук и был весьма осторожен, его вопрос скоро стали называть гипотезой Борсука, и все, кто этой «ги потезой» занимался, верили в ее справедливость. С одной стороны, было много подтверждающих гипотезу соображений, а с другой стороны, слишком уж было заманчиво доказать столь краси вый факт: топологам бы, например, это дало альтернативное определение размерности множества.

Работа выполнена при поддержке гранта Президента России МК-3130.2004.1, гранта поддержки Ведущих научных школ НШ-136.2003.1 и гранта ИНТАС 03-51-5070.

c 2007 РУДН 148 А. М. РАЙГОРОДСКИЙ В результате гипотеза Борсука стала невероятно популярной, и в разное время ей занимались крупнейшие специалисты в дискретной геометрии, геометрии чисел, топологии, комбинаторике и пр. Были созданы многочисленные нетривиальные методы решения проблемы, а также найде ны неожиданные связи с другими задачами комбинаторики и геометрии. Это позволяет говорить о значительной роли, которую проблема Борсука сыграла в процессе становления современной дискретно-геометрической науки. В данной статье мы последовательно расскажем о тех методах и результатах, которые возникли в связи с проблемой. Отметим лишь, что с историей гипотезы Борсука можно также ознакомиться по работам [2, 22, 54, 76, 106].

1. Обозначения и различные варианты формулировки проблемы. Прежде чем переходить к изложению истории вопроса, необходимо договориться о некоторых обозначениях, а также лучше осознать, в чем на самом деле вопрос состоит. Итак, через diam мы будем обозначать диаметр множества, т.е. величину, равную sup |x y|, где |x y| — евклидово расстояние между векто x,y рами x, y Rn. |M| будет обозначать мощность множества M. Давая определение диаметра, мы, конечно, не зря стали брать именно супремум расстояний, а не их максимум. Тем не менее понят но, что величина f (n) не изменится, коль скоро вместо абсолютно произвольных множеств мы с самого начала будем рассматривать только замкнутые. В то же время можно предположить, что у нас всякое выпукло: если это не так, то следует взять выпуклую оболочку, и дальше проблем не будет. Еще разумно, скажем, считать, что diam = 1. Таким образом, f (n) — это минимальное число частей меньшего диаметра, на которые разбивается любое компактное выпуклое множество диаметра 1 в пространстве. Наконец, нетрудно убедиться в том, что вовсе не обязательно раз бивать на «меньшие» части: если мы будем искать оптимальное покрытие множествами меньшего диаметра, то от этого опять-таки ничего не изменится.



2. Универсальные покрышки. Самая первая и самая естественная идея о том, как подступиться к проблеме Борсука, заложена в следующем определении.

Определение 1. Множество U Rn называется универсальной покрышкой для множеств диа метра 1 в пространстве, если для любого Rn, diam = 1, найдется такое движение, что (U ). Иными словами, посредством «жестких копий» множества U можно покрыть произ вольное Rn, имеющее единичный диаметр.

Коль скоро какая-нибудь универсальная покрышка U найдена, каждое множество в Rn разби вать уже не нужно. Достаточно разбить U на минимальное число частей диаметра 1, и все будет в порядке. В предыдущей фразе мы, однако же, намеренно сказали «диаметра 1», а не «меньшего диаметра». Дело в том, что покрышка не обязана сама иметь диаметр 1, так что даже все Rn мо жет служить тривиальным примером покрышки. Разумеется, от такой покрышки проку не будет, и основное искусство состоит, стало быть, в отыскании такого U, которое как можно плотнее «об легает» попадающие в него множества. На первый взгляд, кажется даже, что шансов получить на данном пути хороший результат мало. Однако интуиция не совсем права: многие нетривиальные, а подчас и неулучшаемые факты относительно f (n) основаны именно на построении универсальных покрышек.

По-видимому, проще всего понять, что универсальной покрышкой в любой размерности заведомо является единичный куб — например, куб [0, 1]n. Диаметр такого куба равен n, что гораздо n больше единицы. Тем не менее этот куб разбивается на (c n), c 0, частей надлежащего (c n)n. Куб, очевидно, слишком «угловат», диаметра, и, стало быть, во всяком случае f (n) захватывает много лишнего пространства, и ограничиваться его рассмотрением, понятно, не стоит.

Следующее по своей простоте и изученности множество — это шар. Классическая теорема Х. Юнга (см. [88]) говорит, что любое множество диаметра 1 в Rn вкладывается в шар ради уса n/(2n + 1). Опять-таки шар Юнга имеет диаметр, величина которого с ростом размерности приближается к 2, и все же ясно, что n взаимно перпендикулярных («координатных») гипер плоскостей, проходящих через центр шара, разбивают его на 2n частей диаметра 1. Экспонента значительно меньше, чем (c n)n, но и от нее до гипотетической линейной функции n + 1 далеко.

Шар удается подправить, дабы слегка уточнить оценку, вытекающую непосредственно из тео ремы Юнга. А именно, нужно заметить, что если множество покрыто шаром, то его всегда можно ВОКРУГ ГИПОТЕЗЫ БОРСУКА так «пошевелить» с помощью движения, чтобы хотя бы одна его точка попала на границу шара.

Тогда множество не выйдет также и за пределы шара с центром в найденной точке и радиу сом 1. Ясно, что вид полученной покрышки (пересечение двух шаров) не зависит от того, в какую конкретно часть сферы попала точка «подвинутого» множества, и все в порядке. Пересечение упомянутых шаров разбивается на 2n1 + 1 частей диаметра, меньшего единицы, и это уже не столь существенное продвижение. Однако позже мы увидим, что даже оно оправдано. Заметим, что последняя покрышка была предложена в 1982 г. М. Лассаком (см. [96]).

К сожалению, в «растущей размерности» покрышки, как мы видим, не совсем эффективны.

Впрочем, и то, что мы о них уже знаем, не так плохо. Гораздо сильнее оказываюся приложения метода к малым размерностям — n = 1, 2, 3. На них-то мы сейчас подробно и остановимся.

Пусть для начала n = 1. Тогда все совсем легко. Действительно, на роль универсальной по крышки вполне подойдет отрезок длины 1, который, между прочим, даже диаметр имеет тот же, что и множества, призванные быть покрытыми им. Разумеется, отрезок разбивается на n + 1 = части диаметра 1, и, стало быть, гипотеза Борсука на прямой верна. В сущности, верен еще более сильный результат. Положим diam i (0, 1], n = sup inf max Rn 1,...,n+1 i=1,...,n+ где точная верхняя грань берется по всем n-мерным множествам диаметра 1, а точная нижняя грань — по всем разбиениям этих множеств на гипотетическое число частей (возможно, впрочем, имеющих тот же диаметр 1, если вдруг гипотеза неверна). Иными словами, величина n отвечает за экономность разбиения наихудшего множества на части меньшего диаметра. Если гипотеза имеет место, то заведомо n 1, и, скорее всего, эта величина строго меньше единицы (не следует забывать, что мы работаем с супремумом). Однако при n = 1 все гораздо лучше: предложенная нами покрышка — отрезок — показывает, что 1 = 1/2, так что здесь мы не только проблему Борсука за счет универсальной покрышки решаем, но и даем в придачу точную оценку на степень «экономности» решения проблемы.

При n = 2 сложность построения покрышек значительно возрастает. Тем не менее еще в 1929 г.

Й. Пал доказал, что всякое множество диаметра 1 на плоскости может быть вложено в пра вильный шестиугольник, у которого расстояние между параллельными сторонами равно единице (см. [102]). Зная об этом, Борсук попросту предъявил разбиение покрышки Пала на три части диаметра 3/2 = 0,866... и, тем самым, в размерности 2 его гипотеза также подтвердилась.

Опять-таки, если рассмотреть на плоскости круг радиуса 1/2, то нетрудно убедиться в том, что, как на три части ни разбивай, а все равно диаметр хотя бы одной части будет больше или ра его вен 3/2 = 0,866... (оптимальное разбиение похоже на значок Мерседеса: в круге проводятся три радиуса так, чтобы угол между любыми двумя из них был равен 120 градусов;

соответствующие секторы суть нужные нам части). Следовательно, 2 = 3/2 = 0,866..., и максимально точный результат в двумерной проблеме получен. Заметим, что с плоскими покрышками связано множе ство интересных задач: так, например, никто до сих пор не знает, как устроена универсальная покрышка минимальной площади в R2 (см. [81]).

Хотя в размерности 3 гипотеза Борсука была впервые доказана в 1955 году Х. Эгглстоном (см. [63]), который использовал неэлементарный подход и, в частности, никаких эффективных оценок на 3 не получил, универсальные покрышки и здесь не замедлили появиться. В 1953 г., за два года до опубликования работы Эгглстона, Д. Гэйл построил следующую покрышку в R (см. [72]). Пусть O — это октаэдр, у которого в прямоугольной системе координат Oxyz вершины записываются так:

3 3 A=, 0, 0, B = 0,,0, C = 0, 0,, 2 2 3 3 A=, 0, 0, B = 0,, 0, C = 0, 0,.

2 2 Легко проверить, что расстояния между параллельными гранями этого октаэдра равны 1. Иными словами, O = conv{A, B, C, A, B, C }, где через conv мы обозначаем выпуклую оболочку (точеч ного) множества. Легко видеть, что покрышка Гэйла — октаэдр O — напрямую обобщает покрышку 150 А. М. РАЙГОРОДСКИЙ Пала, и, собственно, доказательство Гэйла мало отличается от паловского (см. [2, 54, 106]). Все бы хорошо, да беда в том, что октаэдр Гэйла не только имеет диаметр 1, но к тому же и на четыре части диаметра 1 никакими силами не разбивается. Одновременно и независимо (в году) А. Хеппеш (см. [84]) и Б. Грюнбаум (см. [75]) придумали способ улучшить гэйловскую покрышку. В самом деле, рассмотрим шесть плоскостей, каждая из которых параллельна одному из трех центральных сечений октаэдра O координатными плоскостями и проходит на расстоянии 1/2 с той или иной стороны от своего сечения. Поскольку любое покрытое октаэдром множество изначально имеет диаметр 1, его точки не могут оказаться сразу по обе стороны от любой из полос, образованных парами параллельных плоскостей. Скажем, если имеются точки со стороны вершины A, то со стороны вершины A точек не будет, и наоборот;

то же самое верно для B, B, C, C. В какой бы ситуации мы ни оказались, действовать надо одним и тем же способом, и в результате без ограничения общности можно считать, что универсальной покрышкой является октаэдр, от которого указанными плоскостями отсечены три пирамидальные «шапочки» с верши нами в A, B, C (т.е. секущие плоскости попарно перпендикулярны). Идея, стало быть, прозрачна, и все упирается отныне в разбиение усеченного октаэдра. Это снова искусство, и тут Грюнбаум оказался изобретательнее Хеппеша: из его манипуляций вытекала оценка 6129030 937419 3 = 0,9887..., 1518 в то время как у Хеппеша получалось лишь 9+4 3 = 0,99775...

(см. [2]).

Размерность 3 — это первая размерность, в которой покрышки не дают максимально точный результат. Дело в том, что самая лучшая известная нижняя оценка на 3 есть 3+ 3 = 0,888..., и возникает она за счет рассмотрения единичного шара. Правда, неравенство Грюнбаума было усилено в 1997 г. В. В. Макеевым и Л. Евдокимовым (см. [14, 15]). Первый показал, что в ка честве трехмерной универсальной покрышки можно взять ромбододекаэдр, расстояние между па раллельными гранями которого равно 1, и более того, этот ромбододекаэдр не перестанет быть покрышкой, если от него отсечь «шапочки» точно так же, как это только что было сделано для октаэдра. Второй с помощью компьютера осуществил разбиение макеевской покрышки на четыре части диаметра 0,98, что на восемьдесят семь десятитысячных лучше прежней оценки. Все равно, конечно, «в масштабах единицы» зазор между числами 0,888 и 0,98 велик, и пафос работы Макее ва по большому счету не в уточнении третьего знака. Просто само доказательство того факта, что ромбододекаэдр — покрышка, весьма нетривиально и требует привлечения тонких топологических методов.

В размерности 3 с точки зрения гипотезы Борсука лучших покрышек никто пока не придумал.

Хуже того, в размерности 4 самым точным так и остается результат Лассака f (4) 241 +1 = 9, и, значит, в R4 гипотеза Борсука не доказана. Забегая вперед, скажем, что она там и не опровергнута, хотя мы верим в ее справедливость там, и кое-какие соображения на сей счет мы приведем в следующем разделе.

Отметим напоследок, что в размерности 3 существует огромное количество покрышек, пред ставляющих самостоятельный интерес, и узнать о них можно, например, по статьям [13, 119].

3. Универсальные покрывающие системы. Универсальные покрышки, о которых шла речь в предыдущем разделе, весьма полезны, но их можно обобщить, и в результате возникнет новый важный объект, называемый универсальной покрывающей системой (у.п.с.). Дело в том, что вместо одного множества U, жесткие копии которого покрывают любое множество диаметра 1 в Rn, разумно рассматривать целые семейства множеств {U }, предполагая, что для каждого Rn, diam = 1, найдутся такие множество U и движение, что (U ). Понятно, что теперь каждое отдельное U из у.п.с. покрышкой быть не обязано. С одной стороны, круг наших возможностей ВОКРУГ ГИПОТЕЗЫ БОРСУКА весьма расширился, ведь свободы в выборе универсальных систем куда больше, чем в выборе покрышек: одни множества хорошо покрываются, условно говоря, кубом, другие — шаром и т. д.

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

4. Усечения октаэдра. Эта система, состоящая всего из двух множеств, была предложена ав тором статьи. Опишем ее простейший вариант. Пусть O — универсальная покрышка Гэйла из предыдущего раздела.

Построим многогранники 1 и 2, последовательно отсекая некоторые части от O. Чтобы по строить 1, возьмем плоскости 1, 1 и 1, где плоскость 1 параллельна плоскости, содержащей 1 2 3 точки B, B, C, C, т.е. плоскости Oyz, и лежит на расстоянии 0,5 от начала координат O с той же стороны, что и вершина A ;

плоскость 1 параллельна плоскости, содержащей точки B, B, A, A, т.е. плоскости Oxy, и лежит на расстоянии 0,5 от начала координат с той же стороны, что и C ;





а плоскость 1 параллельна последней координатной плоскости и лежит на расстоянии 0,475 от нее с той же стороны, что и B. Многогранник 1 получается из O путем отсечения прямоугольных пирамид с вершинами A, B и C плоскостями 1, 1 и 1.

1 2 Чтобы построить 2, нам понадобится шесть плоскостей. Их определение очень близко к опреде лению 1. Они тоже параллельны координатным плоскостям, но теперь они возникают «парами», i так что нам достаточно указать расстояния от них до O и установить вершины, которые будут отсекаться соответствующими плоскостями. Пусть 2, i = 1, 2, 3, отвечают вершинам A, B, C, а i расстояния для них равны 0,5. Пусть в то же время 2, i = 4, 5, 6, отвечают A, B, C, а расстояния i для них суть 0,525. Нетрудно проверить, что {1, 2 } — это у.п.с.

Оказывается, что и 1, и 2 допускают разбиение на четыре части диаметра 0,9842. Этот результат лучше грюнбаумского, но хуже макеевского. Однако он значительно элементарнее по следнего, так как для него не требуется сложная топология. Вместе с тем ничто не мешает при менить нам аналогичную технологию усечения к ромбододекаэдру, а на этом пути можно и до 0,97 добраться. Заметим, наконец, что описанные нами 1, 2 выбраны не вполне оценки оптимально, и к тому же они лишь суть примеры того, как можно действовать. В принципе, точно так же можно было бы выбирать и большее количество усеченных многогранников.

5. Сферические у.п.с. в размерности 3. Эти у.п.с. были также предложены автором в рабо те [37]. Введем сперва некоторые понятия. Пусть R3 имеет диаметр 1. Обозначим через r() радиус минимального шара, в который может быть вложено. Понятно, что за счет теоремы Юнга (см. [88]) 1/2 r() 3/8. Ввиду таких обозначений дальнейшие выкладки будут выглядеть прозрачнее.

Итак, (трехмерная, континуальная) у.п.с. строится в рамках следующей процедуры. Сперва фиксируется произвольное 1/2, 3/8, рассматривается шар B() радиуса и берется любая точка x1 B(). Через центр шара B() проводится плоскость, параллельная касательной плос кости в точке x1 и разделяющая поверхность шара на две (замкнутые) полусферы — «нижнюю»

(содержащую x1 ) и «верхнюю». В верхней полусфере выбирается произвольная точка x2, отстоя щая на расстояние 1 от точки x1. Если x1 и x2 диаметрально противоположны (что возможно лишь при = 1/2), то выбор точек считается завершенным. Иначе снова через центр шара B() проводится плоскость, которая на сей раз перпендикулярна кратчайшему отрезку, соединяющему центр и отрезок x1 x2, и которая по стандартному принципу делит поверхность шара на «верхнюю»

и «нижнюю» (замкнутые) полусферы. В верхней полусфере выбирается произвольная точка x3, отстоящая на расстояние 1 как от x1, так и от x2. Если точки x1, x2, x3 лежат в центральном сечении шара (что возможно, когда 1/3;

см. [88, теорема Юнга]), то их выбор опять-таки считается завершенным. В противном случае последняя, четвертая, точка x4 берется из верхней 152 А. М. РАЙГОРОДСКИЙ полусферы относительно плоскости, проходящей через центр B() и параллельной плоскости, ко торая порождена точками x1, x2, x3. При этом, как и прежде, попарные расстояния между точками x1, x2, x3, x4 не должны превышать 1.

Когда набор точек x1, x2,... построен, ему ставится в соответствие множество U(, x1, x2,... ), являющееся пересечением шара B() и двух, трех или четырех шаров радиуса 1 с центра ми в точках x1, x2,.... В конечном итоге у.п.с. формируется всеми возможными множествами U(, x1, x2,... ), получаемыми в рамках описанной выше процедуры. Нетрудно проверить, что, в самом деле, такая система множеств является универсальной покрывающей. (Для этого достаточно апеллировать к известной теореме Хелли (см. [4, 82, 83]).) Построенная у.п.с. выглядит довольно громоздкой, и, действительно, разбивать множества, при надлежащие ей, совсем непросто: требуется и ручной, и компьютерный счет. Последний был осу ществлен Ю. А. Калнишканом, и в результате были доказаны следующие утверждения.

3/8, то всякое множество R3, такое, что () =, может Теорема 1. Если 1/ быть разбито на четыре части, диаметры которых не превосходят величины (), причем () 0,888... при 1/2, и () 0,801... при 3/8. Более того, существуют та кие константы c1, c2, что в рамках предлагаемой процедуры разбиения стремление величины () к соответствующим пределам монотонно по [1/2, c1 ] и c2, 3/8.

Следствие 1. Если, например, R3 таково, что () [1/2, 0,53] 0,6, 3/8, то разбивается на четыре части диаметра 0,96.

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

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

Замечание 2. Множества, из которых состоит наша универсальная покрывающая система, яв ляются своего рода аналогами так называемых полиэдров Рело (см. [109]). Из теоремы видно, что классический полиэдр Рело поддается гораздо лучшему разбиению на четыре части меньше го диаметра, чем шар: предельная константа 0,801... 0,888... как раз этому полиэдру и отвечает.

6. Множества постоянной ширины. Множество Rn называется телом, если у него непу стая внутренность. Если — тело и точка x лежит на его границе, то опорная гиперплоскость к в точке x — это такая гиперплоскость, что целиком содержится в одном из полупространств, на которые она разбивает Rn. Если x — точка гладкости, то опорная гиперплоскость совпадает с касательной. Выпуклое тело имеет постоянную ширину, если расстояние между любыми двумя параллельными опорными гиперплоскостями к нему («ширина») постоянно. Выполнена (см. [64]) классическая теорема.

Теорема 2. Всякое множество диаметра 1 может быть покрыто некоторым выпуклым телом постоянной ширины и диаметра 1.

Таким образом, тела постоянной ширины тоже составляют бесконечную у.п.с., и проблема их экономного разбиения связана с совершенно новой для нас задачей освещения. Эту задачу в 1957 г. начал рассматривать Г. Хадвигер (см. [78, 79]). Состоит она в следующем. Пусть l — точка на единичной сфере с центром в начале координат. Будем говорить, что направление l освещает границу выпуклого тела в точке x, если существует прямая, параллельная вектору l, которая проходит через x, а затем попадает во внутренность. Обозначим через I() минимальное число направлений, которыми можно в совокупности осветить каждую точку границы. Положим i(n) = max I().

ВОКРУГ ГИПОТЕЗЫ БОРСУКА Легко заметить, что если — параллелепипед, то I() = 2n. Хадвигер предположил, что i(n) = 2n, т.е. что хуже параллелепипеда ни одно тело не освещается. Эта гипотеза доказана лишь в размерности 2 (см. [100]), но нам ее доказательство в общем случае и не нужно. Для нас более актуальны тела постоянной ширины. В 1988 г. О. Шрамм обосновал неравенство n I() 3/2 + o(1), верное, коль скоро выпукло и имеет постоянную ширину (см. [115]). Неравенство это весьма нетривиально. С другой стороны, в 1960 г. В. Г. Болтянский (см. [1, 2, 54]) показал, что если какое-либо освещено I направлениями, то оно же может быть покрыто I своими гомотетичными копиями с положительным коэффициентом гомотетии, строго меньшим единицы. Значит, для тел постоянной ширины выполнена оценка n f () 3/2 + o(1), а стало быть, n f (n) 3/2 + o(1).

Конечно, при малых n величина o(1) может быть очень большой, и потому результат Лассака 2n1 + 1 до опреленного момента все равно самый точный. Зато при n мы имеем f (n) содержательное усиление прежних оценок, которое, впрочем, от n + 1 весьма и весьма отличается.

7. Покрытие множеств шарами. Замечательным образом проблема Борсука оказалась связана с другой важной проблемой, лежащей на стыке комбинаторной геометрии и теории плотнейших упаковок шаров в пространстве. Речь идет о задаче, поставленной Б. Грюнбаумом в 50-е гг. XX ве ка. Эта задача состоит в нахождении величины g(n), равной минимальному числу шаров того же диаметра, которыми может быть покрыто произвольное ограниченное Rn. Говоря более по дробно, g(n) = max g(), где g() — это минимум среди всех g, для которых существует покрытие B1 · · · Bg с условием: каждое Bi — шар и diam Bi = diam.

По существу, проблема Грюнбаума возникла безотносительно проблемы Борсука. Дело в том, что широкий круг аналогичных задач и без того находился под пристальным вниманием спе циалистов. Тут можно упомянуть и всевозможные вопросы упаковок множеств в пространствах (см. [8, 40, 74] и пр.), и различные аспекты эргодической теории (см. [7, 9]). Однако сразу стало понятно, что проблемы тесно между собою связаны. Действительно, разбить шар диаметра 1 на n + 1 частей диаметра 1 ничего не стоит (см. [2]), а значит, f (n) (n + 1)g(n), что с ростом размерности могло бы дать неплохие результаты, коль скоро мы учитываем тот факт, что пока n ничего лучшего неравенства f (n) c + o(1), c 1, мы не знаем. Соответственно, проблема Грюнбаума получает дополнительный стимул к развитию. Заметим, правда, что рассчитывать на доказательство гипотезы при таком подходе, конечно, не приходится, да и мы увидим ниже, что между f (n) и g(n) есть качественное отличие. Однако кое-что доказать удается.

В частности, известно, что g(n) = n + 1 при n 3, и Грюнбаум даже взял на себя смелость предположить, что аналогичное равенство выполнено всегда — столь велика была вера в спра ведливость гипотезы Борсука, которая куда слабее. Упомянутые результаты для одномерного и двумерного случаев просты (см., например, [43, 98, 114]), а в размерности 3 еще более тонкий результат был получен П. Кацаровой-Карановой в 1967 г. (см. [92]): каждое множество диаметра в R3 покрывается четырьмя шарами диаметра 0,99983. Последний результат дает альтернативное доказательство гипотезы Борсука в трехмерном случае.

С ростом n задача становится особенно интересной. Так, в 1965 г. К. А. Роджерс установил нера n венство g(n) 2 + o(1) (см. [110]). Вернее, ни о проблеме Борсука, ни о проблеме Грюнбаума Роджерс в тот момент не думал. Просто он занимался покрытием сфер радиуса r сферическими шапочками радиуса и показал, что (r/ + o(1))n шапочек для этой цели хватит (оценка неулуч шаема с точностью до величины o(1)). Если вспомнить, что по теореме Юнга каждое множество диаметра 1 покрывается шаром диаметра 2, а затем юнговский шар покрыть шарами радиуса n 1/2, то станет понятно, почему, говоря об оценке g(n) 2 + o(1), мы ссылаемся на Роджерса.

Любопытно, что специалисты, занимавшиеся проблемами Борсука и Грюнбаума непосредственно, 154 А. М. РАЙГОРОДСКИЙ о результате Роджерса узнали с опозданием года на три, так что Л. Данцер даже успел сформули ровать (но не опубликовать) некое экспоненциальное неравенство для g(n), которое было слабее роджерсовского (см. [2, 54]).

Больше подобных проколов не было, и дальнейшие результаты были осознанно направлены на решение задач Борсука и Грюнбаума. Совсем нетривиальной является оценка, предложенная Ж. Бургейном и Й. Линденштрауссом в 1991 г. (см. [57]):

n g(n) 3/2 + o(1).

Поразительно, но факт: как бы нетривиален ни был упомянутый результат (он опирается на изо периметрические неравенства и усреднение по ортогональной группе), он в точности повторяет (с точки зрения проблемы Борсука) оценку Шрамма, полученную, казалось бы, на совершенно ином пути (задача освещения).

Полезно также отметить, что гипотеза Грюнбаума оказалась неверна. Ее опровергли очень бы стро: в 1963 г. Данцер доказал оценку g(n) 1,003n (см. [58]), а в 1991 г. Бургейн и Линденштраусс получили неравенство g(n) 1,067n, используя классические результаты Р. Ранкина (см. [107]), Г. А. Кабатянского и В. И. Левенштейна об упаковках шаров (см. [6, 57]). Таким образом, далеко в проблеме Борсука и на этом пути не продвинуться, хотя константу в основании экспоненты улучшить, вероятно, удастся (см. п. 8).

8. Специальные классы множеств. В предыдущих разделах мы изложили многочисленные об щие подходы к решению проблемы Борсука, и это, в частности, вовлекло в орбиту наших исследо ваний несколько других классических задач. Вместе с тем разумно посмотреть, верна ли гипотеза Борсука для каких-нибудь множеств специального вида. Конечно, в голову сразу приходят мно гогранники или, что почти то же самое, конечные точечные конфигурации в пространстве. Еще в 1965 г. в книге [2] ее авторы высказывали предположение, что разобраться с многогранниками проще, чем с множествами произвольного вида (пускай даже эти множества выпуклы, компактны и имеют постоянную ширину). Позже мы увидим, как далеки от истины подобные идеи. Однако на первый взгляд они вполне естественны, и, действительно, если не в произвольной ситуации, то во многих особых интересные результаты получить удается.

Во-первых, детально изучены многоугольники в размерности 2 и многогранники в размерно сти 3. Разумеется, гипотеза Борсука верна и для них, коль скоро мы знаем, что f (n) = n + при n 3. Тем не менее, для конечных систем точек и их выпуклых оболочек на плоскости и в трехмерном случае все гораздо проще: никаких универсальных покрышек строить не приходится, и элементарной комбинаторики вполне достаточно. При n = 2 соответствующий факт установил П. Эрдеш в 1946 г. (см. [65]), а при n = 3 — А. Хеппеш и П. Ревес в 1956 г. (см. [85]). Беда в том, что эти факты имеют лишь относительную ценность;

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

Собственно, о многогранниках как таковых мы здесь больше не скажем. Мы вернемся к ним в п. 8. В следующем классе, они, впрочем, тоже имеются. Речь идет о классе центрально симметричных множеств, для элементов которого гипотеза Борсука была подтверждена А. С. Ри слингом (см. [39]). Вообще, симметрия оказалась весьма полезной для реализации разбиений на n+1 часть меньшего диаметра, и в 1971 г. К. А. Роджерс показал, что для всякого Rn, которое инвариантно относительно действия группы преобразований, оставляющих на месте правильный n-мерный симплекс, f () n+1 (см. [111]). Интересно отметить, что сам Роджерс тщетно пытался опровергнуть гипотезу, но в результате только доказал ее для упомянутых множеств.

В 70-е годы появились первые сомнения в правильности борсуковского предположения. Скепти ческие взгляды высказывали, помимо Роджерса, П. Эрдеш (см. [66]) и Д. Ларман (см. [93, 112]).

Так, Ларман стал рассматривать совсем простые множества, а именно, конечные множества точек, в которых реализуется всего два различных расстояния — диаметр и нечто меньшее. Понятно, что такие множества (они называются двухдистанционными) не могут быть слишком большими, и кажется, что они и устроены несложно: либо удастся легко доказать гипотезу, либо столь же лег ко ее удастся опровергнуть. Поразительно, но до сих пор никто не знает, как правильно оценить f (), коль скоро двухдистанционно.

ВОКРУГ ГИПОТЕЗЫ БОРСУКА Мы уже говорили (см. п. 7 о покрытии шарами), что ничего не стоит разбить шар на n + 1 часть меньшего диаметра. В 1946 г. Г. Хадвигер заметил (см. [2, 77]), что этот факт влечет выполнение аналогичного свойства и для тел с гладкой границей (один раз непрерывно дифференцируемой).

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

однако сделать этого не удается. Проблема Борсука в некотором роде «нестабильна».

Существуют и другие классы множеств, для которых гипотеза верна или хотя бы оценки мини мального числа частей меньшего диаметра лучше общих. Одни из этих классов чересчур специаль ны, и мы на них не останавливаемся, ссылаясь на [54], где о них говорится. Другие естественным образом появятся в конце статьи. В завершение раздела скажем несколько слов о нижних оценках для f (n). Первое, что приходит в голову, — рассмотреть правильный n-мерный симплекс. Прин цип Дирихле дает для него неравенство f () n + 1, но при этом, конечно, f () n + 1. Стало быть, заведомо f (n) n+1. То же самое можно доказать с помощью изучения шара (см. [2,12,55]) и даже произвольного множества постоянной ширины (см. [97]). В конечном счете мы получаем еще одну мотивировку для гипотезы Борсука.

9. Контрпримеры к гипотезе Борсука. В итоге Роджерс, Ларман, Эрдеш и прочие немного численные скептики оказались правы. В 1993 г., ровно через 60 лет после своей публикации, гипотеза Борсука была опровергнута. Дж. Кан и Г. Калаи в кратком сообщении [89] построили контрпримеры в размерностях n 2015 и доказали, что n f (n) 1,203... + o(1).

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

Красивая комбинаторная техника, позволившая опровергнуть гипотезу, возникла в связи с еще одной классической задачей комбинаторной геометрии — задачей Нелсона—Эрдеша—Хадвигера о раскрасках метрических пространств. Речь идет о минимальном числе ((X, ), a) цветов, в ко торые можно так раскрасить метрическое пространство (X, ), чтобы между точками x, y одного цвета не могло быть фиксированного расстояния a 0 ((x, y) = a). На самом деле, пробле ма Нелсона—Эрдеша—Хадвигера была поставлена в 50-х гг. XX в. как раз для пространства Rn (см. [22, 80, 116, 117]), где значение a никакой роли не играет, но в 1976 г. М. Бенда и М. Перлес предложили рассматривать ее в максимально общем контексте (см. [51]).

Для развития дискретной науки проблема Нелсона—Эрдеша—Хадвигера значила почти так же много, как и проблема Борсука. Мы не станем излагать здесь подробности ее истории, так как это увело бы нас слишком далеко. Мы сошлемся на работы [22, 116, 117]. Впрочем, некоторые результаты мы чуть позже приведем.

Очень важно для нас, что проблему Нелсона—Эрдеша—Хадвигера можно перевести на язык теории графов. Действительно, величина ((X, ), a) есть ничто иное как хроматическое число (вообще говоря, бесконечного) графа G = G((X, ), a) = (V, E), где V = X, а E = (x, y) V V : (x, y) = a ;

по этой причине ее, кстати, называют хроматическим числом метрического пространства (X, ) по отношению к критическому (запрещенному) расстоянию a. Понятно, что если мы хотим отыскать нижние оценки для такого хроматического числа, нам достаточно посмотреть на хрома тические числа конечных подграфов графа G. Интересно отметить, что, более того, ((X, ), a) = (G) = max (G), G где максимум берется по всем конечным подграфам графа G (их принято называть конечными графами расстояний), причем предполагается, что хроматическое число ((X, ), a) конечно, а 156 А. М. РАЙГОРОДСКИЙ аксиома выбора выполнена (см. [59]). Далее, следует применить практически очевидное соображе ние, состоящее в том, что, коль скоро граф G = (V, E) конечен, его хроматическое число (G) не может быть меньше, чем |V |/(G), где (G) — это число независимости графа (см. [5, 44]). Лю бопытно, что приведенная сейчас оценка «в среднем», несмотря на свою крайнюю простоту, точна.

Легче всего это понять, рассматривая случайные графы (см. [49, 52, 53]). И наконец, появляется нетривиальность: а именно, отныне весь вопрос в том, как правильно оценить сверху (G). Иногда это сделать не сложно, но тогда оказывается, что мощность V мала и говорить о достаточно боль шом значении хроматического числа не приходится. Иногда это сделать весьма и весьма трудно.

Довольно скоро стало понятно, какого сорта должны быть «геометрические» множества вершин, дабы работать с ними можно было, апеллируя к активно в то же время изучавшейся технике, связанной с экстремальными задачами теории гиперграфов и их обобщений. Безусловно, мы гово рим в основном о наиболее близкой нам ситуации, когда (X, ) — это евклидово пространство или, чуть более общо, пространство (X, lp ), где X Rn, Qn (Qn — множество всех рациональных векторов в Rn ), а lp, 1 p, — обычная гельдерова метрика.

Итак, сперва оказалось возможным обсуждать числа независимости и хроматические числа графов G = (V, E), у которых V = x = (x1,..., xn ) : xi {0, 1}, |{i : xi = 1}| = t, E = (x, y) V V : (x, y) = a.

Здесь величины t и a 0 фиксируются почти произвольно, и по ним можно оптимизировать возни кающие оценки. Впрочем, до 1981 г. подобная оптимизация оставалась лишь несбыточной мечтой:

реально за счет нехватки соответствующей техники удавалось добиваться результатов только для t = 3, 5 и некоторых других специальных значений. Прорыв был осуществлен П. Франклом и Р. М. Уилсоном, которые сумели разработать в [70] мощный линейно-алгебраический метод в комбинаторике, дававший во многих общих случаях точные верхние оценки на (G). В частно сти, именно Франкл и Уилсон доказали в упомянутой статье удивительное, на первый взгляд утверждение.

Утверждение 1. Пусть n = 4p, где p — простое число. Если совокупность 2p-элементных подмножеств некоторого n-элементного множества такова, что никакие два множества в p ней не пересекаются по p общим элементам, то ее мощность не превосходит 2Cn.

Утверждение удивительно хотя бы потому, что из него вытекает экспоненциальное понижение мощности совокупности, элементы которой удовлетворяют всего одному запрету на мощность p 2p пересечения: если бы запрета не было, то вместо Cn мы бы имели Cn, что гораздо больше.

p С другой стороны, утверждение фактически дает оценку (G) 2Cn для G, у которого t = 2p, a = 2p (очевидно, что совокупности множеств и (0, 1)-векторы могут быть отождествлены, причем запрещенные пересечения перейдут в запрещенные расстояния и наоборот). Это позволило Франклу и Уилсону обосновать неравенство 2p Cn n n ((R, lp ), a) = 1,207... + o(1).

p 2Cn Заметим сначала, что упомянутая наука о пересечениях множеств относится к экстремальной теории гиперграфов. Эта теория получила значительный стимул к развитию благодаря работам П. Эрдеша и других авторов. Так, многие близкие вопросы возникали, например, в статьях [45,46, 60–62, 67–69, 94, 95, 108, 121]. Заметим, далее, что с 1981 по 1993 г. (год опровержения гипотезы Борсука) линейно-алгебраический метод неоднократно уточнялся (см. [48,50]). Заметим, наконец, что с проблемой Нелсона—Эрдеша—Хадвигера все опять-таки значительно лучше, чем с нашей основной задачей. Действительно, как теперь мы знаем, выполнены оценки n n n 1,203... + o(1) f (n) 3/2 + o(1) = 1,224... + o(1), и, хотя гипотеза опровергнута, зазор между неравенствами все равно чрезвычайно велик. В то же n время еще в 1972 г. Ларман и Роджерс показали, что ((Rn, l2 ), a) 3 + o(1) (см. [95]), так что ВОКРУГ ГИПОТЕЗЫ БОРСУКА хроматическое число заведомо растет экспоненциально, и речь может идти лишь об уточнении кон станты в основании экспоненты. А недавно Дж.-Х. Канг и З. Фюреди привели достаточно сильные экспоненциальные верхние оценки хроматического числа в произвольной метрике (см. [90]).

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

Дело в том, что и здесь нижние оценки основной величины следует получать с помощью конечных графов G = (V, E), у которых V Rn, а E = (x, y) V V : |x y| = l2 (x, y) = diam V (f (n) (G)). Разумеется, и тут в качестве V можно брать совокупность (0, 1)-векторов с фикси рованным количеством ненулевых координат. Тонкость в том, что запрещенное расстояние вовсе не произвольно: оно обязано совпадать с величиной диаметра, а как с этим бороться, извест но не было. Потребовалось 12 лет, чтобы в работе Кана и Калаи возник нетривиальный трюк, исправивший положение (см. [22, 47, 54, 89, 106]). На нем, однако, и экспоненциальность оценки теряется. Отметим, что графы, появляющиеся в связи с проблемой Борсука, называются графами диаметров.

Дальнейшие продвижения как в проблеме Борсука, так и в интересующей нас отныне пробле ме Нелсона—Эрдеша—Хадвигера основаны преимущественно на усложнении структуры множеств вершин графов расстояний и графов диаметров. Естественно, с увеличением сложности графов растет и сложность получения нижних оценок на их хроматические числа. Подавляющее большин ство соответствующих результатов и методов принадлежит автору. В серии работ [18, 20, 25, 31, 32] изучались графы G = (V, E) c V = x = (x1,..., xn ) : xi {b1,..., br }, |{i : xi = bj }| = tj.

Подразумевается, конечно, что t1 + · · · + tr = n, а b1,..., br — заданные наперед вещественные числа. В частности, при r = 2, b1 = 0, b2 = 1, t2 = t мы возвращаемся к ситуации, с которой имели дело Франкл, Уилсон, Кан и Калаи. Уже при r = 3, b1 = 0, b2 = 1, b3 = 1 требуются нетривиальные модификации линейно-алгебраического метода, и все равно проблемы с оценива нием чисел независимости полностью преодолеть не удается. Тем не менее, в упомянутых выше работах автором получены следующие не улучшенные до сих пор результаты.

n n ((Rn, l2 ), 1) ((Qn, l2 ), 1) 1,239... + o(1), 1,173... + o(1), n n ((Rn, l1 ), 1) ((Qn, l1 ), 1) 1,365... + o(1), 1,365... + o(1), n ((Qn, lp ), 1) 1 + (p) + o(1) ((p) 0), 2n n f (n) 2/ 3 + o(1) = 1,2255... + o(1).

Еще один любопытный аспект проблематики — это понижение размерности контрпримера. Число 2015 как-то совсем неудобоваримо, и хочется как-нибудь приблизить его к четырем-пяти. Здесь возникло целое соревнование, этапы которого мы сейчас приведем в таблице.

Автор, год n f (n) n Дж. Кан, Г. Калаи, 1993, [89] 2015 1,203 + o(1) n А. Нилли, 1994, [101] 946 1,203 + o(1) n Б. Вайссбах, Й. Грей, 1997, [73] 903 1,203 + o(1) n А. М. Райгородский, 1997, [17] 561 1,203 + o(1) n Б. Вайссбах, 2000, [120] 560 1,203 + o(1) А. Хинрихс, 2001, [86] 324 — О. Пихурко, 2002, [105] 323 — А. Хинрихс, Х. Рихтер, 2003, [87] 298 — Во-первых, из таблицы видно, какая упорная велась борьба за место в «общем зачете» (во втором столбце указана размерность, с которой гипотеза Борсука перестает быть верной). Во-вторых, в 158 А. М. РАЙГОРОДСКИЙ ней подчеркнуто, что при понижении размерности контрпримера оценка на f (n) существенных из менений не претерпевала — только o(1) менялось, а константа в основании экспоненты оставалась прежней (ср. приведенное выше неравенство автора). Сами конструкции вплоть до работы авто ра 1997 г. представляли собою все более и более хитрые совокупности (0, 1)-векторов;

в статьях Хинрихса и др. возникли интересные построения, основанные на минимальных векторах решетки Лича (см. [8]). Что происходит в размерностях 4 n 297, пока не известно. Мы предполагаем, что за счет (1, 0, 1)-векторов удастся опровергнуть гипотезу при n 136 (см. [22]).

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

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

10. Проблемы Борсука, Грюнбаума и Нелсона—Эрдеша—Хадвигера для решетчатых мно гогранников и графов. Этот раздел будет как бы продолжением п. 6, в котором мы изучали проблему Борсука в специальных случаях. Теперь речь пойдет о решетчатых многогранниках (многогранниках, вершины которых суть точки решетки) и связанных с ними графах диаметров и расстояний. Мотивировка для рассмотрения этих объектов была дана в конце предыдущего раздела. Сперва мы введем обозначения.

Зафиксируем произвольные вещественные числа b1,..., br, а также произвольные натуральные числа t1,..., tr, удовлетворяющие условию t1 + · · · + tr = n. Ясно, что r n. Определим F(b1,..., br ;

t1,..., tr ;

k;

n) (k R) как класс всех возможных совокупностей векторов F(b1,..., br ;

t1,..., tr ;

k;

n) = {v1,..., vs } Rn, для которых выполнены следующие свойства:

1 n (i) полагая vi = (vi,..., vi ), i = 1,..., s, имеем:

|{ = 1,..., n : vi = bj }| = tj для каждого i {1,..., s} и j {1,..., r}, (ii) diam F(b1,..., br ;

t1,..., tr ;

k;

n) = k.

Таким образом, F(b1,..., br ;

t1,..., tr ;

k;

n) — это класс всех совокупностей n-мерных векторов, имеющих для любого j {1,..., r} в точно сти tj координат, равных величине bj ;

сверх того, квадрат диаметра всякой такой совокупности совпадает с k. С одной стороны, корректность данного определения вытекает из соотношения t1 + · · · + tr = n. С другой стороны, понятно, что свойство (ii) накладывает дополнительные есте ственные ограничения на множества допустимых значений величин t1,..., tr, k.

Перейдем теперь от класса F(b1,..., br ;

t1,..., tr ;

k;

n) к классу O(b1,..., br ;

t1,..., tr ;

k;

n), беря в качестве элементов последнего выпуклые оболочки совокупностей векторов F(b1,..., br ;

t1,..., tr ;

k;

n) F(b1,..., br ;

t1,..., tr ;

k;

n) — многогранники (b1,..., br ;

t1,..., tr ;

k;

n).

На классе O(b1,..., br ;

t1,..., tr ;

k;

n) ВОКРУГ ГИПОТЕЗЫ БОРСУКА введем величины f (b1,..., br ;

t1,..., tr ;

k;

n), g(b1,..., br ;

t1,..., tr ;

k;

n), определяя первую из них как минимальное число частей меньшего диаметра, на которые может быть разбит каждый многогранник из класса, а вторую — как наименьшее число шаров того же диаметра, которыми покрывается всякий такой многогранник. Ясно, что величина f (b1,..., br ;

t1,..., tr ;

k;

n) отвечает проблеме Борсука, а величина g(b1,..., br ;

t1,..., tr ;

k;

n) — проблеме Грюнбаума.

Рассмотрим, наконец, граф G(b1,..., br ;

t1,..., tr ;

k;

n) = V (b1,..., br ;

t1,..., tr ;

k;

n), E(b1,..., br ;

t1,..., tr ;

k;

n), у которого множество вершин V (b1,..., br ;

t1,..., tr ;

k;

n) состоит из всех возможных n-мерных векторов, имеющих для каждого j {1,..., r} ровно tj координат, равных bj, а множество ребер E(b1,..., br ;

t1,..., tr ;

k;

n) отвечает множеству пар вершин, квадрат расстояния между которыми равен k. Понятно опять таки, что величина G(b1,..., br ;

t1,..., tr ;

k;

n) представляет собой конечный аналог величины ((Rn, l2 ), a).

Г. М. Циглер и др. подробно исследовали только что сформулированный вариант проблемы Борсука для случая (0, 1)-многогранников. Так, они доказали, что f (0, 1;

t1, t2 ;

k;

n) n + 1, коль скоро величины k, t1, t2 произвольны, а n 9 (см. [103,104,113,122,123]). Пафос результатов циглеровской группы состоит в том, что они подтверждают гипотезу Борсука в малых размерностях как раз для тех многогранников, с помощью которых при больших n она была опровергнута.

В очень специальных ситуациях величина G(b1,..., br ;

t1,..., tr ;

k;

n) также изучена Циглером и др. Кроме того, ей посвящена работа [99].

Однако все самые сильные верхние оценки величин f (b1,..., br ;

t1,..., tr ;

k;

n), g(b1,..., br ;

t1,..., tr ;

k;

n), G(b1,..., br ;

t1,..., tr ;

k;

n) при n принадлежат автору. Они получены в серии статей [21, 23, 24, 26, 28, 30, 38] за счет предложенного автором метода «покрытия с зацеплением», который опирается, в частности, на технику, связанную с задачами о системах общих представителей для совокупностей подмно жеств конечного множества (см. [3, 10, 11, 16, 19, 41, 42, 71, 91, 118]), и на нетривиальные обобщения теоремы Эрдеша—Ко—Радо из экстремальной теории гиперграфов (см. [45, 46, 62, 67, 68, 121]).

Мы не станем излагать здесь ни подробности метода, ни сами неравенства, полученные с его помощью. Они весьма многочисленны (зависят от соотношений между параметрами) и доволь но громоздки. Главное то, что они значительно уточняют оценки Шрамма (проблема Борсука), Бургейна—Линденштраусса (проблема Грюнбаума) и Лармана—Роджерса (проблема Нелсона— Эрдеша—Хадвигера).

160 А. М. РАЙГОРОДСКИЙ 11. Хроматические числа конечных геометрических графов и связь между проблемами Борсука и Нелсона—Эрдеша—Хадвигера. В пп. 7 и 8 мы говорили, что самые сильные из вестные нижние оценки хроматических чисел, а также величины f (n) получаются за счет рас смотрения конечных геометрических графов (графов расстояний и диаметров) вида G = (V, E), V = x = (x1,..., xn ) : xi {b1,..., br }, |{i : xi = bj }| = tj, E = (x, y) V V : (x, y) = a.

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

Недавно автор разработал новый метод «альтернирования», который помог ему в существенной мере исправить положение. Так, в работах [29,34,35] установлены новые нижние оценки на хрома тические числа конечных графов расстояний произвольного вида. Эти оценки опять-таки зависят от многочисленных параметров, и здесь мы их не приводим. Зато мы можем привести совершенно удивительное и неожиданное следствие метода, повлекшее условное уточнение оценок величин f (n) и ((Rn, l2 ), a).

n Теорема 3. Существует такое 0, что либо f (n), либо 1,2255... + + o(1) n ((Rn, l2 ), a) 1,239... + + o(1).

Эта теорема доказана в [27,36], и свидетельствует она о поразительной связи между двумя про блемами комбинаторной геометрии. Напоследок обсудим еще один аспект связи проблем. Пусть (n, a, d) — это минимальное число цветов, в которые можно так раскрасить произвольное множе ство диаметра d в Rn, чтобы между точками одного цвета не было расстояния a d. Ясно, что мы имеем непрерывную цепочку задач, на одном конце которой находится аналог задачи Борсука (a = d), а на другом — аналог задачи Нелсона—Эрдеша—Хадвигера (a 0). В [33] автор полу чил нетривиальные нижние оценки величины (n, a, d). Недавно некоторые из этих оценок были улучшены М. М. Китяевым.

СПИСОК ЛИТЕРАТУРЫ 1. Болтянский В. Г. Задача об освещении границы выпуклого тела// Изв. Молдавского филиала АН СССР. — 1960. — 76, № 10. — C. 77–84.

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

3. Глускин Е. Д. Экстремальные свойства ортогональных параллелепипедов и их приложение к геомет рии банаховых пространств// Мат. сб. — 1988. — 136, № 1. — C. 85–96.

4. Данцер Л., Грюнбаум Б., Кли В. Теорема Хелли. — М.: Мир, 1968.

5. Дистель Р. Теория графов. — Новосибирск: Инст. Мат., 2002.

6. Кабатянский Г. А., Левенштейн В. И. Оценки для упаковок на сфере и в пространстве// Проблемы передачи информации. — 1978. — 14. — C. 1–17.

7. Каток А. Б., Хассельблат Б. Введение в современную теорию динамических систем. — М.: Факто риал, 1999.

8. Конвей Дж., Слоэн Н. Упаковки шаров, решетки и группы. — М.: Мир, 1990.

9. Корнфельд И. П., Синай Я. Г., Фомин С. В. Эргодическая теория. — М.: Наука, 1980.

10. Кузюрин Н. Н. Асимптотическое исследование задачи о покрытии// Пробл. киберн. — 1980. — 37. — C. 19–56.

11. Леонтьев В.К. Верхние оценки -глубины (0, 1)-матриц// Мат. заметки. — 1974. — 15, № 3. — C. 421– 429.

12. Люстерник Л. А., Шнирельман Л. Г. Топологические методы в вариационных задачах. — М., 1930.

13. Макеев В. В. Универсальные покрышки и проекции тел постоянной ширины// Укр. геом. сб. — 1989. — 32. — C. 84–88.

ВОКРУГ ГИПОТЕЗЫ БОРСУКА 14. Макеев В. В. Аффинно-вписанные и аффинно-описанные многоугольники и многогранники// Зап.

науч. семин. ПОМИ. — 1996. — 231. — C. 286–298.

15. Макеев В. В. Об аффинных образах ромбододекаэдра, описанных вокруг трехмерного выпуклого тела// Зап. науч. семин. ПОМИ. — 1997. — 246. — C. 191–195.

16. Нечипорук Э. И. О топологических принципах самокорректирования// Пробл. киберн. — 1969. — 21. — C. 5–103.

17. Райгородский A. М. О размерности в проблеме Борсука// Усп. мат. наук. — 1997. — 52, № 6. — C. 181–182.

18. Райгородский А. М. Об одной оценке в проблеме Борсука// Усп. мат. наук. — 1999. — 54, № 2. — C. 185–186.

19. Райгородский А. М. Системы общих представителей// Фунд. прикл. мат. — 1999. — 5, № 3. — C. 851– 860.

20. Райгородский А. М. О хроматическом числе пространства// Усп. мат. наук. — 2000. — 55, № 2. — C. 147–148.

21. Райгородский А. М. Проблема Борсука для (0, 1)-многогранников и кросс-политопов// Докл. РАН. — 2000. — 371. — C. 600–603.

22. Райгородский А. М. Проблема Борсука и хроматические числа некоторых метрических пространств// Усп. мат. наук. — 2001. — 56, №. 1. — C. 107–146.

23. Райгородский А. М. Проблема Борсука для (0, 1)-многогранников и кросс-политопов// Докл. РАН. — 2002. — 384. — C. 593–597.

24. Райгородский А. М. Об одной задаче оптимального покрытия множеств шарами// Чебышевский сб. — 2002. — 3, № 2(4). — C. 100–106.

25. Райгородский А. М. Проблемы Борсука и Хадвигера и системы векторов с запретами на скалярные произведения// Усп. мат. наук. — 2002. — 57, № 3. — C. 159–160.

26. Райгородский А. М. Проблема Борсука для целочисленных многогранников// Мат. сб. — 2002. — 193, № 10. — C. 139–160.

27. Райгородский А. М. О нижних оценках для чисел Борсука и Хадвигера// Усп. мат. наук. — 2003. — 59, № 3. — C. 177–178.

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

29. Райгородский А. М. Проблема Эрдеша—Хадвигера и хроматические числа конечных геометрических графов// Докл. РАН. — 2003. — 392, № 3. — C. 313–317.

30. Райгородский А. М. Проблемы Борсука и Грюнбаума для решетчатых многогранников// Изв. РАН. — 2004. — 69, № 3. — C. 96–121.

31. Райгородский А. М. О хроматическом числе пространства с метрикой lq // Усп. мат. наук. — 2004. — 59, № 5. — C. 161–162.

32. Райгородский А. М. О хроматических числах метрических пространств// Чебышевский сб. — 2004. — 5, № 1(9). — C. 175–185.

33. Райгородский А. М. О связи между задачами Борсука и Нелсона—Эрдеша—Хадвигера// Усп. мат.

наук. — 2005. — 60.

34. Райгородский А. М. Проблема Эрдеша—Хадвигера и хроматические числа конечных геометрических графов// Мат. сб. — 2005. — 196, № 1.

35. Райгородский А. М. Хроматические числа метрических пространств// Тр. ин-та математики НАН Беларуси. — 2005.

36. Райгородский А. М. О числах Борсука и Эрдеша—Хадвигера// Мат. заметки. — 2005.

37. Райгородский А. М., Калнишкан Ю. А. О проблеме Борсука в R3 // Мат. заметки. — 2003. — 74, № 1. — C. 149–151.

38. Райгородский А. М., Чернов А. А. Проблема Борсука для некоторых классов многогранников// Чебышевский сб. — 2004. — 5, № 2(10). — C. 98–103.

39. Рислинг А. С. Проблема Борсука в трехмерных пространствах постоянной кривизны// Укр. геом.

сб. — 1971. — 11. — C. 78–83.

40. Роджерс К. Укладки и покрытия. — М.: Мир, 1968.

41. Сапоженко А. А. О сложности дизъюнктных нормальных форм, получаемых с помощью градиентного алгоритма// Дискретный анализ. — Новосибирск, 1972. — № 21. — C. 62–71.

42. Тараканов В. Е. Комбинаторные задачи и (0, 1)-матрицы. — М.: Наука, 1985.

43. Хадвигер Г., Дебруннер Г. Комбинаторная геометрия плоскости. — М.: Наука, 1965.

44. Харари Ф. Теория графов. — М.: Мир, 1973.

162 А. М. РАЙГОРОДСКИЙ 45. Ahlswede R., Khachatrian L. H. The complete nontrivial-intersection theorem for systems of finite sets// J. Combin. Theory. Ser. A. — 1996. — 76. — C. 121–138.

46. Ahlswede R., Khachatrian L. H. The complete intersection theorem for systems of finite sets// Eur. J.

Combin. — 1997. — 18. — C. 125–136.

47. Aigner M. and Ziegler G. M. Proofs from THE BOOK. — Berlin: Springer-Verlag, 1998.

48. Alon N., Babai L., and Suzuki H. Multilinear polynomials and Frankl–Ray–Chaudhuri–Wilson type intersection theorems// J. Combin. Theory. Ser. A. — 1991. — 58. — C. 165–180.

49. Alon N., Spencer J. The probabilistic method. — Wiley Interscience, 2000.

50. Babai L., Frankl P. Linear algebra methods in combinatorics, Part 1. — The Univ. of Chicago Press, 1992.

51. Benda M., Perles M. Colorings of metric spaces// Geombinatorics. — 2000. — 9. — C. 113–126.

52. Bollobas B. The chromatic number of random graphs// Combinatorica. — 1988. — 8. — C. 49–56.

53. Bollobas B. Random Graphs. — Cambridge Univ. Press, 2001.

54. Boltyanski V. G., Martini H. and Soltan P. S. Excursions into combinatorial geometry// Berlin– Heidelberg: Universitext, Springer-Verlag, 1997.

55. Borsuk K. Uber die Zerlegung einer Euklidischen n-dimensionalen Vollkugel in n Mengen// Verh. Int.

Math. Kongr. — Zurich, 1932. — 2. — C. 192.

56. Borsuk K. Drei S tze uber die n-dimensionale euklidische Sph re// Fund. Math. — 1933. — 20. — C. 177– a a 190.

57. Bourgain J., Lindenstrauss J. On covering a set in Rd by balls of the same diameter// Geometric Aspects of Functional Analysis (J. Lindenstrauss and V. Milman, eds.)/ Lect. Notes Math. — Berlin: Springer Verlag, 1991. — 1469. — C. 138–144.

58. Danzer L. On the kth diameter in E d and a problem of Grunbaum// Proc. Colloq. Convexity. — Copenhagen, 1965. — C. 41.

59. de Bruijn N. G., Erdos P. A colour problem for infinite graphs and a problem in the theory of relations// Proc. Koninkl. Nederl. Acad. Wet., Ser. A. — 1951. — 54, № 5. — C. 371–373.

60. Deza M., Erdos P., Frankl P. Intersection properties of systems of finite sets// Proc. London Math.

Soc. — 1978. — 36. — C. 369–384.

61. Deza M., Erdos P., Singhi N. M. Combinatorial problems on subsets and their intersections// Adv. Math., Suppl. Stud. — 1978. — 1. — C. 259–265.

62. Deza M., Frankl P. Erds—Ko—Rado theorem: 22 years later// SIAM J. Alg. Disc. Methods. — 1983. — o 4. — C. 419–431.

63. Eggleston H. G. Covering a three-dimensional set with sets of smaller diameter// J. London Math. Soc. — 1955. — 30. — C. 11–24.

64. Eggleston H. G. Convexity. — Cambridge Univ. Press., 1958.

65. Erdos P. On sets of distances of n points// Amer. Math. Monthly. — 1946. — 53. — C. 248–250.

66. Erdos P. My Scottish book «problems»/ The Scottish Book, Mathematics from the Scottish Caf e (R. D. Mauldin, ed.) — Birkh user, 1981. — C. 35–43.

a 67. Erdos P., Chao Ko, Rado R. Intersection theorems for systems of finite sets// J. Math. Oxford. — 1961. — 12(48).

68. Frankl P. The Erds—Ko—Rado theorem is true for n = ckt// Combinatorics. Coll. Math. Soc. J. Bolyai. — o 1978. — 18. — C. 365–375.

69. Frankl P. Extremal problems and coverings of the space// Eur. J. Combs. — 1980. — 1. — C. 101–106.

70. Frankl P., Wilson R. M. Intersection theorems with geometric consequences// Combinatorica. — 1981. — 1. — C. 357–368.

71. Furedi Z. Tur n’s type problems// Surv. Combinatorics/ Proc. 13th British Combin. Conference a (A. D. Keedwell, ed.). — London Math. Soc. Lect. Note Ser. — Cambridge Univ. Press, 1991. — 166. — C. 253–300.

72. Gale D. On inscribing n-dimensional sets in a regular n-simplex// Proc. Amer. Math. Soc. — 1953. — 4. — C. 222–225.

73. Grey J., Weissbach B. Ein weiteres Gegenbeispiel zur Borsukschen Vermutung. — Univ. Magdeburg, a Fakult t fur Mathematik, 1997. — Preprint 74. Gruber P. M., Lekkerkerker C. G. Geometry of numbers. — Amsterdam: North-Holland, 1987.

75. Grunbaum B. A simple proof of Borsuk’s conjecture in three dimensions// Proc. Cambridge Phil. Soc — 1957. — 53. — C. 776–778.

76. Grunbaum B. Borsuk’s problem and related questions// Proc. Symp. Pure Math. — 1963. — 7. — C. 271– 284.

ВОКРУГ ГИПОТЕЗЫ БОРСУКА 77. Hadwiger H. Uberdeckung einer Menge durch Mengen kleineren Durchmessers// Comm. Math. Helv. — 1945/46. — 18. — C. 73–75;

Mitteilung betreffend meine Note: Uberdeckung einer Menge durch Mengen kleineren Durchmessers// Comm. Math. Helv. — 1946/47. — 19. — C. 72–73.

78. Hadwiger H. Ungel ste Probleme № 20// Elem. Math. — 1957. — 12. — C. 121.

o 79. Hadwiger H. Ungel ste Probleme № 38// Elem. Math. — 1960. — 15. — C. 130–131.

o 80. Hadwiger H. Ungel ste Probleme № 40// Elem. Math. — 1961. — 16. — C. 103–104.

o 81. Hansen H. C. Small universal covers for sets of unit diameter// Geom. Dedic. — 1992. — 42. — C. 205–213.

82. Helly E. Uber Systeme abgeschlossener Mengen mit gemeinschaftlichen Punkten// Monatsh. Math. — 1930. — 37. — C. 281–302.

83. Helly E. On a collection of convex bodies with common points// Russ. Math. Surv. — 1936. — 2, № 2.

e ou e 84. Heppes A. T rbeli ponthalmazok feloszt sa kisebb atm rj r szhalmazok osszeg re// A magyar e a e tudom nyos akad mia. — 1957. — 7. — C. 413–416.

a e 85. Heppes A., Revesz P. Zum Borsukschen Zerteilungsproblem// Acta Math. Acad. Sci. Hung. — 1956. — 7. — C. 159–162.

86. Hinrichs A. Spherical codes and Borsuk’s conjecture// Discr. Math. — 2002. — 243. — C. 253–256.

87. Hinrichs A., Richter C. New sets with large Borsuk numbers// http://www.minet.uni jena.de/ hinrichs/paper/18/borsuk.pdf 88. Jung H. W. E. Uber die kleinste Kugel, die eine r umliche Figur einschliesst// J. Reine Angew. Math. — a 1901. — 123. — C. 241–257.

89. Kahn J., Kalai G. A counterexample to Borsuk’s conjecture// Bull. Amer. Math. Soc. (New Ser.) — 1993. — 29, № 1. — C. 60–62.

90. Kang J-H., Furedi Z. Distance graphs on Zn with l1 -norm// Theor. Comp. Sci. — 2004. — 319, №№ 1–3. — C. 357–366.

91. Katona G., Nemetz T., Simonovitz M. On a graph problem of Turan// Mat. Lapok. — 1964. — 15. — C. 228–238.

92. Katzarowa-Karanowa P. Uber ein euklidisch-geometrisches Problem von B. Grunbaum// Arch. Math. — 1967. — 18. — C. 663–672.

93. Larman D. Open problem 6// Convexity and graph theory (M. Rozenfeld and J. Zaks eds.)/ Ann. Discr.

Math. — Amsterdam–New York: North-Holland, 1984. — 20. — C. 336.

94. Larman D. G. A note on the realization of distances within sets in Euclidean space// Comm. Math.

Helv. — 1978. — 53. — C. 529–535.

95. Larman D. G., Rogers C. A. The realization of distances within sets in Euclidean space// Mathematika. — 1972. — 19. — C. 1–24.

96. Lassak M. An estimate concerning Borsuk’s partition problem// Bull. Acad. Polon. Sci. Ser. Math. — 1982. — 30. — C. 449–451.

97. Lenz H. Zur Zerlegung von Punktmengen in solche kleineren Durchmessers// Arch. Math. — 1955. — 6, № 5. — C. 413–416.

98. Lenz H. Uber die Bedeckung ebener Punktmengen durch solche kleineren Durchmessers// Arch. Math. — 1956. — 4. — C. 34–40.

99. Linial N., Meshulam R., and Tarsi M. Matroidal bijections between graphs// J. Combin. Theory, Ser. B. — 1988. — 45, № 1. — C. 31–44.

100. Martini H., Soltan V. Combinatorial problems on the illumination of convex bodies// Aequationes Math. — 1999. — 57. — C. 121–152.

101. Nilli A. On Borsuk’s problem// Contemp. Math. — 1994. — 178. — C. 209–210.

102. Pal J. Uber ein elementares Variationsproblem// Danske Videnskab. Selskab., Math.-Fys. Meddel. — 1920. — 3, № 2.

103. Payan C. On the chromatic number of cube — like graphs// Discr. Math. — 1992. — 103. — C. 271–277.

104. Petersen J. F rbung von Borsuk–Graphen in niedriger Dimension/ Diplomarbeit. — TU Berlin, 1998.

a 105. Pikhurko O. Borsuk’s conjecture fails in dimensions 321 and 322/ e-print: arXiv:math.

CO/0202112.

106. Raigorodskii A. M. The Borsuk partition problem: the seventieth anniversary// Math. Intelligencer. — 2004. — 26, № 4. — C. 4–12.

107. Rankin R. On the closest packing of spheres in n dimensions// Ann. Math. — 1947. — 48. — C. 1062–1081.

108. Ray-Chaudhuri D. K., Wilson R. M. On t-designs// Osaka J. Math. — 1975. — 12. — C. 735–744.

109. Reuleaux F. Lehrbuch der Kinematik I. Vieweg. — Braunschweig, 1875.

110. Rogers C. A. Covering a sphere with spheres// Mathematika. — 1963. — 10. — C. 157–164.

111. Rogers C. A. Symmetrical sets of constant width and their partitions// Mathematika. — 1971. — 18. — C. 105–111.

164 А. М. РАЙГОРОДСКИЙ 112. Rogers C. A. Some problems in the geometry of convex bodies// The Geometric Vein — The Coxeter Festschrift (C. Davis, B. Grunbaum, and F. A. Sherk, eds.) — New York: Springer-Verlag, 1981. — C. 279– 284.

113. Schiller F. Zur Berechnung und Absch tzung von F rbungszahlen und der -Funktion von Graphen/ a a Diplomarbeit. — TU Berlin, 1999.

114. Schopp J. Die Abdeckung ebener Bereiche mit konstanten Durchmessern durch drei Kreise von kleinerem Durchmesser/ Vortrag, gehalten auf der Geometrie-Tegen in Tihany (Ungarn), 1965.

115. Schramm O. Illuminating sets of constant width// Mathematika. — 1988. — 35. — C. 180–189.

116. Soifer A. Chromatic number of the plane: a historical essay. — Geombinatorics, 1991. — C. 13–15.

117. Soifer A. Mathematical coloring book. — Center for Excellence in Mathematical Education, 1997.

118. Turan P. Egy grafelmeletiszelsoertek feladatrol// Mat. Fiz. Lapok. — 1941. — 48. — C. 436–452.

119. Weissbach B. Polyhedral covers// Coll. Math. Soc. J. Bolyai. — Amsterdam: North-Holland, 1987. — 48. — C. 639–646.

120. Weissbach B. Sets with large Borsuk number// Beitr ge Alg. Geom. — 2000. — 41. — C. 417–423.

a 121. Wilson R. M. The exact bound in the Erds—Ko—Rado theorem// Combinatorica. — 1984. — 4. — C. 247– o 257.

122. Ziegler G. M. Lectures on 0/1-polytopes// in: «Polytopes-Combinatorics and Computation» (G. Kalai and G. M. Ziegler, eds.)/ DMV, Seminar 29. — Basel: Birkh user-Verlag, 2000. — C. 1–44.

a 123. Ziegler G. M. Coloring Hamming graphs, optimal binary codes, and the 0/1-Borsuk problem in low dimensions// Lect. Notes Comput. Sci. — 2001. — 2122. — C. 159–171.

А. М. Райгородский Московский государственный университет им. М. В. Ломоносова

 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.