WWW.DISSERS.RU

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

   Добро пожаловать!


Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |

2n+случае роль покрышки будет играть куб. В самом деле, нетрудно 28. Докажите, что величина f(n) не изменится, если изна- показать, что всякое множество A диаметра 1 в n может быть чально рассматривать только выпуклые замкнутые тела. покрыто некоторым кубом диаметра n, т. е. кубом вида [0, 1]n+x, 29. Пусть Qn n — это множество всех векторов с рацио- x n. Мы оставим довольно рутинное (хотя и простое) доказательнальными координатами. Что такое Qn ство читателю, а сами перейдём к разбиению куба на надлежащее число частей. Для пущей технической ясности мы даже увеличим куб и рассмотрим, соответственно, 9. ОЦЕНКА f(n)n+1 И ПРОБЛЕМА БОРСУКА ДЛЯ ШАРА [ n+1] В седьмой главе мы говорили, что совсем просто установить K1= [0, 1]n n неравенство f(n)n+1. Это и впрямь так, ибо теперь мы знаем, что такое правильный n-мерный симплекс и множество его вер(прибавлять какой-либо вектор не имеет смысла, так как дальшин. Если мы возьмём это самое множество и попытаемся разбить нейшие действия от этого зависеть не будут). Рассмотрим в то же его на n частей, то, конечно же, найдётся хотя бы одна часть, время куб-кирпичик в которой вершин по крайней мере две. Стало быть, и разбиение заведомо не обладает нужным свойством. Заметим, что мы сдела K2= [0, 1]n.

ли в точности то же, что и при n3, ведь, как мы уже говорили 2 n в предыдущей главе, симплекс есть прямое обобщение отрезка, Теперь, фиксируя произвольный вектор вида правильного треугольника и правильного тетраэдра в соответству ющих <школьных> размерностях. Несмотря на то, что геометрия a1 an a= 2n,..., 2n, ai, 0ai2[ n+1]-1, i=1,..., n, многомерная, ничего не изменилось — значит, и с интуицией у нас всё не столь плохо.

применим преобразование параллельного переноса к кубику K2:

Сейчас мы опишем оптимальное разбиение шара на n+1 часть K2 K2+a. Непосредственная проверка показывает, что в резуль меньшего диаметра. Оно тоже будет крайне похожим на своих 2[n+1] n копий нашего кирпичика, причём тате мы получим не более чем трёхмерных предшественников (<значок Мерседеса> объединение этих копий совпадёт с K1. Пользуясь исключительи вписанный тетраэдр).

но одним определением расстояния в n, убеждаемся, что между Итак, пусть B — шар, S — ограничивающая его сфера, а O — любыми двумя точками внутри всякого кирпичика расстояние его центр. Рассмотрим произвольный правильный симплекс не превосходит 1/2<1, и всё в порядке.

R=conv {A1,..., An+1}, Конечно, мы, с одной стороны, провели довольно грубое рассуждение. Ясно ведь, что мы взяли слишком маленький кирпичик:

вершины которого лежат на S (ср. задачу 27). Положим даже если мы увеличим его диаметр почти вдвое, результат оста Ri=conv {O, A1,..., Ai-1, Ai+1,..., An+1}. нется прежним. Следовательно, и оценка f(n)( n+1)n вполне 36 достижима. Однако, с другой стороны, сам тот факт, что в каче- знаем (ср. главу 9), что вершины правильного симплекса диаместве покрышки мы взяли куб, тоже свидетельствует о грубости тра 1 лежат как раз на границе шара радиуса Y(n). Это означает, нашего подхода, и в этом мы вскоре убедимся. что симплекс — в некотором роде наихудшее множество: если каждое множество <шаром Юнга> покрывается, то симплекс нельзя покрыть меньшим шаром (ср. задачу 31).

11. НЕРАВЕНСТВА f(n)2n И f(n)2n-1+С помощью теоремы Юнга удаётся доказать оценку f(n)2n.

В этой главе мы прибегнем к помощи всё тех же универДля этого нужно разбить шар B радиуса Y(n) на 2n частей диаметра сальных покрышек. Идея использования их, как видно, настолько меньше 1. Делается это так. Во-первых, считаем, не ограничивая глубока, что при всей своей кажущейся простоте она влечёт весьобщности, что центр шара — это точка O=(0,..., 0). Далее, берём ма и весьма нетривиальные следствия не только при n3, но гиперплоскости {xi=0}, i=1,..., n. Эти гиперплоскости разбиваи в совершенно общем случае. Желая отыскать покрышку, мы, ют пространство на m=2n частей U1,..., Um (ср. случаи с n=2, 3, естественно, пытаемся рассматривать, по возможности, наименее когда дело сводится к координатным прямым и плоскостям). Несложно устроенные множества. В прошлой главе речь шла о кубе.

трудно видеть, что, поскольку радиус шара при любом n строго Но куб, так сказать, несколько <угловат>, и он захватывает, тем меньше величины 1/ 2, диаметры (одинаковых) частей UiB, разсамым, слишком много лишнего пространства. В результате нам бивающих шар, меньше единицы.

приходится разбивать пустоты, а вовсе даже не исходное множеНеравенство Лассака f(n)2n-1+1 требует дополнительных ство. Какое бы тогда придумать тело, которое покрывало бы любое соображений. Пусть множество A n, diam A =1, покрыто шамножество диаметра 1, выглядело бы попроще, да к тому же ещё ром Юнга B. Можно, как и прежде, считать, что центр B — это O.

и <поплотнее облегало> покрытое множество Конечно, в первую Ясно, что A всегда можно так <пошевелить> внутри B, чтобы очередь в голову приходит обратиться к шару. И действительно, A B =. Пусть xA B. Тогда любая точка из A принадле шар очень удобен. Еще в 1901 году Х. Юнг доказал следующую зажит шару B радиуса 1 с центром в x. Таким образом, A BB, мечательную теорему.

причём можно считать, что Теорема. Всякое множество диаметра 1 в n покрывается шаx={0,..., 0, Y(n)} ром радиуса (нетрудно понять, что геометрия множества BB не зависит от поn Y(n)=.

ложения точки x). Теперь следует взять гиперплоскость {xn= }, 2n+где (0, Y(n)) — параметр, который будет выбран оптимальТеорему Юнга можно доказывать различными способами, но но в конце рассуждения. Гиперплоскость разбивает BB на две каждый из них требует, к сожалению, довольно много места, како- части, в одной из которых лежит x. Назовём эту часть B1, а оставвым мы не располагаем. Мы поступим так: во-первых, предложим шуюся часть — B. Рассмотрим гиперплоскости читателю попытаться самостоятельно доказать теорему (см. зада{xi=0}, i=1,..., n-1.

чи 31 и 32); во-вторых, сошлёмся на книжку [3], где теорема доказана; в-третьих, мы откомментируем теорему, исходя из на- Они, очевидно, разбивают B на m=2n-1 частей B2,..., Bm+1.

копленного материала. В самом деле, в задаче 6 главы 4 и в за- В результате мы имеем разбиение надаче 11 главы 5 читателю уже предлагалось доказать частные шей универсальной покрышки BB на случаи теоремы Юнга. Сперва речь шла о нужное число частей B1,..., Bm+1. Попокрытии произвольного плоского множества кругом радиуса 1/ потом — о покрытии кажите самостоятельно, что параметр 3, трёхмерного множества шаром радиуса 3/8. Однако, если мы можно подобрать так, чтобы diam Bi<подставим в выражение Y(n) двойку и тройку вместо n, то мы для каждого i.

и получим упомянутые величины. Правда, в задачах 7 и 12 из тех Всё, что мы хотели доказать в этой же глав 4 и 5 мы говорили о том, что шара не хватит для реше- главе, мы доказали. Заметим, что пония проблемы Борсука в соответствующих размерностях. Ну, так крышка Лассака уже рассматривалась и сейчас мы не утверждаем, что шар — это предел мечтаний. Про- нами в задачах 8 и 13 из глав 4 и 5 состо в дальнейшем мы убедимся, насколько, с точки зрения нашей ответственно. На рис. 19 показано раззадачи, он лучше куба. В то же время из задачи 27 главы 8 мы биение множества BB на пять частей. Рис. 38 30. Докажите, что при разбиении BB величину можно где любое тело A выпукло и замкнуто. Точно так же можно, коподобрать так, чтобы нечно, определить и h(n). Стало быть, h(n) — это минимальное число гомотетичных копий с коэффициентом гомотетии мень 4n2+ 8n2+1-ше 1, которыми покрывается произвольное наперёд заданное тело.

diam Bi <1.

Опять-таки f(n)h(n).

4n2+4n Задача о нахождении величины h(n) была поставлена в для каждого i.

году И. Ц. Гохбергом и А. С. Маркусом. Чуть ранее (в 1957 году) 31. Докажите один из вариантов классической теоремы ХелГ. Хадвигер начал изучать задачу освещения. Пусть, как и прежде, ли: если любое подмножество в множестве A n, состоящее из тело A n выпукло, замкнуто и имеет диаметр 1. Говорят, что не более чем n+1 точки, покрывается шаром радиуса r, то и санаправление, заданное прямой ={y: }, освещает границу A мо множество A покрывается шаром радиуса r.

в точке x A, если x+yInt A при некотором положитель 32. Пользуясь результатом предыдущей задачи, докажите теоном. Если представить себе плоский или же трёхмерный случай, рему Юнга.

то станет ясно, в чём тут дело: по существу, речь идёт об освещении границы тела пучками параллельных прямых, причём точка 12. НЕРАВЕНСТВО ШРАММА считается освещённой, если она — первая точка тела, на которую В этой главе мы расскажем о том, на чём основано дока упал свет, идущий по соответствующей прямой (>0), и если свет зательство оценки f(n) 3/2+o(1) n, полученной О. Шраммом не прошел её <по касательной>, а попал, пройдя её, <в мясо> A в 1988 году. Разумеется, у нас нет возможности изложить здесь (скажем, когда мы освещаем квадрат на плоскости направленисамо доказательство даже схематично. Оно опирается на достаточем, заданным прямой, которая параллельна двум каким-нибудь но нетривиальные факты анализа и теории вероятностей. Однако его сторонам, очевидно, что ни одна из точек, лежащих на этих удивительным образом оно связано с двумя другими — по сути, сторонах, не освещена). Как обычно, введём некоторую числосовпадающими — задачами комбинаторной геометрии. Эти задавую характеристику тела, отвечающую на сей раз за <качество> чи представляют немалый самостоятельный интерес, и потому мы освещения его границы. Пусть i(A ) — это минимальное число накое-что сперва скажем о них, а уж тогда и связь с нашей основправлений в n, таких, что каждая точка x A освещена одним ной проблемой станет очевидна.

из них. Величина i(A ) называется числом освещения тела A.

Рассмотрим произвольное замкнутое выпуклое тело A n По аналогии с прежними ситуациями рассмотрим число с diam A =1. Положим h(A ) равным минимальному числу гомоi(n)=max i(A ).

тетичных копий A с коэффициентом гомотетии (0, 1), которыA ми A может быть покрыто. Иными словами, мы пытаемся отысДовольно легко показать, что для любого тела A 2 чикать наименьшее количество тел A1,..., Ah, гомотетичных A сла h(A ) и i(A ) совпадают (см. [2]). На самом же деле это верно и обладающих свойством и в произвольной размерности. Соответствующую теорему доказал в 1960 году В. Г. Болтянский. Таким образом, f(n)h(n)=i(n).

A A1...Ah.

Если рассмотреть какой-либо n-мерный куб K, то нетрудно Понятно, что ситуация весьма близка к той, с которой мы имели увидеть, что h(K )=i(K )=2n (каждую вершину куба необходимо дело и в рамках задачи Борсука, и в рамках задачи Грюнбаума.

освещать отдельным направлением). С одной стороны, Хадвигер, Только если раньше мы либо разбивали тело на абы какие части, Гохберг и Маркус высказали гипотезу, что i(n)2n. Поразительно, либо покрывали его геометрически никак не связанными с ним но эта гипотеза до сих пор никем не доказана и не опровергнушарами, то теперь мы покрываем его телами, полученными из та (см. конец главы). Однако, с другой стороны, даже если мы него же посредством вполне конкретного и притом совсем простого допустим, что гипотеза верна, всё равно с точки зрения Борсука преобразования. Ясно, что работать с h(A ) гораздо проще, чем ничего хорошего мы не получим, ведь оценку f(n)2n мы и так с f(A ), и при этом легко видеть, что f(A )h(A ). Тем самым, знаем: она весьма проста, и для её обоснования вовсе не требуется если оценить h(A ) сверху должным образом, то такая же оценка решать проблему освещения. К чему же тогда все наши рассуждебудет верна и для <числа Борсука>.

ния Оказывается, имеет место следующая теорема.

Из задачи 28 главы 8 мы знаем, что Теорема. Всякое выпуклое тело A в n, имеющее диаметр 1, f(n)=max f(A ), покрывается некоторым телом W постоянной ширины, у коA 40 торого и ширина, и диаметр равны единице. Иными словами, говорит нам о том, что всякое множество диаметра 1 покрывается совокупность всех тел постоянной ширины 1 образует (бесконеч- шаром радиуса примерно 1/ 2, но так у этого шара диаметр куда ную) универсальную покрывающую систему в n. как больше единицы. А в то же время есть правильный симплекс, В то же время Шрамм доказал такой глубокий факт: ес- который меньшим шаром покрыть нельзя (см. задачу 27 главы 8).

ли W — тело постоянной ширины, то i(W ) 3/2+o(1) n. Таким образом, нахождение величины g1(n) есть вполне разумная Что отсюда следует Ну, во-первых, h(W ) тоже не превосходит и, вероятно, сложная задача. С другой стороны, если мы покро 3/2+o(1) n. Во-вторых, если A — произвольное выпуклое тело, ем множество g1(n) шарами того же диаметра, то мы его и на то по теореме найдётся W, покрывающее A и имеющее тот же (n+1)g1(n) частей меньшего диаметра без труда разобьём: шар-то диаметр. Ясно, что f(W )h(W ) 3/2+o(1) n, а значит, f(A ) на n+1 часть надлежащего вида, как известно, разбивается. Стаи вместе с ним f(n) оцениваются так, как оно и было обещано. ло быть, f(n)(n+1)g1(n), и если вдруг окажется, что В завершение главы добавим ещё несколько слов о пробле ме освещения. Мы знаем теперь, что для тел постоянной ширины g1(n) c+o(1) n, где c>1, эта проблема решена, и даже, более того, в ней получены весьто и с f(n) дела будут обстоять не хуже (o(1) — это ведь всё, что ма хорошие оценки (правда, n должно быть достаточно велико).

угодно: лишь бы оно к нулю стремилось*)).

Для центрально-симметричных тел она также почти <дожата>:

Историю константы c, которая возникла в предыдущем абзаце, К. А. Роджерс показал в 1965 году, что если A n центральмы фактически уже знаем. А именно, сперва был К. А. Роджерс, но-симметрично, то который оценил c величиной 2, а затем Бургейн с Линденштраус i(A )2n(n ln n+n ln ln n+5n).

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

Хадвигера—Гохберга—Маркуса до сих пор не доказана и не опроВ сущности, Роджерс установил следующий важный факт:

вергнута. Наконец, в общем случае известно лишь, что r/+o(1) n шарами радиуса

шар радиуса r можно покрыть Этот факт крайне непрост, и относится он, вообще-то, к такой i(n)(n+1)n.

очень красивой геометрической науке, которая называется теорией плотнейших упаковок и покрытий. Как следствие, шар Юнга 13. НЕРАВЕНСТВА РОДЖЕРСА может быть покрыт 2+o(1) n шарами диаметра 1, откуда и выИ БУРГЕЙНА—ЛИНДЕНШТРАУССА текает соответствующая оценка на f(n). В свою очередь, Бургейн и Линденштраусс реализовали более тонкую программу. Они расКак мы знаем, оценка Шрамма была передоказана Ж. Бургейсмотрели два случая: либо множество покрывается шаром радиуса ном и Й. Линденштрауссом в 1991 году. Казалось бы, какой в том 3/8, либо нет. В первом случае они применили технику Роджерпрок Ведь оценка однажды уже получена. К чему бы получать её са, что тотчас же привело их к искомой оценке. Во втором же снова Однако смысл был, и очень большой. Дело в том, что если случае они сумели уточнить роджерсовский результат, который Шрамм обосновывал свой результат, исходя из нового неравенства в целом неулучшаем, и это далось им немалой ценой.

в проблеме освещения, то Бургейн и Линденштраусс пользовались Разумеется, мы не станем вдаваться здесь в какие-либо дальсовершенно иным соображением: они апеллировали к задаче Грюннейшие подробности метода. Заметим только, что при всей своей баума, и, в частности, им удалось установить относительно неё нетривиальности и технической сложности он довольно груб: с касамые точные факты среди известных к настоящему времени.

кой стати, в самом-то деле, покрывать множество именно шарами Напомним, что задача Грюнбаума состоит в отыскании миниК сожалению, метод Шрамма груб в не меньшей степени, — разве мального числа gd(n) шаров диаметра d, которыми может быть что там мы используем не шары, а гомотетичные копии исходных покрыто произвольное множество диаметра 1 в пространстве. Котел. Поразительно, что и Шрамм, и Бургейн абсолютно разными нечно, когда в главе 5 мы говорили об этой задаче, речь шла только о малых размерностях, но ничего ведь не изменится, если *) Тут имеется аналитическая тонкость, которую тяжело обойти, не владея в домы формально озвучим то же определение и при n4.

статочной мере теорией пределов. Главное — понимать, что функция n+1 растёт Пусть d=1. Мы прекрасно понимаем, что и в этих условиях значительно медленнее экспоненты, а значит, и влияние её столь же несуществензадача Грюнбаума весьма нетривиальна: разумеется, теорема Юнга но, как и влияние <о малых>.

Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |






















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

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