LINEBURG


<< Пред. стр.

страница 3
(всего 6)

ОГЛАВЛЕНИЕ

След. стр. >>

ма IV доказана.
Тот факт, что оценка Райского тридцатилетней давности, несмо-
тря на усилия специалистов и на наличие мощной вычислительной
техники, до сих пор не улучшена, обескураживает в ещё большей
степени, чем аналогичное обстоятельство, касающееся мозеровско-
го неравенства ?( 2 )?4: если для плоскости существуют соображе-
ния, заставляющие верить в точность столь простой конструкции,
как веретено, то в пространстве и таких соображений нет.
О б с у ж д е н и е т е о р е м ы V. Заметим сперва, что совсем лег-
ко может быть получена оценка ?( 3 )?27. Эта оценка является
прямым переносом на трёхмерную ситуацию простейших методов,
позволивших отыскать неравенства ?( 1 )?2 и ?( 2 )?9: на пря-
мой мы чередовали отрезки, на плоскости — квадраты, ясно,
что в пространстве нужно для тех же целей использовать кубы.
15
z




y

x




Рис. 10


Например, можно <замостить> всё 3 <большими> кубами с дли-
ной ребра 1,65, разбитыми, в свою очередь, одним и тем же
способом на 27 <маленьких> кубиков-<цветов>, имеющих длину
ребра 0,55. Тогда длина диагонали в одноцветном кубике ока-
v
зывается равна 0,55 3<1, а расстояние между любыми двумя
одноцветными кубиками не меньше, чем 1,1>1.
Результат Кулсона, к обсуждению которого мы собираемся
приступить, опирается, по-существу, на ту же <решётчатую> тех-
нику, которая, в конечном счёте, позволила нам обосновать дву-
мерный результат Хадвигера. Иными словами, мы и здесь столк-
нёмся с совершенно эффективным построением раскраски, при-
чем оно опять-таки будет основано на рассмотрении разбиений
Вороного.
Определение. Решёткой ? в пространстве называется множе-
ство всех точек вида
ax+by+cz=(ax1 +by1 +cz1 , ax2 +by2 +cz2 , ax3 +by3 +cz3 ),
где векторы x=(x1 , x2 , x3 ), y=(y1 , y2 , y3 ) и z=(z1 , z2 , z3 ) неком-
планарны (т. е. точки (0, 0, 0), (x1 , x2 , x3 ), (y1 , y2 , y3 ) и (z1 , z2 , z3 )
не лежат в одной плоскости), а величины a, b и c принимают
любые целочисленные значения. Говорят, что векторы x, y и z
образуют базис решётки ?.
Таким образом, решётка в 3 — это непосредственный ана-
лог двумерной решётки, а её простейшим примером является
решётка 3 , состоящая из всех векторов с целыми координатами
16
z




x

y




Рис. 11

и порождённая естественным базисом из векторов (1, 0, 0), (0, 1, 0)
и (0, 0, 1).
Определение. Разбиением пространства на многогранники на-
зывается бесконечное множество T , состоящее из таких (много-
гранных) тел T1 , T2 , ..., что их объединение T1 ?T2 ?... совпадает
со всем 3 и что любые два из них пересекаются, как максимум,
по элементам границы (граням, рёбрам и вершинам).
Определение множества Вороного, отвечающего точке решёт-
ки ?, даётся в точности так же, как это было сделано и в случае
плоскости. Только теперь множество Вороного — это многогранник
(докажите это). Имеет место теорема, которая обобщает теорему
о разбиении плоскости на многоугольники и которую мы тем бо-
лее в этой брошюре доказывать не будем.
Теорема. Какова бы ни была решётка ? в пространстве,
множество всех многогранников Вороного, отвечающих элемен-
там x??, образует разбиение 3 . Такое разбиение называется
(решётчатым) разбиением Вороного.
17
z




x

y




Рис. 12


Из теоремы вытекает общий рецепт построения раскраски:
нужно взять какую-нибудь решётку ? в 3 и по определённо-
му правилу раскрасить её многогранники Вороного в достаточно
маленькое число цветов. Дальнейшая проблема состоит в том,
чтобы цвета оказались расположенными в верном порядке, т. е.
чтобы, с одной стороны, сами многогранники имели, как гово-
рят, диаметр (наибольшее расстояние между точками), меньший
единицы, а с другой стороны, расстояние между многогранни-
ками одного цвета было больше единицы. В этой брошюре мы
не станем вдаваться в подробности того, как решается послед-
няя проблема. Мы здесь заметим лишь, что оценка ?( 3 )?27 уже
получена с помощью общего метода, поскольку кубы суть много-
гранники Вороного для решётки 3 . Заметим также, что оценка
?( 3 )?21, принадлежащая Сойферу (1996), может быть доказана
за счёт рассмотрения решётки, порождённой базисом из векторов
(1, 1, 0), (0, 1, 1), (1, 0, 1); оценка ?( 3 )?18, найденная Кулсо-
ном в 1997 году, следует из свойств разбиения Вороного для
# A
1 1 1!
решётки с базисом (1, 0, 0),  , , !, (0, 0, 1), а результат теоре-
!
2 2 2
мы V обусловлен структурой решётки, построенной на векторах
18
#v A# vA#v A
v v v
2! 2! 2 2 !
! ! !
22 22 2
! ! 0!. Наконец, на рис. 10—
 3v 5 , v 5 , 0!, ? 3v 5 , 0, v 5 !,  3v 5 , ? v 5 , !
  
12 изображены многогранники Вороного, отвечающие перечислен-
ным разбиениям (решёткам).
Замечая напоследок, что средствами геометрии чисел мож-
но доказать неулучшаемость кулсоновского неравенства ?( 3 )?15
при помощи решётчатых разбиений пространства, мы приходим,
в частности, к следующим интересным и важным задачам.
7. Попробуйте получить по возможности лучшую нижнюю
оценку для минимального числа цветов в раскраске 3 , при ко-
торой каждый цвет обладает надлежащим свойством с запретом
расстояния и при этом является объединением многогранников.
8. Можно ли усилить оценку ?( 3 )?27 за счёт рассмотрения
раскрасок кубами?
9. Попытайтесь раскрашивать пространство многогранниками
того или иного типа. Сколько цветов, в зависимости от вы-
бранного множества, придётся задействовать, и скольких цветов
заведомо хватит? Можно ли придумать такой многогранник, что-
бы цветов потребовалось, скажем, больше 30?
10. Постройте разбиение Вороного для решётки с базисом
# A# A
1 2!
!, 0, 0, 3 !.
!
! !
(1, 0, 0), 0, , 
4
33

МНОГОМЕРНЫЙ СЛУЧАЙ
В предыдущих главах мы весьма подробно изучили задачу Эр-
дёша—Хадвигера в пространствах, с которыми мы, в принципе,
достаточно хорошо знакомы: обычные школьные курсы плани-
метрии и стереометрии уже содержат в себе всю необходимую
информацию об их природе, да и повседневной интуиции впол-
не хватает для того, чтобы слова <размерность 1> или, скажем,
<размерность 3> не вызывали какого-либо недоумения. Однако
в математике часто возникают (и активно используются) раз-
личные объекты, определение которых не предполагает наличия
в той или иной степени конкретных образов, которыми можно
было бы оперировать, имея целью дать себе максимально нагляд-
ное, <жизненное> (т. е. имеющее аналог в окружающем нас мире)
представление об этих объектах. Такие объекты носят обыкновен-
но вполне абстрактный характер, и человеку, не подготовленному
к встрече с ними, может показаться странной сама идея их рас-
смотрения. На самом же деле, огромное количество совершенно
реальных, <прикладных> задач зачастую сводится как раз к ис-
следованию свойств подобного рода <невообразимых> конструкций
и понятий. Более того, у специалистов, работающих с этими по-
нятиями, появляется особая интуиция, которая уже полностью
19
отвлечена от повседневных образов и опирается лишь на внутрен-
нее видение соответствующей концепции.
?
Тем самым, определения и термины, которые нам понадобят-
ся, мы постараемся ввести наименее формальным способом, так
как для понимания сути проблемы хроматических чисел требует-
ся совсем немного.
Итак, мы хотим сформулировать задачу Эрдёша—Хадвигера
в том изначальном — <классическом> — виде, в каком она была
поставлена своими авторами. Для этого нам понадобится понятие
n-мерного евклидова пространства, которое, памятуя о прежних
обозначениях, мы будем записывать в виде выражения n , указы-
вая в верхнем индексе на размерность. В сущности, само понятие
вводится крайне просто: фактически, n — это есть множество
всех возможных наборов из n вещественных чисел (<координат>
или <компонент>) x1 , x2 , ..., xn — <векторов> (или <точек>) x=
=(x1 , x2 , ..., xn ), снабжённое <расстоянием>
q
|x? y|= (x1 ?y1 )2 +(x2 ?y2 )2 +...+(xn ?yn )2 ,

где, естественно, x=(x1 , x2 , ..., xn ) и y=(y1 , y2 , ..., yn ). Таким обра-
зом, n есть прямое обобщение для 1 , 2 и 3 . Как видно, даже
будучи прямым обобщением известных конструкций, <геометриче-
ски> n при n?4 становится чем-то малоосязаемым и, безусловно,
абстрактным. Тем не менее, научиться работать с таким объек-
том, даже не имея чисто геометрической интуиции его внутренней
структуры, не так уж сложно: в нашей ситуации на помощь здесь
приходит комбинаторика, и это обстоятельство может служить
одним из обоснований термина <комбинаторная геометрия>, с ко-
торого мы начали нашу брошюру.
Коль скоро мы знаем, что такое n , понятна и постановка
задачи Эрдёша—Хадвигера: как всегда, необходимо отыскать вели-
чину ?( n ), равную минимальному числу цветов, в которые можно
так раскрасить всё n-мерное пространство, что одноцветных точек,
отстоящих друг от друга на расстояние 1, существовать не будет.
Заметим, как и в начале брошюры, что расстояние 1 в опре-
делении хроматического числа играет лишь условную роль: оно
без труда заменяется любым другим положительным расстоянием,
и значение величины ?( n ) от этого никак не зависит. Для удоб-
ства изложения упомянутое расстояние мы будем в дальнейшем
называть <критическим> или <запрещённым>.
Ясно, что раз задача была трудной уже в размерностях 2
и 3, то ожидать упрощения ситуации при условии неограничен-
ного возрастания величины n отнюдь не приходится. Прежде чем
приступать к подробному обсуждению и доказательству известных
(и объяснению неизвестных, но предполагаемых гипотетически)
20
результатов, мы вкратце изложим их. В следующей таблице при-
ведены верхние и нижние оценки для ?( n ) в размерностях n,
4?n?15. Кроме того, в таблице указаны фамилии авторов оце-
нок и годы появления в печати соответствующих публикаций*).

n n
)? Автор, год )? Автор, год
n ?( ?(
4 6 Д. Е. Райский, 1971 49 Д. Кулсон, 2002
45
5 8 Д. Ларман и К. А. Роджерс, 1972 фольклор
46
6 10 А. М. Райгородский, 2000 фольклор
47
7 15 А. М. Райгородский, 2000 фольклор
48
8 16 Д. Ларман и К. А. Роджерс, 1972 фольклор
59
9 16 Д. Ларман и К. А. Роджерс, 1972 фольклор
510
10 19 Д. Ларман и К. А. Роджерс, 1972 фольклор
511
11 20 А. М. Райгородский, 2000 фольклор
512
12 24 Д. Ларман и К. А. Роджерс, 1972 фольклор
513
13 31 Д. Ларман и К. А. Роджерс, 1972 фольклор
514
14 35 Д. Ларман и К. А. Роджерс, 1972 фольклор
515
15 37 Д. Ларман и К. А. Роджерс, 1972 фольклор


В таблицу вошли результаты для n?15. По-видимому, нет
?
смысла пытаться распространить эту таблицу на большие значе-
ния n. Вернее, это, конечно, можно сделать, но в любом случае
где-нибудь рано или поздно придётся остановиться. Другое дело,
что очень интересно попробовать понять, как устроены верхние
и нижние оценки для хроматического числа, когда n не есть
фиксированная константа, а когда n неограниченно возрастает.
Иными словами, разумно постараться записать оценки в виде
u(n)??( n )?v(n), где u(n) и v(n) суть функции от n. И здесь хро-
нологическая последовательность результатов такова. В 1971 году
Д. Е. Райский, с именем которого мы уже сталкивались прежде,
показал, что ?( n )?n+2 (заметьте, что при n=2 упомянутая
оценка отвечает теореме братьев Мозеров, а при n=3 — это ре-
зультат всё того же Райского). В 1972 году два выдающихся
английских математика Д. Ларман и К. А. Роджерс установи-
ли, что ?( n )?c1 n2 , где c1 — вполне конкретная константа,
не зависящая от размерности (значение c1 мы выпишем позже).
В 1978 году Д. Ларман улучшил последний результат, заменив
его неравенством ?( n )?c2 n3 . Наконец, в 1981 году П. Франкл
и Р. Уилсон совершили настоящий прорыв, доказав свою знамени-
тую теорему, о которой в надлежащем месте мы скажем несколько

*) Оценки, авторство которых мы приписываем фольклору, разумеется, крайне
слабы, и нет сомнений в том, что они могут быть значительно улучшены. Однако
похоже, что за эту неблагодарную работу ещё никто не брался.
21
слов и из которой, в частности, вытекает оценка вида ?( n )?
??1 ·1,207n (?1 >0 — конкретная константа). В действительности,
запись оценки может быть слегка уточнена, но, по-существу, нам
хватит и этого*). Неравенство Франкла—Уилсона удалось слегка
усилить лишь спустя почти 20 лет после его появления: соответ-
ствующий факт был обнаружен автором этой брошюры, и состоит
он в том, что ?( n )??2 ·1,239n . Опять-таки мы не приводим здесь
это утверждение в своём самом точном виде.
После всего сказанного выше у читателя может возникнуть со-
вершенно резонный вопрос: а что же с верхними оценками для
хроматических чисел? Не окажется ли так, что и вовсе, несмо-
тря на уже установленную нами ограниченность величины ?( n )
?
при n?3, в каких-нибудь больших размерностях она сделается
бесконечной (т. е. будет иметь место равенство v(n)=?, означа-
ющее, что при некотором n, какое бы конечное число цветов v
мы ни взяли, раскрасить с помощью них всё n надлежащим
образом не получится)? Вопрос тем более резонен, что в случае
положительного на него ответа (или даже гипотетической возмож-
ности такового) значимость теорем, упомянутых выше, несколько
блёкнет: ведь в сравнении с бесконечностью и степенная функция,
и экспонента мало отличаются друг от друга. Утешительным обсто-
ятельством является то, что, конечно, хроматические числа всегда
v
ограничены. Легче всего обосновать оценку ?( n )?(4[ n+1])n ,
и мы не преминём сделать это, когда перейдём к детальному об-
суждению (а не перечислению) результатов. Эта оценка настолько
естественно обобщает уже заготовленные нами в предыдущих гла-
вах факты, что приписывать её какому-либо автору не принято.
В то же время она существенно разнится с самой лучшей из ниж-
них**), и потому для её улучшения были предприняты абсолютно
оправданные усилия: в 1972 году Ларман и Роджерс показали,
что ?( n )??3 ·3,001n . Как всегда, для большей прозрачности мы
не выписываем оценку в самом точном виде.
Итак, хроматическое число <зажато> между двумя экспонентами:
?2 ·1,239n ??( n )??3 ·3,001n ; эти экспоненты никто в настоящий
*) Слово <прорыв> здесь отнюдь не случайно: тот, кто хотя бы немного знаком
с теорией пределов, знает, что функция вида cn при c>1 (такая функция назы-
вается <экспонентой>) растёт <быстрее> любой степенной, т. е. что для любого
фиксированного k? выполнено соотношение nk /cn >0 при n>?. Иначе говоря,
оценка Франкла—Уилсона не только лучше при достаточно больших n, чем оценки
Лармана и Роджерса, но она заведомо превосходит всякую оценку схожего вида.
<Эмпирически>, т. е. опытным путём, убедиться в этом может каждый — даже ес-
ли слово <предел> для него ново. Попробуйте, например, сопоставить n100 и 1,207n ,
и вы увидите, что, начиная с некоторого n0 , значения второй функции станут всё
быстрее и быстрее увеличиваться по сравнению со значениями первой. То же самое
произойдёт и для n1000 (по отношению к экспоненте), и для n1000000 , и т. д.
**) Здесь вновь правильнее было бы говорить в терминах теории пределов, но
и компьютерного счёта достаточно, чтобы увидеть, насколько быстрее, чем экспо-
v
нента, растёт функция (4[ n+1])n .
22
момент ничем лучшим заменять не умеет, а главная проблема
состоит, разумеется, именно в <сближении> верхней и нижней
оценок. В дальнейшем об этой проблеме мы ещё поговорим.

n )?n+2
Доказательство теоремы Райского: ? (
Коль скоро мы уже умеем обосновывать аналогичные резуль-
таты при фиксированных n=2 и 3, логично предположить, что
и в случае произвольной размерности метод, с помощью которого
доказывается теорема Райского, напоминает своих <маломерных>
предшественников. В действительности, так оно и есть. Проблема,
однако, заключается в том, что, не имея, скажем, четырёхмерной
интуиции, мы не можем без определённой подготовки сказать, что
является аналогом иглы в 4 , и т. д. Дабы разобраться с этой
проблемой, давайте подумаем: а в чём состоит сходство между
конструкциями братьев Мозеров и Райского (т. е. между двумер-
ным и трёхмерным веретеном)? Ответ напрашивается сам собой:
для построения игл, а стало быть, и веретена на плоскости мы
использовали правильные треугольники с длинами сторон 1; для
соответствующего построения в пространстве 3 мы прибегли к по-
мощи правильных тетраэдров с единичными рёбрами. Естественно,
тем самым, попробовать обобщить понятия (правильных) треуголь-
ников и тетраэдров на размерности n?4.
Определение. Если расстояние между любыми двумя точками
из множества точек x1 , x2 , ..., xn+1 , лежащих в пространстве n ,
равно одному и тому же фиксированному числу (например, еди-
нице), то говорят, что x1 , x2 , ..., xn+1 суть вершины правильного
n-мерного симплекса. Сам симплекс представляет собой <выпукл-
ую оболочку> своих вершин, т. е. множество всех векторов x,
которые можно записать в виде x=?1 x1 +?2 x2 +...+?n+1 xn+1 , где
?1 ?0, ?2 ?0, ..., ?n+1 ?0 и ?1 +?2 +...+?n+1 =1*).
Привести пример правильного симплекса (и, таким образом,
доказать, по крайней мере, корректность определения) ничего
не стоит: достаточно взять, скажем, множество вершин x1 =
# A # A # A
! ! 1!
! ! !
1 1
=  v , 0, ..., 0!, x2 = 0, v , 0, ..., 0!, ..., xn = 0, ..., 0, v !, xn+1 =
! ! !
  2
2 2
# A
v v v
1+ 1+n ! !
1+ 1+n 1+ 1+n !. Кроме того, тот факт, что
!
v v v
= , , ..., 
n2 n2 n2
множество вершин правильного симплекса есть прямой аналог

*) Запись ?1 x1 +?2 x2 +...+?n+1 xn+1 подразумевает, как и прежде, что векторы x1 ,
x2 , ..., xn+1 представлены в координатной форме, что каждую координату векто-
ра xi мы домножаем на число ?i и что затем сложение векторов мы производим
покомпонентно.
23

<< Пред. стр.

страница 3
(всего 6)

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign