WWW.KNIGI.KONFLIB.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

 
<< HOME
Научная библиотека
CONTACTS

Pages:     || 2 | 3 | 4 | 5 |   ...   | 6 |

«СОДЕРЖАНИЕ Введение........................................... 147 1. Обозначения и различные варианты формулировки проблемы. ...»

-- [ Страница 1 ] --

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

УДК 514.11

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

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

c 2007 г.

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

СОДЕРЖАНИЕ

Введение........................................... 147 1. Обозначения и различные варианты формулировки проблемы............ 148 2. Универсальные покрышки................................. 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, и, стало быть, гипотеза Борсука на прямой верна. В сущности, верен еще более сильный результат. Положим где точная верхняя грань берется по всем 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 вершины записываются так:



Pages:     || 2 | 3 | 4 | 5 |   ...   | 6 |
 


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

«ГЕОГРАФИЯ. Подготовка к ЕГЭ 2010 770 разноуровневых тренировочных заданий ко всем темам школьного курса географии с ответами и решениями; 5 вариантов ЕГЭ с ответами и решениями структуры 2010 г. АННОТАЦИЯ Книга География. Подготовка к ЕГЭ содержит тестовые материалы по географии, разработанные и составленные автором. Первая часть книги состоит из тренировочных заданий, разбитых по темам, обозначенным в Кодификаторе элементов содержания и требований к уровню подготовки выпускников...»

«Утвержден президиумом Челябинского областного суда 05 сентября 2012 года ОБЗОР СУДЕБНОЙ ПРАКТИКИ ЧЕЛЯБИНСКОГО ОБЛАСТНОГО СУДА ЗА ВТОРОЙ КВАРТАЛ 2012 ГОДА СУДЕБНАЯ ПРАКТИКА ПО УГОЛОВНЫМ ДЕЛАМ Вопросы квалификации 1. Причинение потерпевшему в ходе разбоя вреда здоровью средней тяжести охватывается составом преступления, предусмотренным статьей 162 Уголовного кодекса Российской Федерации. Приговором Аргаяшского районного суда К. осужден по ч. 1 ст. 112 и ч. 2 ст. 162 Уголовного кодекса Российской...»

«Все обещало мне его Анна Ахматова 2 Книга Анна Ахматова. Все обещало мне его скачана с jokibook.ru заходите, у нас всегда много свежих книг! 3 Книга Анна Ахматова. Все обещало мне его скачана с jokibook.ru заходите, у нас всегда много свежих книг! Анна Ахматова Все обещало мне его. Стихотворения 4 Книга Анна Ахматова. Все обещало мне его скачана с jokibook.ru заходите, у нас всегда много свежих книг! Предисловие Всего прочнее на земле печаль. А. Ахматова Творческая судьба Анны Ахматовой...»

«СХЕМА КОМПЛЕКСНОГО ИСПОЛЬЗОВАНИЯ И ОХРАНЫ ВОДНЫХ ОБЪЕКТОВ БАССЕЙНА РЕКИ ВОЛХОВ Книга 4 ВОДОХОЗЯЙСТВЕННЫЕ БАЛАНСЫ И БАЛАНСЫ ЗАГРЯЗНЯЮЩИХ ВЕЩЕСТВ 1 ВВЕДЕНИЕ В данном проекте рассматривается территория бассейна реки Волхов (российская часть бассейна) (код 01.04.02), включая следующие водохозяйственные участки: 01.04.02.001 - Шлина от истока до Вышневолоцкого г/у; 01.04.02.002 - Мста без реки Шлина от истока до Вышневолоцкого г/у; 01.04.02.003 - Ловать и Пола; 01.04.02.004 - Шелонь; 01.04.02.005 -...»

«Пояснительная записка Данная рабочая программа по английскому языку разработана для обучения в 5Б классе МБОУ-СОШ №36 на основе федерального компонента государственного образовательного стандарта 2004 г., примерной программы основного общего образования по английскому языку 2004 года с учетом второй ступени (5-9 классы) блока авторской рабочей учебной программы курса английского языка Биболетовой М.З., Трубаневой Н.Н к линии УМК и материалам авторского учебнометодического комплекса,...»

«Издание второе, исправленное и дополненное Скан&OCR 3aH3u6ap Издательство Советская Россия Москва — 1976 31 декабря 2012 Долина реки Сороти Valley of the Sorotj river © Издательство Советская Россия, 1974 г. Valle de la reviere Sorot © Издательство Советская Россия, 1976 г. Tal des Sorotj-Flusses с исправлениями и...»

«В.Я. Ворошилов. Феномен игры Предисловие Книга, которую вы держите в руках, написана человеком, окрещенным одной из центральных газет как Инкогнито из Останкино. И действительно, Владимир Ворошилов, в отличие от всех своих телевизионных cобратьевведущих, предпочитает не появляться на экране. В передаче Что? Где? Когда?, придуманной и созданной им, присутствует лишь его голос. Лишь. Но это, оказывается, и создает тот уникальный эффект притяжения зрительного интереса и к личности ведущего...»

«66 Подборка из 8 планов Санкт-Петербурга и изъяснений к ним: 1) Изъяснение плана Санкт-Петербурга. СПб., в типографии А.А. Плюшара, 1840. 2) Изъяснение плана местности Санкт-Петербурга в 1700 году. СПб., печатано в типографии К. Жернакова, 1846. 3) Изъяснение плана местности Санкт-Петербурга в 1705 году. СПб., печатано в типографии К. Жернакова, 1846. 4) Изъяснение плана местности СанктПетербурга в 1725 году. СПб., печатано в типографии К. Жернакова, 1846. 5) Изъяснение плана местности...»

«ПОД СОЗВЕЗДИЕМ ТОПОРА Избранное ПОСЕВ Обложка работы художника Николая Сафонова © Posscv-Verlag, V. Goradiek К. G., 1976 Frankfurt/Main Printed in Germany Сергею Бонгарту другу и художнику посвящаю эту книгу ПО ДОРОГЕ ОТТУДА Апрель! Я болен этой датой! За крышей — голубой клочок, И грач слетел как завсегдатай На облюбованный сучок. Кричит — и на гортанный вызов К нему сородичи спешат, И хлещет жижица с карнизов. Как будто вылили ушат! Очнутся люди, хлынут песни И вскроют окон переплет....»

«V ОТ ИЗДАТЕЛЯ Что? Книга про стикеры? А разве по этой теме можно написать целую книгу? Именно так большинство коллег и друзей реагировало на известие о том, чему будет посвящена вторая...»






 
© 2013 www.knigi.konflib.ru - «Бесплатная электронная библиотека»

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