Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2011/01/raigorodsky.pdf Дата изменения: Wed Nov 21 16:11:52 2012 Дата индексирования: Sun Feb 3 06:49:34 2013 Кодировка: Windows-1251 Поисковые слова: п п п п п п п п п п п п п п п

Гипотеза Кнезера и топологический метод в комбинаторике
А.РАЙГОРОДСКИЙ
1. Введение Комбинаторика это один из самых увлекательных разделов современной математики. И один из самых бурно развивающихся. Если еще каких-то 100 лет назад можно было сказать, что комбинаторика это набор красивых, но разрозненных утверждений о перечислении объектов того или иного вида, то сейчас комбинаторика это полноценная дисциплина, которая постепенно вырабатывает свой собственный язык и систему методов, позволяющих собирать воедино все то многообразие задач, которые совсем недавно казались никак не связанными между собой. Когда говорят о комбинаторных методах, обычно вспоминают только метод производящих функций, который действительно играет огромную роль при решении перечислительных задач. Однако не менее значимы в комбинаторике и задачи экстремальные, т.е. задачи отыскания наибольших (наименьших) в том или ином смысле систем объектов. И здесь, конечно, производящие функции ни к чему. Их заменяют инструменты, которые появились буквально в последние десятилетия. Среди них вероятностный метод (см. [1], [2]), активно разрабатываемый с середины ХХ века (во многом благодаря классику венгерской и мировой комбинаторики Полу Эрдешу), линейно-алгебраический метод (см. [3]), возникший и вовсе около тридцати лет назад, и топологический метод метод столь же молодой и в то же время столь же перспективный. В этой статье мы хотим рассказать об исторически первой задаче, которая была решена с помощью топологической технологии. Это так называемая гипотеза Кнезера, сформулированная Мартином Кнезером в 1955 году и доказанная Ласло Ловасом в 1977 году. Пафос в том, что постановка задачи исключительно проста и доступна школьнику, а решение ее выходит далеко за рамки школьной программы. Тем не менее, мы построим статью так, что практически все в ней при желании сможет понять заинтересованный старшеклассник. Наша цель на примере одной конкретной задачи продемонстрировать силу и красоту топологического метода: рассуждение, которое мы в конечном счете проведем, это поистине жемчужина (ср. [4]) комбинаторики, одно из самых элегантных рассуждений в математике, которые известны автору. И значимость его не только в исключительном изяществе, но и в том, что оно как нельзя лучше свидетельствует о единстве математики: зачастую глубокое знание одного предмета позволяет достичь неожиданно ярких результатов в совершенно иной области; именно так возникают методы. Отметим, что имеется прекрасная книга [5], в которой дается обзор некоторых наиболее употребительных топологических методов в комбинаторике. Правда, эта книга довольно сложна для первого чтения. Поэтому весьма полезными будут также книги [6] и [7], по которым можно получить наглядное представление о самой топологии. 2. Попарно пересекающиеся множества и возникновение гипотезы множество Rn = {1,..., n} . Пусть K = K1,..., KCk n совокупность всех k-элементных подмножеств множества Rn . Иными словами, каждое Ki это подмножество множества Rn , имеющее мощность k. Подчеркнем, что каждое подмножество обозначено у нас обычной заглавной буквой K, а совокупность подмножеств обозначена 'красивой' заглавной буквой K . В 1955 году Кнезер установил следующий очень простой факт. n Теорема 1. Пусть k . Тогда совокупность K 2 можно представить в виде объединения n 2k + 2 совокупностей, элементы каждой из которых попарно пересекаются. Иначе говоря, Рассмотрим произвольное натуральное число n и

{

}

K = K1 ... K

n - 2k + 2

,

(1)

причем для любого i {1,..., n - 2k + 2} и любых двух множеств Ka , Kb K i выполнено Ka Kb . n Понятно, откуда взялось условие k . Во-первых, 2 n при k > величина n 2k + 2 становится не больше 2 единицы, что в контексте соотношения (1) нелепо. Вовторых, при таком k любые два множества из самой совокупности K имеют непустое пересечение, так что


и впрямь говорить о каком-либо объединении вида (1) смысла нет. Совокупности, подобные K1,..., K n -2k +2 , т.е. состоящие из попарно пересекающихся множеств, играют огромную роль в самых разных областях комбинаторной математики и ее приложений. Например, их можно интерпретировать как коды со сравнительно небольшим расстоянием Хэмминга между любыми двумя кодовыми словами. В теории кодирования они широко распространены. Доказательство теоремы 1 исключительно легкое, но мы приведем его во всех подробностях. Доказательство теоремы 1. В качестве совокупности K1 возьмем совокупность, состоящую из всех Ka K , которые содержат элемент 1 множества Rn :
K1 = {Ka K :1 Ka } .

3. Небольшой экскурс в теорию графов и переформулировка гипотезы Мы предполагаем знакомство читателя с простейшими понятиями теории графов, которые легко найти, например, в книге [8]. Тем не менее, давайте аккуратно договоримся о том, что такое граф. В этой статье мы будем считать, что у графа не может быть ни петель, ни кратных ребер, ни ориентации. Иными словами, граф это пара G = (V, E), в которой V это конечное множество вершин, а E это любой набор ребер {x, y} , x, y V , с условиями: (i) {x, x} E (нет петель); (ii) / каждая пара {x, y} входит в E не более одного раза (нет кратных ребер); (iii) {x, y} = {y, x} (нет ориентации). Изображать графы мы будем совершенно стандартно точками и соединяющи- Рис. 1 ми их отрезками (или дугами). Скажем, на рисунке 1 приведены примеры некоторых возможных изображений полного графа K4 , т.е. графа, у которого на четырех вершинах присутствуют ('проведены') все возможные шесть ребер. На рисунке 2 указан объект, который мы в дальнейшем графом Рис. 2 считать не будем. Нам понадобятся три тесно связанные между собою 'экстремальные' характеристики графа. Назовем числом независимости графа G = (V, E) величину (G ) , равную размеру самого большого множества вершин графа, внутри которого отсутствуют ребра. Любое такое множество называется независимым, и именно отсюда идет название величины (G ) . На рисунке 3 приведены примеры графов с числами независимости 2 и 3 соответственно. В первом

Очевидно, множества, принадлежащие совокупности K1 , попарно пересекаются как минимум, по элементу 1. Аналогично, положим
K 2 = {Ka K :2 Ka } ,

, K

n -2k +1

= {Ka K : n - 2k + 1 Ka } .

Какие множества из совокупности K еще не задействованы? Разумеется, те, которые целиком содержатся в множестве {n - 2k + 2,..., n} . Это множество имеет мощность 2k 1, и, стало быть, любые два его k-элементных подмножества пересекаются. В итоге мы вольны положить
K
n - 2k + 2

= {Ka K : Ka {n - 2k + 2,..., n}} ,

и теорема 1 доказана. Отметим, что суть доказательства теоремы не изменится, даже если мы потребуем, чтобы для любых i, j {1,..., n - 2k + 2} , i j , было выполнено K i K j = . Просто тогда надо брать
K 2 = {Ka K :2 Ka } \ K1 , K 3 = {Ka K :3 Ka } \ K1 \ K 2 ,...

В этом случае напишем

K = K 1b... b K

n - 2k + 2

,

( 1 )

подчеркивая с помощью значка ' b ', что объединение ( 1 ) теперь дизъюнктное, т.е. его элементы попарно не пересекаются. При всей простоте доказательства теоремы 1 любые попытки уточнить его, т.е. заменить величину n 2k + + 2 на что-либо меньшее, не приводят к успеху, и читатель может сам, вслед за Кнезером, убедиться в этом. Возникает любопытная гипотеза. Гипотеза. Совокупность K нельзя представить в виде объединения n 2k + 1 совокупностей, элементы каждой из которых попарно пересекаются. Это и есть гипотеза Кнезера. Теперь нам предстоит понять, как она связана с теорией графов, почему обычные комбинаторные средства не помогают ее доказать и какую роль в ее доказательстве играет топология.

Рис. 3

случае независимых множеств максимальной мощности 2, во втором 3. Назовем кликовым числом графа G = (V, E) величину (G ) , равную размеру самого большого множества вершин графа, внутри которого проведены все ребра. Это величина, в некотором смысле противоположная числу независимости. Действительно, если в графе G удалить все ребра и провести вместо них все те ребра, которых в G не было, то получится граф G , у которого G = (G ) и G = (G ) . Фактически, (G )

()

()


ГИПОТЕЗА

КНЕЗЕРА

И

ТОПОЛОГИЧЕСКИЙ

МЕТОД

В

КОМБИНАТОРИКЕ

это количество вершин в любом максимальном (по числу вершин) полном подграфе графа G. Именно такой полный подграф и называется кликой в графе. Назовем хроматическим числом графа G = (V, E) величину (G ) , равную минимальному количеству цветов, в которые можно так покрасить все вершины графа, чтобы концы любого ребра имели разные цвета. Из определения видно, что каждый цвет это независимое множество. Таким образом, хроматическое число это еще и наименьшее количество независимых множеств, на которые можно разбить множество вершин графа. Из последнего рассуждения ясно, что имеет место V неравенство (G ) . Действительно, даже если (G ) сделать каждый цвет максимальным по мощности, то эта мощность будет равна (G ) , и, стало быть, даже V в таком случае потребуется цветов. Еще проще (G ) неравенство (G ) (G ) , ведь на покраску всего графа уйдет никак не меньше цветов, чем на покраску любой клики в нем. А на клику нужно столько цветов, сколько в ней вершин. Какое же все это имеет отношение к гипотезе Кнезера? Сейчас мы введем в рассмотрение кнезеровский граф, и все окончательно прояснится. n Итак, пусть по-прежнему n N , k . Назовем 2 кнезеровским граф KGnk = (V, E ) , у которого ,

1 ства {},{2},... Rn . Разумеется, эти множества попарно не пересекаются, так что ребра в графе KGn,1 соединяют каждые две вершины. Иначе говоря, граф KGn,1 это полный граф Kn на n вершинах. Его хроматическое число равно n, и это прекрасно согласуется с гипотезой: ( KGn,1 ) = ( Kn ) = n = n - 2 1 + 2 . n (здесь мы считаем, что число 2 n четно). Тогда кнезеровский граф KGn,n 2 представляет собой паросочетание, т.е. имеет вид графа, изображенного на рисунке 4 (паросочетанием называется набор ребер, никакие два из которых не имеют общих вершин; это своего рода независимое множество ребер). Очевидно теперь, что n KGn,n 2 =2 = n - 2 + 2, 2 2 и это снова подтверждает Рис. 4 гипотезу. Есть еще один симпатичный пример совсем част2 ный, но любопытный. Это граф KG5,2 . У него 10 = C5 вершин, являющихся парами элементов из 1, ..., 5. Если 'правильно' изобразить этот граф, то получится картинка, изображенная на рисунке 5. В теории

Во втором случае k =

(

)

V=K, E=

{{Ka

, Kb } : Ka , Kb K , Ka Kb = } .

Иными словами, вершинами кнезеровского графа служат k-элементные подмножества множества Rn , а ребра кнезеровского графа образованы парами непересекающихся k-элементных подмножеств множества Rn . Независимые множества в таком графе это, конечно же, совокупности, состоящие из попарно пересекающихся множеств Ka K , т.е. в аккурат совокупности типа K1,..., K n -2k +2 . А значит, гипотеза в новых терминах звучит так: хроматическое число кнезеровского неравенство ( KGn,k ) n - 2k + 2 есть тривиальное следствие соотношения ( 1 ), и лишь оценка
( KGn,k ) n - 2k + 2 является предположительной. В ней вся загвоздка. В последующих разделах мы попробуем установить искомое неравенство с помощью стандартных оценок V и (G ) (G ) . Но прежде обсудим (G ) (G ) простейшие примеры кнезеровских графов (с конкретными n и k).

Рис. 5

графа равно n 2k + 2: ( KGn,k ) = n - 2k + 2 . При этом

графов эта картинка хорошо известна. Она называется графом Петерсена. Ясно, конечно, что хроматическое число такого графа равно трем. Верхнюю оценку мы давно знаем: ( KG5,2 ) 5 - 2 2 + 2 = 3 . Нижняя же следует хотя бы из наличия нечетного цикла в нашем графе. О графе Петерсена можно почитать в замечательной книге [8]. 5. Применим оценку (G ) (G

)

4. Несколько простых примеров Есть два некотором первом из графа (т.е. простейших частных случая, которые в смысле противоположны друг другу. В них k = 1. Тогда вершины кнезеровского графа KGn,1 ) суть одноэлементные множе-

Ну, это совсем легко. Действительно, что такое клика в графе KGn,k ? Это, по сути, любой набор попарно непересекающихся k-элементных подмножеств множе- Рис. 6 ства Rn . Естественно, типичная клика выглядит так, как показано на риn сунке 6. И размер ее заведомо не превышает , k


где через [x] мы обозначаем максимальное целое число, не превосходящее x. В итоге имеем неравенство n ( KGn,k ) ( KGn,k ) = . k Абсолютно ничего хорошего. Вместо желаемой оценки вида n 2k + 2 имеем примерно в k раз худший результат. Стоит отметить еще одно любопытное обстоятельn ство. Допустим, k = + 1 . Тогда 3 n ( KGn,k ) = < 3 , k т.е. в кнезеровском графе нет даже треугольников. Тем не менее, мы верим, что хроматическое число такого графа равно
n n n n - 2 + 1 + 2 n - 2 + 1 + 2 = . 3 3 3 Это, на первый взгляд, довольно удивительно: граф без треугольников и со сколь угодно большим хроматическим числом. Что ж, тем интереснее. V (G ) Здесь тоже все легко. Мы ведь отлично знаем, что k -1 ( KGnk ) Cn -1 = K1 (см. доказательство теоремы 1). , А стало быть, самое лучшее, на что мы можем теперь рассчитывать, это оценка

нужны лишь следующие совсем базовые объекты и понятия. Во-первых, нам потребуется пространство R d . Во-вторых, в этом пространстве мы рассмотрим сферу. Сфера это, разумеется, поверхность шара. Если размерность шара естественно считать равной размерности всего пространства, то размерность сферы полагают на единицу меньшей. Скажем, круг на плоскости (в пространстве R 2 ) это двумерное множество, а его граница окружность одномерна: это попросту отрезок со склеенными концами. Посему обозначим шар единичного радиуса в R d через Bd , а его сферу через S d -1 :
2 2 Bd = x = ( x1,..., xd ) : x1 + ... + xd 1 ,

S

d -1

{ = {x

2 2 = ( x1,..., xd ) : x1 + ... + xd =

} 1}

.

6. Применим оценку (G )

В-третьих, назовем A S d -1 открытым множеством, если для любого x A найдется достаточно маленький шарик B с центром в x, у которого все точки, лежащие на сфере, содержатся и в A: B S d -1 A . Назовем A S d -1 замкнутым, если его дополнение до всей сферы открыто. Еще следует иметь представление о плоскостях в многомерных пространствах. Под (гипер)плоскостью мы будем понимать аналог обычной плоскости в R 3 . Если в R 3 любая плоскость задается уравнением ax + +by + cz = m, то в общем случае плоскость это множество

(

)

= {x = ( x1,..., xd ) : a1x1 + ... + ad xd = m} .

( KGn,k

)

k -1 Даже если бы мы доказали, что ( KGn,k ) = Cn -1 , это нам не помогло бы.1 Получается весьма забавная ситуация. Обе известные нам комбинаторные оценки хроматического числа приводят к практически одному и тому же результату. n В первом случае мы имели неравенство ( KGn,k ) . k Во втором случае мы получили неравенство n ( KGn,k ) . С учетом того, что хроматическое число k n всегда целое, можно написать ( KGn,k ) , где k И x это минимальное целое число, не меньшее x. Н Таким образом, вторая оценка только на единицу больше первой, да и то лишь при тех k, которые не делят n. Мало мы приблизились к заветной цели, пора переходить к топологии.

Ck n kn 1 = . - Cn -1 k

7. Теоремы БорсукаУламаЛюстерника Шнирельмана Мы предполагаем знакомство читателя с самыми азами математического анализа. По существу, нам
1 Этот факт верен. Он называется теоремой ЭрдешаКо Радо. Доказательство этой теоремы (не вполне тривиальное) можно найти в книге [2].

В этом смысле прямая на обычной плоскости R 2 это тоже своего рода гиперплоскость в двумерном пространстве. Размерность гиперплоскости равна d 1. В 1930 году Л.А.Люстерник и Л.Г.Шнирельман доказали следующую замечательную теорему. Теорема 2. Пусть A1,..., Ad замкнутые множества на сфере S d -1 , причем S d -1 = A1 ... Ad . Тогда одно из множеств обязательно содержит пару противоположных точек сферы, т.е. существует Ai и такая точка x Ai , что - x Ai . Теорема 2 в случае плоскости (d = 2 ) очень проста, но мы докажем ее в первом параграфе последнего раздела (см. также популярную статью [9]). Уже случай обычного пространства (d = 3) совсем не тривиален. В прекрасной книге [10] содержится элементарное рассуждение, которое доказывает утверждение теоремы 2 при d = 3. Для полноты картины и большей замкнутости изложения мы приведем подобное рассуждение во втором параграфе последнего раздела. Общий случай элементарному изложению не поддается, и мы лишь можем отослать заинтересованного читателя к книге [5]. Теорема 2 в некотором смысле не может быть улучшена. А именно, в ней нельзя заменить d на d + 1. Иными словами, сферу S d -1 можно покрыть d + 1 замкнутым множеством, ни одно из которых не содержит противоположных точек. В третьем параграфе последнего раздела мы расскажем, почему это так при d = 3.


ГИПОТЕЗА

КНЕЗЕРА

И

ТОПОЛОГИЧЕСКИЙ

МЕТОД

В

КОМБИНАТОРИКЕ

Стоит отметить, что из последнего обстоятельства (возможности покрыть сферу d + 1 множеством) возникла знаменитая гипотеза Борсука, о которой есть масса литературы, в том числе популярной: см. [10], [11]. В 1932 году К.Борсук, не зная о работе Люстерника и Шнирельмана, доказал ряд утверждений, равносильных теореме 2. Он исходил из соображений, высказанных незадолго до того С.Уламом. Именно поэтому все вариации на тему теоремы 2 принято сейчас называть теоремами БорсукаУлама (в западной традиции) и теоремами БорсукаУламаЛюстерникаШнирельмана (в российской традиции). Для доказательства гипотезы Кнезера нам потребуется следующий вариант теоремы 2. Теорема 3. Пусть A1,..., Ad множества на сфере S d -1 , причем часть из них замкнута, часть открыта и S d -1 = A1 ... Ad . Тогда одно из множеств обязательно содержит пару противоположных точек сферы, т.е. существует Ai и такая точка x Ai , что -x Ai . Теорема 3 сильнее теоремы 2. В ней мы не предполагаем, что все множества, покрывающие сферу, замкнуты; мы разрешаем им также быть открытыми. Отметим, что случай, когда все множества открыты, равносилен случаю, когда все множества замкнуты. Это не очевидно, и доказательство этого можно найти в книге [5]. В четвертом параграфе последнего раздела мы обсудим еще несколько формулировок, равносильных теореме 2. А в следующем разделе мы приведем поистине удивительное рассуждение, которое с помощью теоремы 3 доказывает гипотезу Кнезера. 8. Доказательство гипотезы Как мы уже говорили, первым гипотезу доказал Л.Ловас в 1977 году. Однако рассуждение, которое мы изложим ниже, предложил в 2002 году студент Джошуа Грин. В разделе 8.1 мы определим ряд вспомогательных понятий, а в разделах 8.2 и 8.3 проведем обещанное рассуждение.
8.1. Вспомогательные понятия

S d -2 . Для случаев d = 2 и d = 3 это наглядно очевидно. В первом случае мы пересекаем окружность с прямой и получаем две точки, но S0 = x R : x2 = 1 = {-1, 1} ,

{

}

и все в порядке. Во втором случае мы получаем окружность, и снова нет проблем. В общем случае картина аналогичная. Любую сферу S d -2 = S d -1 назовем экватором на сфере S d -1 . Множество точек сферы S d -1 , которые лежат по одну сторону от некоторого экватора, назовем полусферой. Если полусфера не включает в себя свой экватор, то она открыта, и мы будем явно говорить о ней как об открытой полусфере. Точку полусферы, которая равноудалена от всех точек соответствующего экватора, назовем эпицентром этой полусферы (рис.7). Для данной точки x S d -1 (открытая) полусфера H ( x ) с эпицентром в точке x задается однозначно. Нам хочется доказать, что ( KGn,k ) n - 2k + 2 . Предположим противное и придем в конечном счете к противоречию. Итак, допустим, ( KGnk ) n - 2k + 1 . , Это означает, что каждой вершине кнезеровского графа (т.е. каждому множеству Ka K ) присвоен некоторый цвет, причем всего цветов (в худшем случае) n 2k + 1 и вершины, соединенные ребром (т.е. множества Ka , Kb K со свойством Ka Kb = ), покрашены в разные цвета. Введем обозначение d = = n 2k + 1 и обозначим цвета, в которые покрашены вершины графа, через 1,..., d . Теперь рассмотрим множество Rn , в котором 'живут' все множества Ka K , служащие вершинами кнезеровского графа. Каждому элементу этого множества мы хотим поставить в соответствие некоторую точку на сфере S d , лежащей в R d +1 . Иными словами, мы хотим заменить множество натуральных чисел Rn = {1,..., n} на множество точек Xn = {x1,..., xn } , считая, что каждому числу i Rn соответствует точка xi . Разумеется, это можно сделать бесконечным количеством способов. Однако мы внесем одно важное дополнительное ограничение. А именно, мы потребуем, чтобы на любом экваторе сферы S d лежало не более d точек из множества Xn . На первый взгляд, требование пугает, и неискушенному читателю должно показаться, что удовлетворить этому требованию очень трудно. В действительности все весьма просто, и мы сейчас попробуем (не вдаваясь, впрочем, в технические детали) создать интуицию того, что 'почти всякое' расположение n точек на сфере S d обладает нужным свойством. Рассмотрим понятный и наглядный пример: положим d = 2 . Тогда n = d + 2k - 1 d + 1 . Скажем, n = 3. Естественно, сейчас речь идет о размещении трех точек на обычной сфере S2 в трехмерном пространстве. Представим себе, что эти три точки мы выбираем наугад. Если угодно, мы закрываем глаза и, повертев пальцем в воздухе, тыкаем в случайную точку сферы (палец 'бесконечно тонкий'). Это точка x1 . Точно так
8.2. Разместим элементы множества R
n

на сфере

Пусть любая гиперплоскость в R d , проходящая через центр сферы S d -1 , т.е. через точку 0 = (0, 0,..., 0 ) . Тогда множество S d -1 представляет собой сферу

Рис. 7


же находим точки x2, x 3 . Давайте подумаем, с какой 'вероятностью' эти точки улягутся на один экватор. Коль скоро точки x1, x2 уже выбраны, они вместе с центром 0 нашей сферы однозначно определяют некоторую плоскость . И окружность S1 = S2 это тот самый единственный экватор, на котором одновременно лежат x1, x2 . Стало быть, если мы хотим, чтобы точка x3 попала на этот экватор, мы вынуждены выбирать ее из одномерного множества. Однако изначально выбор точки x3 ничем ограничен не был, и мы вольны были тыкать в любую точку двумерной сферы. Ясно, что в любом разумном смысле вероятность попадания в одномерное подмножество при случайном выборе из двумерного множества равна нулю. Таким образом, мы и впрямь можем утверждать, что вероятность размещения трех точек на сфере S2 c условием, что все они не лежат на одном и том же экваторе, равна единице. А это и значит, по сути, что почти любое расположение точек x1, x2, x 3 нас устраивает. Очевидно, при n > 3 рассуждение по-прежнему в силе. В общем случае работают совершенно аналогичные соображения. Ключевой момент ведь был в том, что любые три точки в R 3 однозначно задают плоскость. Так вот, в R d +1 , где разворачиваются наши события, любые d + 1 точек однозначно задают гиперплоскость. А это нам и нужно.
8.3. Применим теорему 3

Итак, мы выбрали на сфере S d множество точек Xn , и никакие d + 1 точек из Xn не лежат на одном экваторе. При этом Xn находится во взаимно однозначном соответствии с Rn . Это, в частности, означает, что каждому множеству Ka K однозначно соответствует множество La Xn , имеющее мощность k. При этом мы можем считать, что La покрашено в тот же цвет, что и Ka , и, более того, если La Lb = , то и цвета множеств La , Lb различны. Сейчас будет основной трюк. Мы чудесным образом увяжем все, о чем до сих пор шла речь, с теоремой 3. Для этого нам нужно будет покрыть сферу S d некоторыми множествами A1,..., Ad +1 , часть из которых замкнута, а часть открыта. Что ж, за дело. Пусть x S d . Рассмотрим открытую полусферу H ( x ) с эпицентром в точке x. Если в H ( x ) содержится меньше k точек из множества Xn , то скажем, что точка x принадлежит множеству Ad +1 . Если же m = = H ( x ) Xn k , то в множество H ( x ) Xn попаk дает s = Cm множеств La1 , La2 ,..., Las . У каждого из них

ные пересечения. Однако очевидно, что S d = A1 ... Ad +1 , и наличие пересечений нас не смущает. Надо еще понять, какие из множеств A1,..., Ad +1 замкнуты, а какие открыты. Пусть точка x принадлежит любому из множеств Ai, i {1,..., d} . Это Рис. 8 значит, что H ( x ) Xn представляет собой конечное множество точек U на сфере, причем, безусловно, U вложено в открытое множество H ( x ) . Если взять точку x S d , достаточно близкую к x, то нетрудно понять, что H ( x ) целиком накроет множество U. Наглядная иллюстрация этому факту дана на рисунке 8. Суть в том, что точки из U не лежат на экваторе полусферы H ( x ) . Именно поэтому можно столь мало пошевелить полусферу, чтобы и после этого шевеления точки из U не вышли на новый экватор или за его пределы. Таким образом, любая точка x , близкая (в известном смысле) к точке x, принадлежит тому же множеству Ai , что и x. Следовательно, множества Ai , i {1,..., d} , открыты. В то же время вся сфера S d замкнута, а значит, множество Ad +1 = S d \ ( A1 ... Ad ) тоже замкнуто (как разность замкнутого и открытого множеств). Применим теорему 3. Она говорит, что в одном из множеств A1,..., Ad +1 есть пара противоположных точек x и -x . Рассмотрим два случая: в первом случае x Ai , где i {1,..., d} ; во втором случае x Ad +1 . Случай 1. В этом случае полусферы H ( x ) и H ( - x ) содержат множества La и Lb соответственно, каждое из которых имеет цвет i (раз уж и x, и -x сидят в одном и том же Ai ). Но полусферы H ( x ) и H ( -x ) не пересекаются (они ведь не содержат общего экватора), а стало быть, не пересекаются и множества La , Lb . Так ведь у нас непересекающиеся множества не могут быть одного цвета! Противоречие. Случай 2. В этом случае H ( x ) Xn k - 1 и H ( - x ) Xn k - 1 . Обозначим через S общий экватор полусфер H ( x ) и H ( -x ) . Тогда
S Xn = Xn - H ( x ) Xn - H ( - x ) Xn
n - (k - 1) - (k - 1) = n - 2k + 2 = d + 1 ,

есть свой цвет j , j {1,..., d} . Соответственно, скажем, что точка x принадлежит множеству Aj с каждым из индексов j, участвующих в упомянутой раскраске. Формально можно написать так:

Ad

+1

= x S d : H ( x ) Xn < k ,
n i

Ai = x S :в H ( x ) X
d

{

{

}

т.е. на экваторе S лежит не меньше d + 1 точек, что также невозможно. Опять противоречие, и гипотеза Кнезера доказана. 9. Дополнение Для понимания этого раздела потребуется слегка больше навыков, чем прежде. Например, необходимо знать определения непрерывной функции и непрерывного отображения. Следует знать также, что непрерыв-

есть подмножество La цвета

}

при i = 1,,d.

Разумеется, множества A1,..., Ad могут иметь взаим-


ГИПОТЕЗА

КНЕЗЕРА

И

ТОПОЛОГИЧЕСКИЙ

МЕТОД

В

КОМБИНАТОРИКЕ

ная функция достигает своего максимального (минимального) значения на замкнутом множестве. Понадобится представление о связности множеств. Но это и все, пожалуй.
9.1. Доказательство теоремы 2 при d = 2

Пусть окружность S1 покрыта двумя замкнутыми множествами A1, A2 , не содержащими противоположных точек. Возьмем некоторую точку x A1 . Тогда -x A2 . На любой из дуг, соединяющих точки x и -x , найдем последнюю точку y множества A1 . Это можно сделать, поскольку A1 замкнуто и - x A1 . Ясно, что y лежит и в A2 , ведь иначе за ней были бы еще точки множества A1 . Но тогда - y не может принадлежать ни A1 , ни A2 . Противоречие, и теорема доказана.
9.2. Доказательство теоремы 2 при d = 3

Предположим, S2 = A1 A2 A3 , причем все множества Ai замкнуты и, вопреки утверждению теоремы, ни одно из них не содержит пары противоположных точек сферы. Наша цель прийти к противоречию. Разобьем сферу на очень маленькие кирпичики и две шапочки, как показано на рисунке 9. Чуть позже мы скажем, что именно означает выражение 'очень маленькие'. Все кирпичики одинаковы, шапочки тоже совпадают по форме, и для дальнейшего крайне важно, Рис. 9 что мы располагаем кирпичики на сфере в стиле обычной кирпичной кладки: мы будем существенно опираться на то, что ни в одной точке сферы не сходятся сразу четыре отрезка, служащие границами кирпичиков (ситуация, показанная на рисунке 10, невозможна). Объединим все кирпичики, каждый из которых имеет хотя бы одну общую точку с множеством A1 . Полученное множество назовем B1 . Аналогично поступим с A2 и A3 , образуя множества B2 и B3 соответственно. Поскольку множества Ai замкнуты, то, выбрав кирпичики с самого начала достаточно мелкими, мы добьемся того, что и множества Bi не будут содержать противоположных точек сферы. Разумеется, S2 = B1 B2 B3 . Рассмотрим пока только множество B1 . Его граница это система ломаных линий на сфере. Назовем эти ломаные L1,..., Lk , где k это просто обозначение для числа наших ломаных. Благодаря способу укладки кирпичиков на сфере, мы можем утверждать, что любая из ломаных замкнута, не пересекает саму себя и не пересекается ни с одной из оставшихся ломаных. Именно ради этого мы так старательно избегали ситуаций, показанных на рисунке 10. В итоге граница множества B1 имеет весьма приятный вид, Рис. 10 чего нельзя было сказать, вообще-то, о гра-

нице исходного множества A1 . Затевая кирпичную кладку и заменяя A1 на B1 , мы как раз стремились к тому, чтобы от одного замкнутого множества без противоположных точек перейти к другому замкнутому множеству без противоположных точек, улучшив при этом свойства границы множества. Отразим множество B1 относительно центра сферы. Получится множество B1 , которое не пересекается с множеством B1 , так как иначе в B1 нашлись бы противоположные точки сферы. Граница множества B1 образована лома ными L1,..., Lk , которые симметричны ломаным L1,..., Lk . Итого у нас на сфере есть уже 2k ломаных, которые замкнуты, не пересекают самих себя и не пересекаются друг с другом. Хорошо известно, что такие ломаные делят Рис. 11 сферу на 2k + 1 связных кусков. Этот факт интуитивно понятен: одна замкнутая ломаная разбивает сферу на два куска, две замкнутые ломаные разбивают сферу на три куска и т.д. В действительности, этот факт крайне нетривиален, ведь замкнутая ломаная может быть сколь угодно сложной (рис.11). Он называется теоремой Жордана. Однако мы применим этот факт, по-прежнему надеясь на интуицию читателя. Итак, на сфере есть 2k + 1 связных множеств, которые ее покрывают. По построению, среди этих множеств могут быть либо пары множеств, симметричных друг другу, либо множества, которые симметричны относительно центра сферы. Поскольку 2k + 1 нечетное число, хотя бы одно центрально-симметричное множество найдется. Назовем его C. Ясно, что C ( B2 B3 ) . В множестве C есть, конечно, пары противоположных точек сферы. Возьмем любую из них: скажем, y и - y . Ввиду связности множества C, существует непрерывная кривая , соединяющая точки y и - y и целиком лежащая внутри множества C. Дальнейшее рассуждение полностью повторяет рассуждение из параграфа 9.1: непрерывная кривая это точный аналог дуги окружности, и она покрыта только множествами B2 и B3 . Приходим к противоречию, и теорема доказана.
9.3. Покрытие окружности и двумерной сферы

Здесь мы хотим разобраться с тем, как можно покрыть окружность S1 тремя, а сферу S2 четырьмя замкнутыми множествами без противоположных точек. С окружностью все тривиально. Покрытие имеет вид значка 'Мерседеса', и оно изображено на рисунке 12. Очевидно, что в каждом из секторов нет противоположных точек. Более того, максимальное расстояние между парами точек в любом из секторов (оно называ-


ется диаметром сектора) равно 3 , и это, разумеется, намного меньше 2 (диаметра окружности). На значок 'Мерседеса' можно посмотреть и по-другому. А именно, его можно получить так: вписываем в S1 правильный треугольник со сто3 , 'смотрим' роной Рис. 12 из центра окружности на каждую из сторон треугольника и получаем те самые три сектора, которые покрывают S1 . Последнее рассуждение полезно с той точки зрения, что в случае R 3 мы его обобщим, и, тем самым, трехмерная конструкция окажется понятнее. Итак, впишем в S2 правильный тетраэдр, служащий естественным аналогом правильного треугольника. Посмотрим из центра на каждую из его четырех граней. Получатся трехгранные углы с общей вершиной в центре сферы (рис. 13). Каждый из углов имеет в сечении одну из граней тетраэдра. Пересечения углов со сферой и суть искомые четыре замкнутых множества, покрывающие сферу. Ясно, что все эти множества геометрически одинаковы. В сущности, ясно и то, что Рис. 13 такие множества не содержат противоположных точек сферы. Интереснее подсчитать их диаметры. Заметим, что в случае плоскости диаметры искались тривиально: максимум расстояний в секторах достигался на парах вершин вписанного треугольника. Возникает гипотеза, что и в трехмерной ситуации следует просто найти длину стороны тетраэдра. Однако такая интуиция неверна, и это здесь самое забавное. Дабы описать положения наиболее удаленных точек данного множества в покрытии сферы, введем некоторые обозначения. Пусть вершины тетраэдра это A1, A2 , A3, A4 , а его центр это O (см. рис. 13). Для определенности рассмотрим множество, порожденное трехгранным углом OA1 A2 A3 . Пусть B середина стороны A2 A3 . Проведем через точку B радиус OC. Утверждение состоит в том, что диаметр это длина отрезка AC . Мы не станем доказывать этот неслож1 ный факт, оставляя читателю хорошую пищу для размышлений. Посчитать длину отрезка AC большого труда не 1 составляет. Давайте все же проделаем это. Прежде всего найдем длину x стороны тетраэдра. Рассмотрим высоту тетраэдра, опущенную из вершины A4 на

плоскость A1 A2 A3 . Обозначим ее основание через D. Понятно, что D центр окружности, описанной вокруг x треугольника A1 A2 A3 . Длина отрезка DA1 равна 3 (по теореме косинусов). Значит, высота A4 D имеет длину
x2 2 =x (по теореме Пифагора). 3 3 x2 В то же время OD = 1 - . В итоге 3 x2 - x 2 x2 = 1+ 1- , 3 3

так что x = 2

2 1 и OB = . 9 3 Мы знаем длины всех сторон треугольника OA1B 1 ( OA1 = 1 , OB = , AB = 2 ). По теореме косинусов 1 3 1 косинус угла AOB равен - . 1 3 Берем треугольник AOC и по теореме косинусов 1 находим AC = 2 1 3+ 3 1, 776 ... < 2 . 6

2 . 3 Далее, по теореме Пифагора DB =

9.4. Вокруг теоремы 2

Полезно понимать, что следующая формулировка равносильна утверждению теоремы 2. Теорема 4. Для любого непрерывного отображения f: S d R d существует точка x S d с f ( -x ) = f ( x ) . В двумерном случае теорема 4 говорит о том, что нельзя непрерывно растянуть обычную сферу на обычную плоскость, не склеив при этом какие-нибудь две противоположные точки. Интуитивно это довольно понятно, а доказательство, по очевидным причинам, то же самое, что и в параграфе 9.2. Ниже мы объясним, как из теоремы 4 вывести теорему 2. Рассуждение в обратную сторону мы предложим читателю в качестве упражнения. Итак, пусть теорема 4 верна. Рассмотрим произвольное покрытие S d = A1 ... Ad +1 сферы замкнутыми множествами. Нам хочется доказать, что найдется индекс i и такая точка x Ai , что - x Ai . Построим отображение f: S d R d по следующему правилу:
f ( x ) = (dist ( x, A1 ),..., dist ( x, Ad
y Ai

))

.

Здесь x S d , а dist ( x, Ai ) = min x - y (минимум достигается, поскольку множество Ai замкнуто). Очевидно, отображение f непрерывно. Из теоремы 4 мы, стало быть, знаем, что для некоторой точки y S d выполнено f ( y ) = f ( -y ) . Если i-я координата точки y равна нулю, то dist ( y, Ai ) = 0 , т.е. y Ai , а значит, и


ПРОГУЛКИ

С

ФИЗИКОЙ

- y Ai . Если же все координаты у точки y ненулевые, то y не принадлежит ни одному из множеств Ai , i {1,..., d} , т.е. y Ad +1 . Но тогда и - y Ad +1 . В обоих случаях все доказано. Назовем отображение f: S d R d антиподальным, если f непрерывно и для любого x S d выполнено f ( -x ) = - f ( x ) . Вот еще один важный вариант теоремы 2: Теорема 5. Не существует антиподального отображения f: S d S d -1 . Равносильность теорем 5 и 4 почти тривиальна, и мы ее не обсуждаем. Зато, отталкиваясь именно от теоремы 5, очень удобно получать обобщения результата БорсукаУламаЛюстерникаШнирельмана. Одно из таких (наиболее широких и важных) обобщений мы приведем ниже, не комментируя терминологию, которая в его рамках возникает. Читатель, знающий продвинутую алгебру, поймет, о чем речь, а читатель, который с подобными вопросами еще не знаком, получит стимул к дальнейшему изучению науки. Теорема 6. Пусть G нетривиальная конечная группа, которая действует свободно на топологических пространствах X и Y. Предположим, что X это (n 1)-связное пространство, а размерность пространства Y равна m < n. Тогда не существует G-эквивариантного отображения из X в Y. Следовало наложить некоторые дополнительные ограничения на пространства X, Y в формулировке теоремы, но мы не стали этого делать, дабы совсем уж не загромоздить утверждение. Можно считать, что X и

Y 'достаточно хорошие'. Например, если X = S n , а Y = Sm , то X имеет связность n 1, а Y имеет размерность m . Если к тому же G = Z2 , то G-эквивариантность и антиподальность отображения суть одно и то же. Таким образом, при X = S n , Y = = S n -1 , G = Z2 теорема 6 влечет теорему 5. Список литературы 1. Н.Алон, Дж.Спенсер. Вероятностный метод. М.: Бином, Лаборатория знаний, 2007. 2. А.М.Райгородский. Вероятность и алгебра в комбинаторике. М.: МЦНМО, 2008. 3. А.М.Райгородский. Линейно-алгебраический метод в комбинаторике. М.: МЦНМО, 2007. 4. А.Я.Хинчин. Три жемчужины теории чисел. М.: Наука, 1979. 5. J.Matouek. Using the Borsuk Ulam theorem. Universitext, Springer, Berlin, 2003. 6. Н.Стинрод, У.Чинн. Первые понятия топологии. М.: Мир, 1967. 7. В.Г.Болтянский, В.А.Ефремович. Наглядная топология. М.: Наука, 1982. 8. Ф.Харари. Теория графов. М.: Мир, 1973. 9. М.Г.Крейн, А.А.Нудельман. Теорема Борсука Улама, или Кое-что о погоде, о дрессированной лошади и двумерных полях. Квант, 1983, ?8, с.2025. 10. В.Г.Болтянский, И.Ц.Гохберг. Теоремы и задачи комбинаторной геометрии. М.: Наука, 1965. 11. А.М.Райгородский. Проблема Борсука. М.: МЦНМО, 2006.

ПРОГУЛКИ С ФИЗИКОЙ Как увидеть 50 Гц?
(Начало см. на 4-й странице обложки) Подсоедините к контактам '+' и '' светодиода два тонких изолированных провода длиной около двух метров каждый и скрутите их. Утяжелите светодиод чем-нибудь и прикрепите середину скрученного провода, например, к книжной полке. Вы получите светодиодный маятник длиной 1 м. Теперь свободные концы проводов, идущих от светодиода, подсоедините к источнику переменного тока частотой 50 Гц и напряжением 34 В, светодиод начнет светиться. Однако светодиод, как и любой другой диод, пропускает ток только в одном направлении, т.е. 10 мс он светится, а

Рис. 2 следующие 10 мс нет. Чтобы увидеть мелькание светодиода с частотой 50 Гц, достаточно раскачать светодиодный маятник. Как только скорость маятника станет выше 1 м/с, вы увидите светящуюся пунктирную линию, вместо сплошной. Особенно хорошо это видно в темноте. На рисунках 1 и 2 приведены фотографии части траектории такого светодиодного маятника, сделанные с экспозицией 0,5 с. Горизонтальный размер этого участка траектории составляет 0,8 м. Нетрудно убедиться в том, что средняя скорость маятника на рисунках равна 1,6 м/с и 2,2 м/с. К.Богданов

Рис. 1