LINEBURG


<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>

на и, несомненно, достойна серьёзного внимания и тщательного
изучения.
В заключение параграфа добавим, что конструкции автора этой
брошюры, позволившие ему в 2000 году слегка улучшить оценку
Франкла—Уилсона, принципиально отличаются ото всех, что бы-
ли описаны выше: вместо (0, 1)-векторов в них рассматриваются
(0, 1, ?1)-векторы (т. е. векторы с тремя возможными значени-
ями координат). В свою очередь, дополнительные видоизменения
техники Франкла—Уилсона и др. дают известные усиления оце-
нок для хроматических чисел. Отметим, кстати, что (0, 1, ?1)-век-
торы уже не допускают столь наглядной интерпретации в тер-
минах подмножеств конечного множества. Разумеется, можно го-
ворить об <упорядоченных парах непересекающихся подмножеств
в Rn >, но удобнее здесь оказывается работать непосредственно
с векторами, запрещая не пересечениям, как то было в леммах,
принимать конкретные значения, а скалярным произведениям,
т. е. величинам (x, y)=x1 y1 +x2 y2 +...+xn yn . Последнее обобще-
ние, в действительности, абсолютно прозрачно, ведь для (0, 1)-век-
торов скалярное произведение и мощность пересечения соответ-
ствующих множеств, очевидно, совпадают.
11. Докажите, что в некотором смысле оценка в теореме Фран-
кла—Уилсона неулучшаема (ср. обсуждение леммы Лармана—
Роджерса), а именно: полагая, например, n=4p (p — простое),
a=2p?1, можно построить совокупность M a-элементных под-
множеств n-элементного множества, которая бы обладала всеми
необходимыми свойствами и в то же время имела мощность,
допустим, µ(n), такую, что величина µ(n) отличается от значе-
p?1
ния верхней оценки, даваемой теоремой (т. е. от величины Cn )
не более чем в P(n) раз, где P(n)=ut nt +ut?1 nt?1 +...+u1 n+
+u0 — некоторый (конкретный) многочлен степени t, зависящий
от переменной n. Впрочем, для начала найдите хотя бы какую-
нибудь, по возможности лучшую, оценку снизу для подобно-
го µ(n).
12. (Н е р е ш ё н н а я п р о б л е м а.) Можно ли в условиях
теоремы Франкла—Уилсона избавиться от требования простоты
числа p? Сохранится ли при этом оценка? Если нет, то какая
32
оценка будет точной?
13. Зафиксируйте какую-нибудь <маленькую> размерность n,
например, n=4, 5, ..., 10 и т. д. Можно ли ожидать, что кон-
струкции из (0, 1)-векторов дадут в этой размерности достаточно
большую нижнюю оценку на хроматическое число? Иными сло-
вами, постарайтесь получить максимально хорошую в е р х н ю ю
оценку для величины
?({0, 1}n )=max ?(?, l),
?, l

где ? — произвольное семейство n-мерных (0, 1)-векторов, l —
произвольное запрещённое расстояние, а ?(?, l) — это мини-
мальное количество цветов, которые можно выбрать так, чтобы
раскрасить все элементы из ? с естественным условием: если ка-
кие-либо два элемента отстоят друг от друга на расстояние l, то
они раскрашены в разные цвета. Ясно, что искомая оценка будет
служить мерилом того, насколько, в действительности, разумно
рассматривать именно системы (0, 1)-векторов для решения за-
дачи Эрдёша—Хадвигера. Заметим, что об этой оценке известно
довольно много. Однако точного результата здесь никто не знает.
14. Проделайте то же, что и в задаче 13, но для систем (0, 1,
?1)-векторов (с запретами на скалярные произведения). Про та-
кие системы, кстати, известно гораздо меньше. Ещё хуже устро-
ена жизнь для систем общего вида — скажем, систем (b1 , b2 , ...
..., bt )-векторов, т. е. векторов, у которых координатам разреша-
ется принимать ровно t перечисленных значений: здесь имеются
лишь многомерные оценки автора, так что возможность для твор-
чества тут ничем не ограничена.
15. (Н е р е ш ё н н а я п р о б л е м а.) Постройте наилучшую
(т. е. дающую наилучшие неравенства) критическую конфигу-
рацию с помощью (0, 1, ?1)-векторов. Гипотеза состоит в том,
что конструкция, предложенная автором, отнюдь не оптимальна
(см. [1]) и что, вообще говоря, улучшение техники обязано приве-
сти к весьма существенному усилению оценки ?( n )??2 ·1,239n .
v
Доказательство оценки ? ( n )?(4[ n+1])n
и обсуждение методов её усиления
Искомое доказательство, в конечном счёте, опирается на со-
ображения, полностью аналогичные тем, что мы использовали при
обосновании простейших <маломерных> оценок ?( 1 )?2, ?( 2 )?
?9 и ?( 3 )?27. Однако вновь, как и при обсуждении теоремы
Райского, мы сталкиваемся с необходимостью перенесения не-
которых вполне стандартных понятий с размерностей 1, 2 и 3
на размерности n?4, где одной обыденной интуицией, как пра-
вило (и к сожалению), обойтись не удаётся. Если для теоремы
33
Райского нам потребовалось понятие симплекса — обобщение по-
нятий правильного треугольника и правильного тетраэдра, то для
?
интересующей нас оценки нам нужно будет осознать, что предста-
вляет собой n-мерный куб — аналог отрезка на прямой, квадрата
на плоскости и обычного куба в обычном же пространстве (нашей
целью будет, естественно, <замощение> n кубами: ср. похожие
доказательства при n?3).
Вообще говоря, существует несколько эквивалентных определе-
ний n-мерного куба. Часть из них мы приведём в разделе задач
в конце параграфа, и это, безусловно, будет способствовать возник-
новению лучшей геометрической интуиции у читателя. Сейчас же
мы воспользуемся лишь одним из возможных определений —
тем, которое наиболее удобно для обоснования неравенства ?( n )?
v
?(4[ n+1])n . В любом случае, мы откажемся от чисто комбина-
торного подхода и постараемся вернуться к классической геометрии.
Определение. Единичным n-мерным кубом (который мы обо-
значим [0, 1]n ) мы будем называть выпуклую оболочку множества
всех 2n (0, 1)-векторов в n . Сами (0, 1)-векторы мы будем называть
(в данном контексте) вершинами единичного куба. Произвольный
куб (скажем, K ) будет тогда получаться из единичного посредством
преобразований <растяжения> (<сжатия>) и параллельного переноса:
K =k·[0, 1]n + x, где k>0 — произвольный коэффициент, отвеча-
ющий за <растяжение> (<сжатие>), а x — произвольный n-мерный
вектор, за счёт которого осуществляется перенос. При этом равен-
ство между множествами понимается в том смысле, что каждый
вектор y в K может быть представлен в виде y=kz+ x, где, в свою
очередь, z?[0, 1]n (и наоборот, kz+ x?K для каждого z?[0, 1]n ).
Понятно, что данное определение есть и впрямь точный аналог
соответствующих одно-, двух- и трёхмерных, и читателю остаётся
лишь с лёгкостью убедиться в этом (ср. задачи).
v
2[ n+1]
Рассмотрим <большой> куб K1 = ·[0, 1]n и <малень-
v
n
1
кий> куб-<кирпичик> K2 = v ·[0, 1]n . В дальнейшем посредст-
2n
вом K1 мы замостим всё n-мерное пространство, а K2 будет
отвечать за тот или иной цвет в искомой раскраске внутри ка-
ждого из больших кубов. В самом деле, фиксируя произвольный
# A
an ! v
!
a1
вектор вида a=  v , ..., v !, ai — целые и 0?ai ?4[ n+1]?1,
!

2n 2n
1?i?n, применим преобразование параллельного переноса к ку-
бику K2 : K2 >K2 + a. Непосредственная проверка показывает,
v
что в результате мы получим (4[ n+1])n копий нашего кирпи-
чика, причём объединение этих копий совпадёт с K1 . Каждую
из полученных копий раскрасим в свой цвет. (Если какая-нибудь
34
точка x?K1 попадает одновременно в несколько копий, то ей
мы присвоим цвет произвольным образом.) Пользуясь исключи-
тельно одним определением расстояния в n , убеждаемся, что
между любыми двумя точками внутри всякого кирпичика расстоя-
ние не превосходит 1/2<1. Теперь <разносим> раскраску куба K1
на всё пространство опять-таки с помощью параллельных перено-
сов, последовательно добавляя к K1 всевозможные векторы вида
v v
b=(kb1 , ..., kbn ), где b1 , ..., bn — целые, а k=2[ n+1]/ n (снова
при неоднозначности выбираем цвет наугад). Ясно, что расстояние
между точками одного цвета, лежащими в разных копиях большо-
v
2[ n+1] 1
? v >1, и, стало быть,
v
го куба, никак не меньше, чем
2n
n
v
n )?(4[n+1])n .
?(
Известно два способа усиления только что доказанного нера-
венства. Первый способ состоит попросту в том, чтобы сделать
слегка менее грубыми проведённые выше рассуждения. В свя-
зи с этим мы предлагаем читателю самостоятельно произвести
v
надлежащие выкладки и убедиться в том, что ?( n )?( n+2)n .
Конечно, последняя оценка значительно (примерно в 4n раз) луч-
ше изначальной. Однако и она, по сути, столь же далека от оценки
?( n )?c·3,001n , которая, как мы помним, является наилучшей
из обоснованных к настоящему времени. Оказывается, что методы
геометрии чисел работают не только в размерностях n?3, и вто-
рой способ нетривиального улучшения оценок хроматического
числа опирается как раз на обобщение подробно изученной нами
соответствующей техники на случай n>3. Иными словами, в лю-
бой размерности можно определить понятие решётки (по аналогии
с тем, как это было сделано на плоскости и в 3 ), понятие много-
гранника и разбиения Вороного и, пользуясь достаточно сложными
результатами Роджерса, Эрдёша и некоторых других авторов,
организовать решётчатую раскраску в c·3,001n цветов. К сожале-
нию, даже упомянутые определения (не говоря уже о результатах)
носят более тонкий характер, чем все объекты, с которыми нам
доводилось сталкиваться в этой брошюре: для их максимально-
го прояснения потребовалось бы слишком много времени и места,
и потому мы считаем возможным не рассматривать их подробно,
а лишь ограничимся сделанным упоминанием. Заметим, нако-
нец, что, по всей видимости, геометрико-числовые инструменты,
используемые для отыскания верхних оценок на хроматическое
число, не являются оптимальными*). Тем не менее, никто не знает,

*) Во всяком случае, нельзя надеяться на получение с их помощью оценки, луч-
шей, чем ?( n )?2n+1 ?1 (Кулсон, 2000), хотя, безусловно, даже подобная оценка
весьма далека от своего доказательства или опровержения. Кстати, при n=2 вели-
чина 2n+1 ?1 равна 7, а при n=3 равна 15 (см. сс. 11 и 19).
35
чем их следует заменить с целью дальнейшего продвижения
в вопросе.
16. Докажите, что
[0, 1]n ={x=(x1 , ..., xn ): 0?xi ?1, i=1, ..., n}.
17. Назовём гиперплоскостью в n-мерном пространстве мно-
жество всех векторов, координаты которых удовлетворяют со-
отношению a1 x1 +...+an xn =b, где a1 , ..., an , b — некоторые
вещественные числа, причём все ai =0, i=1, ..., n. Докажи-
те, что всякая гиперплоскость может быть естественным образом
отождествлена с n?1 .
18. Назовём l-мерной гранью (0?l?n?1) единичного n-мер-
ного куба любое множество вида
[0, 1]n ?{x=(x1 , ..., xn ): xi =?1 , ..., xi =?n?l }.
1 n?l


Здесь i1 , ..., in?l — произвольный набор несовпадающих индек-
сов, лежащих в пределах от 1 до n, а ?j — либо 0, либо 1. Найдите
число различных l-мерных граней единичного куба и убедитесь
в том, что оно совпадает с соответствующими величинами, по-
лучающимися при n=1, 2, 3. Дайте естественное определение
l-мерной грани произвольного куба K .
19. Докажите, что в рамках приведённой нами раскраски n
копии маленьких кубов либо не пересекаются, либо пересекают-
ся между собой по граням какой-нибудь размерности l. То же
самое — для больших кубов.

ПРИЛОЖЕНИЕ 1
НЕСКОЛЬКО СЛОВ О ТЕОРИИ ГРАФОВ
В предыдущих главах мы изложили многие важные результа-
ты, касающиеся проблемы Эрдёша—Хадвигера: кое-что мы просто
сформулировали, кое-что доказали, кое-что предложили в каче-
стве задач или и вовсе нерешённых проблем и гипотез. Теперь же
в общих чертах обсудим глубокий математический контекст, в ко-
торый, на самом деле, вкладывается наша проблема: с одной
стороны, это позволит ещё лучше понять основную подоплёку
нашей деятельности, с другой стороны, это даст возможность про-
чувствовать нетривиальные связи между различными разделами
математики в целом и комбинаторики в частности.
Одной из наиболее бурно развивающихся математических тео-
рий является теория графов. Прежде чем пояснить, что же такое,
собственно, есть граф, мы заметим, не вдаваясь в подробности,
что этот объект, во всей своей полноте начавший исследовать-
ся приблизительно в середине XX века, возникает при поста-
новке, решении и комбинаторно-геометрической интерпретации
36
v3
огромного числа современных задач науки.
v5
Про графы написано бесчисленное множество v1
замечательных статей, монографий, популяр-
v4 v7
ных книг и учебников, и мы, естественно,
не преследуем цель хоть в какой-то мере по- v2 v6
крыть в рамках этой главы даже малую долю
имеющихся фактов. Отсылая заинтересован- Рис. 13
ного читателя к соответствующей литературе
(см., скажем, [2]), мы только введём несколько необходимых нам
определений и с их точки зрения прокомментируем понятие хро-
матического числа.
Определение. Графом называется <пара> (V, E), где V — не-
которое (произвольное) множество объектов vi , природа которых
нам, в принципе, не важна, а E — это некоторое множество
(различных) пар (vi , vj ) элементов V, причём мы считаем, что
(vi , vj )=(vj , vi ) (т. е. что рассматриваемые пары <не упорядочены>,
а сам граф <не ориентирован>) и что (vi , vi )?E (т. е. что в графе
нет <петель>). Множества V и E могут быть как конечными, так
и бесконечными; первое из них носит название <множества вер-
шин графа>, второе — <множества его рёбер>.
Разумеется, определение звучит ужасающе. Тем не менее оно,
по счастью, допускает вполне прозрачную геометрическую интер-
претацию. Действительно, каждому элементу из абсолютно аб-
страктного V (т. е. каждой вершине графа) можно сопоставить
какую-нибудь точку на плоскости. В свою очередь, каждому ребру
ставится в соответствие линия, которая соединяет точки, отве-
чающие вершинам этого ребра (рис. 13). Понятно, конечно, что
подобная интерпретация далеко не единственна: всё зависит от то-
го, какие точки мы возьмём в качестве образов вершин и как
начертим линии рёбер. В этом отношении возникает классическая
проблема: можно ли <вложить> граф в плоскость, т. е. можно ли
придумать такое соответствие между объектами в V и E и ана-
логичными объектами на плоскости, чтобы при нём линии рёбер
графа пересекались между собой исключительно по вершинам?
Например, на рис. 14, а, б приведены две различные интерпре-
тации одного и того же графа, причём в первой из них условие
вложения нарушено, а во второй всё в порядке (здесь в обоих слу-
чаях V ={v1 , ..., v10 }, а E={(v1 , v2 ), (v1 , v4 ), (v1 , v3 ), (v2 , v3 ), (v2 , v5 ),
v7
v2
v7 v8
v1 v2
v5 v6 v5 v6
v3 v10 v8
v1

v3 v4 v9 v10 v4 v9
а) б)
Рис. 14
37
K5 K3,3
(v4 , v5 ), ..., (v9 , v10 )}). Проблема
была решена Л. С. Понтряги-
ным в 1927 году и, независи-
мо, К. Куратовским в 1930 го-
ду: конечный граф вкладывает-
ся в плоскость тогда и только
Рис. 15
тогда, когда его множества вер-
шин и рёбер не содержат в себе подмножеств, изображённых
на рис. 15, быть может, с дополнительными вершинами на рёбрах
(строгую формулировку см. в книге [2]). Факт, обнаруженный
Понтрягиным и Куратовским, является весьма нетривиальным
и глубоким.
Заметим, во-первых, что всякий (конечный) граф легко вкла-
дывается в 3 (попробуйте доказать это). Заметим также, что,
позволяя множеству V быть бесконечным, а потом <кодируя>
его точками плоскости, мы немного слукавили. Дело в том, что
в теории множеств, разработанной Г. Кантором в XIX веке, суще-
ствует целая иерархия бесконечностей, так что, например, беско-
нечность множества натуральных чисел и бесконечность множества
рациональных чисел в самом точном смысле относятся к одному
и тому же классу, в то время как бесконечность множества ве-
щественных чисел принципиально отличается от двух последних:
она, как говорят, <мощнее>. Есть бесконечности и более мощные,
чем бесконечность множества точек на плоскости; поэтому, беря
<их> в качестве множеств вершин графа, мы не сможем проин-
терпретировать их точками в 2 . Однако в рамках этой брошюры
об этом не стоит беспокоиться: никаких <заумных> графов мы
строить не будем, и всё сказанное выше в наших дальнейших си-
туациях будет верно.
Одним из весьма распространённых примеров того, как графы
возникают в приложениях, могут служить знакомые всем компью-
терные сети — Интернет и пр. Вершинами графа тогда являются
объединённые в сеть компьютеры, а рёбра графа суть, если угод-
но, провода, соединяющие <вершины> и позволяющие им, тем
самым, производить обмен информацией. Математика (комбинато-
рика) возникает в тот момент, когда мы задаёмся целью изучить
поведение нашей системы в предположении наличия возможных
сбоев в процессах передачи информации: различные (как правило,
числовые) характеристики графа помогают, например, отследить,
с какой <вероятностью> (строго определяемой степенью достовер-
ности) система будет в том или ином смысле <хорошо> (или,
наоборот, <плохо>) функционировать. Замечательно то, что в роли
одной из упомянутых числовых характеристик графа выступает
его хроматическое число, определяемое как минимальное количе-
ство цветов, в которые можно раскрасить вершины графа с тем,
38
чтобы вершины, соединённые рёбрами, были раскрашены в раз-
ные цвета.
В контексте последнего определения становится ясно, что,
на самом деле, хроматические числа пространств, которые мы
до сих пор изучали, суть не что иное, как хроматические числа бес-
конечных графов Gn =(Vn , En ), где Vn = n , а En ={(v1 , v2 )=(x, y):
|x? y|=a}, a>0 — произвольное фиксированное вещественное чи-
сло (критическое расстояние). Иными словами, множество вершин
графа Gn совпадает со всем n-мерным евклидовым пространством,
а множество рёбер этого графа состоит из всех возможных пар
n-мерных векторов, расстояние между которыми равно крити-
ческому. Единственный вопрос, который, вследствие замечаний,
сделанных выше, может здесь возникнуть, — почему граф со столь
<жирным> множеством вершин тоже допускает геометрическую
интерпретацию. Ответ сводится, с одной стороны, к ссылке на всё
ту же канторовскую теорию множеств, утверждающую, что между
точками в n и точками в 2 имеется взаимно однозначное со-
ответствие, т. е. что и впрямь какая-то двумерная интерпретация
допустима. С другой стороны, само определение Gn уже совершен-
но геометрично, так что особенно стремиться тут к понижению
размерности, пожалуй, и не стоит.
На язык теории графов очень удобно и полезно переводить
понятие (M, D)-критической конфигурации. Для этого, правда,
нужно сперва сказать, что подграфом G =(V , E ) графа G=(V, E)
называется граф, множество вершин V которого вкладывается
в множество вершин V графа G, причём у этого графа, в свою оче-
редь, множество рёбер E , заданное на V , естественно, является
подмножеством множества E. Если хроматические числа графов
обозначать, как и прежде, греческой буквой ?, то из опреде-
лений, очевидно, вытекает неравенство ?(G)??(G ). Разумеется,
неравенство применимо и к графу Gn с его подграфами. В част-
ности, в качестве последних можно брать конечные подграфы
?=(V , E ), считая, что #V =M. Стандартный способ отыскания
нижних оценок для хроматических чисел конечных графов состоит
в следующем. Пусть ?(?) есть максимальная мощность подмно-
жества в множестве вершин V , такого, что никакие два его
элемента не соединены ребром. Величина ?(?) называется числом
независимости графа ?, и нетрудно видеть, что ?(?)?M/?(?).
В то же время, вспоминая связь между обычным определением
хроматического числа пространства и определением той же вели-
чины при помощи графа Gn , легко убедиться в том, что ?(?),
по сути, есть просто теоретико-графовый эквивалент величины D
из критической конфигурации. Таким образом, мы, действитель-
но, имеем право понимать множество ? и как (M, D)-критическую
конфигурацию, и как граф с множеством вершин мощности M
39
и числом независимости, равным D, т. е. оценка ?( n )?M/D,
в конечном счёте, проистекает из теоретико-графового неравен-
ства ?(Gn )??(?)?M/?(?). Заметим, наконец, что нет никакой
необходимости распространять описанную технику на бесконечные
подграфы графа Gn , поскольку выполнена
Теорема Эрдёша—де-Брёйна. Если у бесконечного графа ко-
нечное хроматическое число, то оно достигается на некотором его
конечном подграфе.
Коль скоро мы знаем, что ?(Gn )=?( n )??3 ·3,001n <?, то всё,
стало быть, обосновано, и, в частности, намного прозрачнее то

<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign