WWW.DISSERS.RU

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

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


Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 7 |

На самом деле, тут всё же имеется одна тонкость. Рассмотрим при- Неудобоваримое число. Что такое 2015 измерений, помыслить не 2+2/n n мер с a=2, o(1)=2/ n. Можно показать, что функция реально. В то же время и н и ж н я я оценка на f(n), которую заодно n с ростом n ведёт себя примерно так же, как функция 2ne. А по- с контрпримерами предложили Кан и Калаи, оказалась весьма люследняя функция, безусловно, превосходит экспоненту 2n в весьма бопытной. Теперь речь уже не шла ни о каком n+1; выяснилось, n быстро растущее число раз. Тем не менее, если n достаточно вели- что всё гораздо хитрее и что по крайней мере f(n) 1,203+o(1).

n ко, то 1,999n2ne 2,001n, а начиная с ещё более крупных n, Такая оценка всё равно весьма далека от оценки сверху f(n)S(n).

и вовсе различие между верхней и нижней оценками проявится В указанном обстоятельстве проще всего убедиться, исходя из зналишь в каком-нибудь миллиардном знаке после запятой. В реаль- ния теории пределов, и <на пальцах> нетрудно подсчитать, что но 1,203+o(1) n становится пренебрежимо ма ности очень редко бывает интересна такая запредельная точность, с ростом n величина и потому (именно с такой — обыденной — точки зрения) мы име- ленькой по сравнению с S(n).

ем право говорить о том, что (a+o(1))n <приближается> к an: Короче говоря, <пришла мысль — отворяй ворота>. Отныне разницы между a-10-100, a и a+10-100 для нас в к а к о м - т о львиная доля усилий была брошена на уменьшение размерности, с м ы с л е не существует. в которой удаётся построить контрпример, и на уточнение нижней Рассмотрим оценки первого вида. Совсем легко показать, что оценки для f(n). Соответствующая деятельность была во многом f(n) 2[ n+1] n (см. главу 10). Несколько тяжелее даётся нера- подобна спортивному соревнованию, когда всё решается сотыми венство f(n)2n (см. главу 11). Наконец, в 1982 году М. Лассак долями секунды. Ниже мы приводим таблицу последовательных доказал, что f(n)2n-1+1, и мы докажем это в главе 11. Среди рекордов от 1993 года до последних дней.

28 <трагедия> состоит хотя бы в том, что даже при n=4 мы никаких Автор, год n f(n) n разумных результатов не имеем. Есть оценка Лассака 1,203 +o(1) Дж. Кан, Г. Калаи, 1993 n f(4)24-1+1=9, 1,203 +o(1) А. Нилли, 1994 n и есть соображения, показывающие, что, скорее всего, при n= 1,203 +o(1) Б. Вайссбах, Й. Грей, 1997 n гипотеза Борсука верна. Тем не менее, проблема остаётся открытой 1,203 +o(1) А. М. Райгородский, 1997 и крайне интересной.

1,2255+o(1) n А. М. Райгородский, 1999 — В следующей главе мы дадим некоторые важные многомерные n 1,203 +o(1) определения, которые хорошо коррелируют со своими аналогами Б. Вайссбах, 2000 при n3 и которые позволят нам грамотно обсуждать и даже подчас А. Хинрихс, 2001 324 — доказывать различные результаты из числа упомянутых выше.

О. Пихурко, 2002 323 — 8. ВСПОМОГАТЕЛЬНЫЕ ПОНЯТИЯ И ЕЩЁ НЕМНОГО ИСТОРИИ А. Хинрихс, Х. Рихтер, 2003 298 — В этой главе мы приведём набор важных определений и проПрокомментируем таблицу. Во втором столбце указаны нижкомментируем их.

ние границы для размерностей, с которых гипотеза Борсука заведоОпределение. Пусть имеется два вектора мо перестаёт быть верной благодаря результатам соответствующих x=(x1,..., xn), y=(y1,..., yn) n авторов. С остальными столбцами всё и так ясно. Если в какой-то графе стоит прочерк, это означает, что либо хорошие контрприи два вещественных числа, µ. Тогда через x+µy мы будем обо меры не получаются, хотя оценка на f(n) улучшена, либо что, значать вектор z=(z1,..., zn), у которого координаты имеют вид наоборот, контрпримеры придуманы, а вот оценка с ростом n <не zi=xi+µyi, i=1,..., n. Данное определение позволяет естественпошла>. Читатель спросит: <Как же такое возможно Вроде бы ным образом перенести сложение векторов и умножение их на 1,2255+o(1) n куда больше, чем 1,203+o(1) n Почему же точисло на многомерную ситуацию.

гда в надлежащей графе стоит прочерк> Дело в том, что в малых Определение. Пусть x1,..., xk — какие-то векторы в простран размерностях, где мы и стремимся отыскать контрпримеры, нельзя стве. Их выпуклой оболочкой называется множество A, состоящее сбрасывать со счетов o(1). К сожалению, метод может позволить из тех и только тех векторов, которые могут быть представлены увеличить константу с 1,203 до 1,2255, но при этом изменится сков виде 1x1+...+kxk, где 1,..., k — неотрицательные веще рость, с которой o(1) приближается к нулю. Скажем, могло быть так:

ственные числа, в сумме дающие единицу. Множество A принято n n обозначать conv {x1,..., xk}, подчёркивая выпуклость*), и называть 1000 f(n) 1,203+ и f(n) 1,2255+.

выпуклым многогранником или политопом.

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

именно в том, как устроена <бесконечно малая>, которую мы Определение. Длина отрезка — это расстояние между концами не конкретизируем.

отрезка.

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

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

него определения.

Завершая главу, заметим, что и по сей день никто не знает, как устроена жизнь в размерностях 4n297. Основная нынешняя *) От слова convexus (лат.) — выпуклый.

30 Определение. Назовём векторы x1,..., xn+1 n вершинами Теперь мы хотим определить многомерный аналог квадрата правильного n-мерного симплекса, коль скоро все попарные рассто- и куба. Мы уже делали это в брошюре [1]. Однако мы повторим яния между ними равны одному и тому же числу. Многогранник необходимые слова и здесь.

Определение. Единичным n-мерным кубом (который мы обоconv {x1,..., xn+1} значим [0, 1]n) мы будем называть выпуклую оболочку множества мы будем называть правильным n-мерным симплексом. Зафиксиру- всех 2n (0, 1)-векторов в n (т. е. векторов, имеющих координаты ем произвольный набор вершин симплекса — скажем, xi1,..., xik, или 1). Сами (0, 1)-векторы мы будем называть (в данном контек 1kn. Мы будем говорить, что выпуклая оболочка этих вер- сте) вершинами единичного куба. Произвольный куб (скажем, K ) шин образует (k-1)-мерную грань симплекса. будет тогда получаться из единичного посредством преобразоваВо-первых, ничего не стоит привести пример множества вер- ний <сжатия> и параллельного переноса: K =k[0, 1]n+x, где шин правильного симплекса в n (см. [1]). Во-вторых, довольно k>0 — произвольный коэффициент, отвечающий за сжатие (разпросто понять, что если бы мы захотели построить правильный дувание), а x — произвольный n-мерный вектор, за счёт которого симплекс с n+2 вершинами, то нам бы это не удалось. При этом осуществляется перенос. При этом равенство между множествами всё сказанное прекрасно коррелирует с тем, с чем мы постоянно понимается в том смысле, что каждый вектор y в K может быть сталкивались, изучая n при n3: отрезок, правильный тре- представлен в виде y=kz+x, где, в свою очередь, z[0, 1]n (и на угольник и тетраэдр суть очевидные <прародители> правильного оборот, kz+xK для каждого z[0, 1]n).

симплекса. Заметим, что грани иной раз могут превращаться в сто- Определение. Пусть дано некоторое множество A n. Будем роны (при k=2) и даже в вершины (при k=1). Смысл вычитания говорить, что точка xA является внутренней точкой множе единицы из k при определении размерности грани ясен: разумно ства A, если существует шар достаточно маленького радиуса ведь считать любую точку нульмерной, любой отрезок одномерным с центром в x, целиком содержащийся в A. Если точка x n и т. д. Грани размерности n-1 иногда ещё называют гипергранями такова, что сколь угодно малый шар с центром в ней имеет непуили фасетами. Понятно, что граней размерности k-1 в симплексе стое пересечение как с A, так и с его дополнением n A, то эта ровно Ck. В частности, в симплексе имеется n+1 гипергрань — точка называется граничной для A. Совокупность всех внутренn+по числу вершин. Наконец, диаметр симплекса — это длина его них точек множества A мы будем обозначать Int A и называть стороны. внутренностью или мясом A. Совокупность же граничных точек Определение. Пусть набор чисел a1,..., an содержит ненулевые для A — это граница (шкура) A множества A. Если Int A неэлементы. Тогда множество векторов x=(x1,..., xn) n, удовле- пусто, то мы скажем, что A — тело. Если Int A =A, то A — творяющих условию открытое множество (его граница ему не принадлежит). Если же дополнение к A открыто, то A замкнуто (оно полностью содерa1x1+...+anxn=b, жит свою границу).

где b — некоторое фиксированное число, образует гиперплоскость. В разделе задач мы рассмотрим несколько вопросов, которые Гиперплоскость обобщает прямую в 2 и плоскость в 3. позволят лучше прочувствовать только что введённые понятия.

Легко убедиться в том, что любая гипергрань симплекса од- Определение. Пусть A — выпуклое тело, а x A. Рассмо нозначно задаёт гиперплоскость, которая через неё проходит (её трим множество всех гиперплоскостей, проходящих через точку x.

содержит). Таким образом, каждый правильный симплекс опреде- Некоторые из них проходят через внутренность A, а некоторые — ляет n+1 гиперплоскость в пространстве (очевидно, эти гиперплос- нет. Назовём последние опорными гиперплоскостями к A в точкости различны). Зафиксируем одну из вершин xi симплекса A ; ке x*) (они таковы, что множество A лежит <по одну сторону> от через неё проходит ровно n гиперплоскостей, определённых сим- каждой из них). Если для любого x A опорная гиперплоскость плексом. Нетрудно видеть, что эти гиперплоскости разбивают n к A в x единственна, то A называется телом с гладкой грани на 2n частей, в одной из которых лежит исходный симплекс. На- цей или просто гладким телом.

зовём эту часть n-мерным многогранным углом, имеющим вершину Смысл понятия опорной гиперплоскости легче всего иллюв xi и порождённым симплексом A (см. главу 5). Ясно, что мы стрировать в 2. Там речь пойдёт об опорной прямой. Примеры имеем дело с обычным углом на плоскости и с многогранным углом в 3, коль скоро в приведённом определении ограничиваем*) Вообще-то, нужно доказывать существование опорных гиперплоскостей, но ся случаями n=2 и n=3. в данном случае оно обусловлено выпуклостью.

32 множеств с гладкой и негладкой границей показаны на рис. 18. Определение. Пусть x, y n. Будем говорить, что — это Ясно, что в случае гладких множеств опорные прямые суть каса- прямая, проходящая через x и y, если — это множество точек тельные. Поэтому в общем случае также говорят о касательных вида x+(1-)y,.

гиперплоскостях. Это определение прямой, как всегда, прекрасно коррелирует с общеизвестным. В частности, прямая содержит отрезок от x до y.

Определение. Пусть даны точки x, O n и прямая ={x+(1-)O}, проходящая через них. Тогда говорят, что точка x =-x+2O симметрична точке x относительно O. Пусть A — некоторое Рис. множество и существует такая точка O n, что для любого xA точка x, симметричная x относительно O, принадлежит A.

Назовём две гиперплоскости параллельными, если у них нет Тогда множество A называется центрально-симметричным, а точобщих точек. Можно показать, что если A — выпуклое тело ка O — центром симметрии.

и x A, то для любой опорной гиперплоскости к A в точке x Приведённых определений хватит для обсуждения результанайдётся и притом единственная параллельная ей опорная гипертов, сформулированных в предыдущей главе. Более того, мы даже плоскость к A. Это утверждение особенно понятно в случае 2.

способны теперь изложить ещё несколько замечательных фактов, Пусть x=(x0,..., x0), соответствующая опорная гиперплоскость n связанных с историей гипотезы Борсука. Излагая эту историю, мы задаётся условием a1x1+...+anxn+b=0, а опорная гиперплосзаметили, что гипотеза была доказана для множеств из обширных кость, параллельная ей, — условием a x1+...+a xn+b =0. Ши1 n классов. Что же это за классы Во-первых, в 1947 году Г. Хадвигер риной тела A в точке x мы будем называть расстояние между установил, что любое множество с гладкой границей может быть нашими гиперплоскостями, определяемое, например, по формуле разбито на n+1 часть меньшего диаметра, и тогда казалось, что |a x0+...+a x0 +b| до решения проблемы совсем недалеко: стоит только покрыть про1 n n.

извольное множество достаточно близким к нему гладким телом, (a )2+...+(a )1 n разбить последнее и, подобно тому, как у нас это получалось в слуИнтуитивно не совсем ясно, почему речь идёт именно о рассточае универсальных покрышек и покрывающих систем, прийти янии. Однако, если провести аналогии с 2 и 3, то становится к выводу, что и само исходное множество допускает надлежащее немного легче. А вот уж почему ширина — это расстояние между разбиение. К сожалению, описанный подход реализовать невозпараллельными гиперплоскостями, вполне понятно.

можно: отсюда и контрпримеры. С другой стороны, гипотеза была Определение. Множество A называется выпуклым телом подоказана для центрально-симметричных множеств, которые уже стоянной ширины, если, во-первых, оно является выпуклым телом вовсе не обязаны быть гладкими. В книжке [2] кое-что из сказани, во-вторых, его ширина не зависит от точки x A.

ного есть, и мы не станем вдаваться здесь в подробности.

Самым простым примером выпуклого тела постоянной ширины 19. Докажите, что куб [0, 1]n можно определить как множеможет служить шар (см. задачи).

ство точек x=(x1,..., xn), удовлетворяющих условию Определение. Рассмотрим некоторое множество A n. Пусть 0i=1,...,n xi1.

max O n — фиксированная точка, а x — произвольная точка в A.

Рассмотрим отрезок, соединяющий O с x. Пусть r — это длина Является ли куб выпуклым замкнутым нашего отрезка. Возьмём на нём точку y, отстоящую от O на рас 20. Докажите, что сфера — это шкура шара. Что является стояние r, где (0, 1) — произвольное число. В результате провнутренностью шара куба ведения такой операции с каждой точкой xA получится новое 21. Является ли куб телом с гладкой границей А симплекс множество A, которое называется гомотетичной копией множе22. При каких >0 множество ства A с центром гомотетии O и коэффициентом гомотетии.

Данное определение совершенно естественно, если сравнить его A = x=(x1,..., xn): |x1|+...+|xn| с двумерными и трёхмерными аналогами. Легко видеть, что выпукло Будет ли такое множество центрально-симметричным diam A = diam A

25. Докажите, что диаметр тела постоянной ширины совпадает Заметим напоследок, что Борсук ещё в 1932 году доказал с его шириной. невозможность разбиения шара B на n частей меньшего диаметра.

26. Пусть B1, B2 — шары с общим центром и радиусами r1, r2 Это весьма тонкий результат, также дающий оценку f(n)n+1.

(r1>r2). Рассмотрим A =B1 B2. Будет ли A выпуклым цен трально-симметричным замкнутым 10. ОЦЕНКА f(n) 2[ n+1] n 27. Докажите, что вершины правильного n-мерного симплекса, Здесь мы воспользуемся стандартной идеей универсальной по n крышки, к помощи которой мы уже не раз прибегали. В данном имеющего диаметр 1, лежат на сфере радиуса.

Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 7 |






















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

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