LINEBURG


<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>

множества вершин правильного треугольника, а равно и множе-
ства вершин правильного тетраэдра, очевиден без дальнейших
пояснений: всякий раз попарные расстояния между векторами,
образующими упомянутые множества, совпадают друг с другом,
причём и впрямь у треугольника (n=2) число вершин есть 2+1=
=3, а у тетраэдра (n=3) оно равно 3+1=4. Остаётся осознать,
что треугольник с тетраэдром, действительно, получаются как вы-
пуклые оболочки множеств своих вершин, и это мы предлагаем
сделать читателю самостоятельно. Заметим ещё, что понятие вы-
пуклой оболочки играет весьма значительную роль в геометрии.
Заметим, наконец, что одномерный симплекс — это отрезок.
k-мерной гранью (n-мерного) симплекса называется выпуклая
оболочка любой совокупности k+1?n вершин, выбранных из мно-
жества x1 , ..., xn+1 . Ясно, что всего у симплекса столько k-мерных
граней, сколькими способами такой выбор можно осуществить.
Число этих способов равно биномиальному коэффициенту Ck+1 = n+1
(n+1)!
= . Рёбрами симплекса называют одномерные грани-
(k+1)! (n?k)!
отрезки*).
В целом, геометрия симплекса довольно красива, и на её
примере вполне можно почувствовать, что собой представляют
многомерные задачи. Сравнивая известные характеристики тре-
угольников и тетраэдров с аналогичными характеристиками для
симплексов произвольной размерности, легко понять, насколько
геометрично n , даже несмотря на отсутствие у нас изначальной
интуиции. Вообще, можно было бы ещё долго обсуждать аналогии
между <маломерными> и <многомерными> ситуациями. Однако
нашей целью является доказательство теоремы Райского, и к не-
му мы теперь практически готовы перейти.
Рассмотрим симплекс A1 A2 ...An+1 в n (скажем, тот, коор-
динаты вершин которого мы уже выписывали ранее; во всяком
случае, мы предполагаем, что длина каждого ребра этого сим-
плекса равна 1**)) и зафиксируем одну (любую) из его граней
размерности n?1: допустим, это будет грань A1 A2 ...An . Пользуясь
исключительно координатной записью векторов в нашем n-мерном
пространстве, нетрудно доказать следующую лемму.
Лемма. Помимо симплекса A1 A2 ...An+1 , существует ровно один
(правильный) симплекс A1 A2 ...An An+1 , имеющий общую грань
A1 A2 ...An с исходным. Если называть объединение двух упо-

*) Проверьте корректность сказанного, т. е. примените определение к треуголь-
нику и тетраэдру и убедитесь в том, что понятие ребра-отрезка отвечает интуитивно
очевидному.
**) Ясно, что <длина ребра> — это попросту расстояние между точками Ai и Aj ,
выпуклой оболочкой которых это ребро является, т. е. длина ребра — это длина
отрезка Ai Aj .
24
мянутых симплексов — <многогранник> A1 A2 ...An An+1 An+1 —
<иглой>, то найдётся другая игла An+1 B1 B2 ...Bn Bn+1 , такая, что
у неё с первой иглой есть в точности одна общая вершина An+1
и что расстояние между вершинами An+1 и Bn+1 равно 1.
Мы оставляем несложное доказательство леммы читателю.
Заметим также, что появившееся в формулировке леммы опреде-
ление иглы (да и вся лемма) наиболее естественным образом обоб-
щает соответствующие объекты (и факты) из малых размерностей.
Вспоминая теперь, что мы в размерностях 2 и 3 называли
(M, D)-критической конфигурацией, легко понять, как такой объ-
ект должен быть определён в n (см. соответствующую главу, где
всё полностью аналогично). Более того, нетрудно проверить, что
множество точек A1 , A2 , ..., An+1 , An+1 , B1 , B2 , ..., Bn+1 образует
(2n+3, 2)-критическую конфигурацию, а стало быть, по стандарт-
ным соображениям,
A A
n )? 2n+3 ! +1=n+2,
!
!
 
?(
2
и теорема Райского доказана.
5 )?8
Доказательство теоремы Лармана—Роджерса: ? (
Доказывая теорему Райского, мы, безусловно, спокойно могли
обойтись без каких-либо геометрических определений, рассужде-
ний и аналогий: в принципе, нам достаточно было бы выписать все
векторы A1 , A2 , ..., An+1 , An+1 , B1 , B2 , ..., Bn+1 в координатной
форме и сослаться на свойства критических конфигураций. Тем
не менее, мы намеренно пошли по более трудному пути: во-пер-
вых, только на том пути можно было реально понять пружины
доказательства (формалистика исключительно вредит пониманию
<кухни> и отбивает — по крайней мере на первых порах — спо-
собность к самостоятельному мышлению и проникновению в суть
предмета, без осознания которой вряд ли возможно дальнейшее
творчество), а во-вторых, со столь геометричной ситуацией*) нам
уже столкнуться, по-видимому, не удастся. Познакомившись од-
нажды с глубокой геометрической подоплёкой <многомерной> де-
ятельности и заполучив, тем самым, некий опыт и интуицию, мы
откажемся теперь от чисто геометрической почвы и постараемся
научиться извлекать максимальную пользу из комбинаторной ин-
терпретации задачи.
Для удобства будем называть (0, 1)-векторами в n любые век-
торы, координаты которых могут принимать всего два различных
значения — 0 и 1. В пятимерном пространстве рассмотрим сле-
дующее семейство ? из 16-ти (0, 1)-векторов: в ? лежит вектор
*) При доказательстве нижних оценок.
25
из одних нулей (<начало координат> (0, 0, 0, 0, 0)), все C2 =10
5
векторов с двумя единицами (векторы (1, 1, 0, 0, 0), (0, 1, 0, 0, 1)
и т. д.) и все C4 =5 векторов с четырьмя единицами. Как всегда,
5
мы хотим показать, что ? есть (M, D)-критическая конфигурация
с достаточно большим отношением величины M к величине D,
причём сразу ясно, что M=16. Для нахождения величины D
мы впервые воспользуемся тем обстоятельством, что в качестве
<запрещённого расстояния> в определении хроматического числа
вовсе не обязательно брать единицу. На сей раз мы положим это
v
расстояние равным 2 и сообразно этому будем трактовать само
понятие критической конфигурации.
Очень удобно интерпретировать (0, 1)-векторы и расстояния
между ними в чисто комбинаторных терминах. Для этого полезно
ввести в рассмотрение конечное множество, состоящее из n (в дан-
ном случае n=5) различных элементов. Такое множество мы будем
обозначать Rn и зачастую представлять его себе как отрезок на-
турального ряда (множества всех натуральных чисел): например,
можно считать, что Rn ={1, 2, ..., n} или что Rn ={3, 4, ..., n+2},
и т. д. Если мы захотим уточнить, о каком именно отрезке идёт
речь, мы напишем Ri,j , подразумевая множество {i, ..., j}, т. е.
множество, состоящее из всех натуральных чисел от i до j включи-
тельно. Таким образом, Rn =Ri,i+n?1 , где i — произвольное число,
зависящее от контекста.
Каждому (0, 1)-вектору x=(x1 , x2 , ..., xn ) мы сопоставляем
подмножество M=Mx в Rn ={1, 2, ..., n} по принципу: если xi =
=1, то мы <кладём> i в наше M; иначе — не кладём. Более
формально, M={i?Rn : xi =1}. В результате связь между вектора-
ми и множествами получается взаимно однозначной. Кроме того,
расстояния между векторами однозначно интерпретируются мощ-
ностями пересечений соответствующих множеств и наоборот, т. е.
|x? y|=a тогда и только тогда, когда #(Mx ?My )=b, где между
числами a и b существует известная зависимость.
В частности, векторам из ? отвечают множества из такой со-
вокупности M ={M1 , ..., M16 }, что среди множеств Mi есть ровно
одно (единственно возможное) <пустое> (оно получается из вектора
(0, 0, 0, 0, 0)), ровно 10 (всевозможных) двухэлементных и ров-
но 5 (всевозможных) четырёхэлементных. Запрещённому расстоя-
нию отвечают, в свою очередь, следующие мощности пересечений
(проверьте!):
1) если #Mi =0, #Mj =2, то #(Mi ?Mj )=2;
2) если #Mi =2, #Mj =2, то #(Mi ?Mj )=1;
3) если #Mi =4, #Mj =2, то #(Mi ?Mj )=2;
4) если #Mi =4, #Mj =4, то #(Mi ?Mj )=3.
Исходя из условий 1)—4), простым перебором ситуаций не-
трудно показать, что какова бы ни была подсовокупность мно-
26
жеств M в M , свободная от запрещённых пересечений, мощность
её не будет превосходить двух. В самом деле, достаточно заме-
тить, что M не может одновременно содержать два различных
четырёхэлементных множества (условие 4)), что вместе с пустым
множеством она не может содержать ни одного двухэлементно-
го (условие 1)) и что если в ней имеется четырёхэлементное
множество, то сразу двух двухэлементных множеств в ней уже
не окажется (условия 2) и 3)). Но тогда в силу взаимной однознач-
ности соответствия между множествами и векторами последнее
обстоятельство немедленно влечёт неравенство D?2. Следователь-
но, ?( 5 )?M/D=8, и теорема Лармана—Роджерса доказана.

n )?c n2
Доказательство теоремы Лармана—Роджерса: ? ( 1
и обсуждение методов её усиления
Настало время конкретизировать значение константы c1 , и для
этого мы сформулируем теорему Лармана—Роджерса ещё раз —
в самом точном виде.
Теорема Лармана—Роджерса. Пусть n?2. Тогда имеет место
оценка ?( n )?C3 /n , где, в свою очередь,
n+1
n =n, если n=4q, q? , т. е. n делится на 4 нацело;
n =n?1, если n=4q+1 или n=4q+2, q? ;
n =n+1, если n=4q+3, q? .
Во-первых, очевидно, что в утверждении теоремы исчерпаны
все возможные ситуации, ведь и впрямь либо n=4q, либо n=
=4q+1, либо n=4q+2, либо n=4q+3. Во-вторых, ясно, как
в зависимости от величины остатка при делении n на 4 выгля-
дит c1 . Вернее, можно слегка <огрубить> результат и записать его
в форме
n2
n )? (n+1)n(n?1) ? n(n?1) ?
?(
6n 6 12

(здесь мы использовали тот факт, что, с одной стороны, n ?n+1,
а с другой, n?2 и, стало быть, n(n?1)=n2 ?n?n2 /2). Конечно,
в действительности c1 ?1/6, в то время как мы только что удоволь-
ствовались одной двенадцатой, но это и не столь принципиально:
всё равно реально мы будем применять саму теорему*), вычислять
биномиальный коэффициент и т. д., а c1 (не важно уж, меньше
она одной шестой или нет) есть просто элемент стандартной (более
удобной и короткой) записи.
Перейдём теперь к изложению сути того механизма, который
лежит в основе доказательства неравенств Лармана—Роджерса.
В целом, идея здесь та же, что и в случае с оценкой ?( 5 )?8,

*) См. таблицу оценок при n=10, 12, 13, 14, 15.
27
подробно изученной в предыдущем параграфе. Иными словами,
нам следует, как обычно, воспользоваться концепцией (M, D)-кри-
тической конфигурации с некоторым критическим расстоянием,
причём в качестве искомой конфигурации мы выбираем систему
(0, 1)-векторов с подходящими свойствами. Итак, рассмотрим мно-
жество (n+1)-мерных векторов
?={x=(x1 , ..., xn+1 ):
xi ?{0, 1} ? i=1, ..., n+1; x1 +...+xn+1 =3}.
На первый взгляд, может показаться немного странным то, что,
желая работать с n-мерным евклидовым пространством и, со-
ответственно, с n-мерными конфигурациями, мы тем не менее
рассматриваем систему векторов с числом координат, на единицу
большим ожидаемого. В конечном счёте, формальное объяснение
должно опираться на представление о том, что такое подпро-
странства (<плоскости>) меньшей размерности в n . Кое-какие
понятия подобного рода ещё возникнут в задачах в конце следую-
щего параграфа. Сейчас же, дабы чересчур не заострять внимание
на деталях, можно либо считать, что мы слегка ослабили оценку
и доказываем её не в n , а в n+1 , либо <на пальцах> обосно-
вать n-мерность конструкции, исходя из тех соображений, что
в определении множества ? сумма координат каждого из векторов,
принадлежащих множеству, фиксирована (равна 3) и что, следо-
вательно, одна из координат находится в жёсткой зависимости
от остальных: если вспомнить, что, скажем, на плоскости это бы
означало попадание ? на прямую, а в пространстве — на плос-
кость, то положение дел становится гораздо более ясным.
Дальнейшая деятельность вполне аналогична деятельности
из предшествующей части этой главы. Понятно, что, какое бы
критическое расстояние мы впоследствии ни фиксировали, уж за-
ведомо (для ?) M=C3 , и, таким образом, очевидна природа
n+1
числителя в оценке ?( n ), указанной в теореме. Для отыскания
знаменателя, т. е. величины D в критической конфигурации, нуж-
но, естественно, задаться некоторым запрещённым расстоянием:
положим таковое равным 2. Проинтерпретируем ? посредством
известной нам комбинаторики: возьмём Rn+1 и установим стан-
дартное соответствие между семейством векторов ? и совокуп-
ностью M всех трёхэлементных подмножеств множества Rn+1 .
Тогда запрещённому расстоянию между векторами будет однознач-
но отвечать пересечение множеств по одному общему элементу.
Лемма. Если произвольная подсовокупность множеств M в со-
вокупности множеств M обладает тем свойством, что любые два
множества M1 , M2 , принадлежащие ей, не пересекаются между
собой ровно по одному элементу (т. е. либо #(M1 ?M2 )=2, либо
#(M1 ?M2 )=0), то #M ?n .
28
Доказать лемму не слишком трудно при помощи метода ма-
тематической индукции. Чтобы не загромождать эту брошюру
излишними подробностями, мы не приводим этого доказательства.
Мы надеемся, что заинтересованный читатель постарается обосно-
вать лемму самостоятельно: такая комбинаторика возникнет и при
обсуждении возможностей усиления теоремы Лармана—Роджерса,
так что прочувствовать её полезно. Сама теорема уже фактически
доказана: достаточно лишь заметить, что из леммы и из прямого
соответствия между множествами и векторами вытекает равенство
D=n .
За счёт чего разумно пытаться усиливать полученный ре-
зультат? В принципе, можно было бы надеяться на уточнение
оценки в лемме. Однако на этом пути нас ждёт разочарование:
оценка и без того точна в том плане, что найдётся совокуп-
ность M трёхэлементных подмножеств в Rn+1 , такая, что все
надлежащие ограничения на мощности попарных пересечений её
элементов выполнены и что в то же время #M =n . Примером
A A
n+1 !
!. Тогда
!
может служить следующая конструкция. Пусть t=   4
4t?n+1, а 4(t+1)>n+1, т. е. либо n+1=4t, либо n+1=
=4t+1, либо n+1=4t+2, либо n+1=4t+3. Разобьём R4t =
={1, 2, ..., 4t}?Rn+1 на t последовательных непересекающихся
четырёхэлементных частей R1,4 , R5,8 , ..., R4t?3,4t , а Rn+1 пред-
ставим, соответственно, в виде Rn+1 =R4t ?R, где, в зависимости
от ситуации, #R=i, 0?i?3. Пусть Mj , j=1, 2, ..., t, — это сово-
купность всех (четырёх) трёхэлементных подмножеств множества
R4j?3,4j . Пусть, кроме того, Mt+1 определена тогда и только тогда,
когда #R=3, причём определена она попросту как Mt+1 ={R}
(в Mt+1 ровно один элемент). Тогда M мы положим либо равным
M1 ?M2 ?...?Mt , либо равным M1 ?M2 ?...?Mt+1. Все множества
в M трёхэлементны, попарные их пересечения устроены как по-
ложено, а количество их есть 4t или 4t+1, что, как нетрудно
проверить, совпадает с n *).
Коль скоро лемма нам не помощник и усилить её не удаёт-
ся, нужно искать иной путь к улучшению оценок. Оказывается,
такой путь состоит в обобщении конфигурации ?. Так, например,
результат Лармана 1978 года (?( n )?c2n3 ) использует множество
векторов
?={x=(x1 , ..., xn+1 ): xi ?{0, 1} ? i=1, ..., n+1; x1 +...+xn+1 =5}.
Это множество является v(M, D)-критичной конфигурацией с за-
прещённым расстоянием 6, отвечающим мощности 2 пересечения
*) Мы неявно предполагали, что n+1?4. Однако в меньших размерностях всё
делается вообще мгновенно (убедитесь в этом).
29
пятиэлементных подмножеств Rn+1 , с M=C5 2
n+1 и D?const·n .
Доказательство последнего неравенства получается из аналога лем-
мы, который и обосновывается более или менее схожим образом
(но технически уже совсем нетривиально).
После всего сказанного становится видна общая стратегия
дальнейших возможных усилений описанных оценок. Принято,
в этой связи, рассматривать семейства (0, 1)-векторов вида
?={x=(x1 , ..., xn ): xi ?{0, 1} ? i=1, ..., n; x1 +...+xn =a},
где a=a(n) — произвольное (возможно, зависящее от размерности,
но фиксированное при каждом n) натуральное число, меньшее,
чем n. Здесь M=Ca , а D определяется величиной запрещённого
n
расстояния — тоже неким параметром l=l(n), удовлетворяющим
естественным ограничениям вида l>0 или l?2a и т. д. Понятно,
что зависимость D от l и прочих факторов должна вытекать из лем-
мы, в которой бы максимально точным образом оценивалась сверху
мощность произвольной совокупности a-элементных подмножеств
множества Rn , такой, что любые два множества в ней не имеют
права обладать конкретной мощностью пересечения (эта мощность
пересечения однозначно отвечает значению параметра l, и читате-
лю предлагается самостоятельно вывести формулу, позволяющую
по размерности, числу единичных координат в каждом векторе
конфигурации и запрещённому расстоянию находить запрещён-
ную мощность пересечения). Дабы не оставаться голословными,
мы сформулируем самую сильную в отношении следствий для хро-
матических чисел лемму, которую как раз и доказали в 1981 году
Франкл и Уилсон, обосновав, таким образом, <экспоненциаль-
ность> роста ?( n ). Эта лемма касается векторной конструкции
v
с параметрами a<n/2 и l= 2p, где p — минимальное простое чи-
сло, для которого a?2p<0, т. е. p?a/2*). Ясно, что запрещённое
пересечение тут имеет мощность a?p, т. е. запрещать <полезнее>
всего пересечения, мощность которых приблизительно равна поло-
вине мощности каждого из множеств.
Лемма (теорема Франкла—Уилсона). Если произвольная под-
совокупность множеств M в совокупности M всех a-элементных
подмножеств множества Rn обладает тем свойством, что любые
два множества M1 , M2 , принадлежащие ей, не пересекаются
между собой ровно по a?p элементам, то #M ?Cn . p?1

Ca
n )? M = n
Из леммы немедленно следует оценка ?( p?1 , и, если
D Cn
n )?
максимизировать её по a, то мы и получим неравенство ?(
*) Заметим, что существование простого числа p с указанными свойствами —
факт уже весьма нетривиальный. Его доказательство требует знания сложнейшего
аппарата современной аналитической теории чисел. Для результата Франкла—
Уилсона этот факт принципиален.
30
??1 ·1,207n . На самом деле, для понимания последнего утвер-
ждения необходимо записать биномиальные коэффициенты в виде
x!
выражений Cy = , а затем приближать значения факто-
x y! (x?y)!
риалов за счёт формулы Стирлинга: при достаточно больших x
выполнено соотношение
# Ax
v x!
x!? 2?x  !
!
e
(здесь ??3,1415926 и e?2,718281828 — стандартные константы,
а значок <?> — тоже стандартный — следует понимать в том смы-
сле, что при неограниченном возрастании величины x отношение
факториала к выражению, стоящему справа от значка, становится
всё ближе и ближе к единице, т. е. в некотором роде x! всё менее
и менее отличается от своего приближения)*).
Теорема Франкла—Уилсона (лемма) является одной из <жем-
чужин> комбинаторики (или, дабы быть более точными, <экстре-
мальной теории гиперграфов>**)). Её доказательство уже отнюдь
не основано на методе математической индукции, как это было
с теоремами Лармана—Роджерса и Лармана, оно поистине изящно
и крайне нетривиально в том плане, что, будучи удивительно про-
стым, оно в то же время опирается на столь неожиданную в данном
контексте технику, что не вполне понятно, как вообще авторам
удалось увязать её с искомым результатом. Одна из модификаций
подхода Франкла—Уилсона была даже включена двумя извест-
ными современными математиками М. Айгнером и Г. Циглером
в монографию под названием <Доказательства из КНИГИ>. В этой
монографии воплощена мысль Эрдёша о том, что у Бога есть не-
кая КНИГА, в которой содержатся самые красивые доказательства
математических утверждений и что изредка людям удаётся туда
заглянуть. К сожалению, в рамках нашей брошюры обосновать
лемму нам не удастся: потребовались бы чересчур многочисленные
дополнительные пояснения тех понятий, которые всё же лучше
воспринимаются студентами по крайней мере второго семестра
первого курса. Отсылая заинтересованного читателя к оригиналь-
ным работам и обзорам (см. [1]), мы заметим лишь, что теорема
*) Более аккуратно о формуле Стирлинга можно говорить в терминах теории
пределов. Сейчас же достаточно ограничиться и нестрогим пониманием ситуации.
Попробуйте воспользоваться приведённой методикой, скажем, в случае, когда n=
=4p (p — простое), a=2p?1: к таким параметрам теорема Франкла—Уилсона,
безусловно, применима.
**) Гиперграф — это просто совокупность подмножеств конечного множества,
а эпитет <экстремальный> употреблён из тех соображений, что интересующие нас
задачи предполагают отыскание каких-либо экстремальных (т. е., например, макси-
мальных или минимальных) конструкций и результатов: отыскание максимальной
мощности совокупности с запретами на мощности попарных пересечений её эле-
ментов и др.
31
Франкла—Уилсона возникла далеко не только в связи с изучени-
ем хроматических чисел. Эта теорема есть лишь одна из многих
в ряду тех, что относятся к уже упомянутой экстремальной теории
гиперграфов. Не менее известной в этой науке является, скажем,
теорема Эрдёша—Ко—Радо о том, что если k-элементные подмно-
жества n-элементного множества попарно пересекаются и k?n/2,
то таких подмножеств не может быть больше, чем Ck?1 . Мы n?1
не будем вдаваться в дальнейшие подробности, но ещё раз подчерк-
нём, что описанная комбинаторика весьма красива, многообраз-

<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign