WWW.DISSERS.RU

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

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


Pages:     || 2 | 3 | 4 | 5 |   ...   | 7 |
Библиотека <Математическое просвещение> Выпуск 28 А. М. Райгородский ХРОМАТИЧЕСКИЕ ЧИСЛА Издательство Московского центра непрерывного математического образования Москва • 2003 УДК 519.1 ББК 22.15 Р18 Аннотация В сороковые годы XX века известными математиками П. Эрдёшом и Г. Хадвигером была поставлена одна из самых коротко формулируемых и в то же время одна из самых ярких и трудных задач комбинаторной геометрии — задача о нахождении хроматического числа ( n) евклидова пространства n, т. е. минимального числа цветов, в которые можно так раскрасить точки пространства, чтобы точки, отстоящие друг от друга на расстояние 1, оказались раскрашенными в разные цвета.

Эта задача до сих пор не решена даже для n=2, т. е. для плоскости, хотя простотой и естественностью своей постановки она сразу привлекла внимание всех математиков. К настоящему времени разработано много интересных и остроумных подходов к её (пока частичному) решению.

Текст брошюры представляет собой запись лекции, прочитанной автором 7 декабря 2002 года на Малом мехмате МГУ для школьников 9—11 классов.

Брошюра рассчитана на широкий круг читателей, интересующихся математикой: школьников старших классов, студентов младших курсов, учителей.

Издание осуществлено при поддержке Московской городской Думы и Департамента образования г. Москвы.

ISBN 5-94057-121-2 © Райгородский А. М., 2003.

© МЦНМО, 2003.

Андрей Михайлович Райгородский.

Хроматические числа.

(Серия: <Библиотека,,Математическое просвещение“>. Вып. 28).

М.: МЦНМО, 2003. — 44 с.: ил.

Редактор Г. А. Колюцкий.

Техн. редактор М. Ю. Панов. Корректор Т. Л. Коробкова.

Лицензия ИД № 01335 от 24/III 2000 года. Подписано к печати 10/X 2003 года.

1 Формат бумаги 6088 /. Офсетная бумага № 1. Офсетная печать.

16 Физ. печ. л. 2,75 + 0,50 (вкл.). Усл. печ. л. 3,18. Уч.-изд. л. 3,45. Тираж 3000 экз.

Заказ 3923.

Издательство Московского центра непрерывного математического образования.

121002, Москва, Г-2, Бол. Власьевский пер., 11. Тел. 241 05 00.

Отпечатано с готовых диапозитивов в ФГУП <Производственно-издательский комбинат ВИНИТИ>.

140010, г. Люберцы Московской обл., Октябрьский пр-т, 403. Тел. 554 21 86.

ВВЕДЕНИЕ Задачу, о которой мы хотим рассказать в этой брошюре, принято относить к разделу математики, называемому <комбинаторной геометрией>. Само по себе название раздела уже носит, по-видимому, довольно интригующий характер. В самом деле, взятые в отдельности, слова <комбинаторика> и <геометрия> понятны многим. Однако их сочетание выглядит, быть может, немного неожиданно, и потому следует сперва пояснить, о чём идёт речь.

Очень трудно дать общее и вместе с тем исчерпывающее определение того, что представляет из себя та или иная область математики. За последние десятилетия математика ушла столь далеко на пути абстракции и разделы её столь сильно переплелись между собой, что не всегда возможно чётко разграничить их. Поэтому мы не будем стремиться здесь к какой-либо всеобщности. Мы только ограничимся более или менее ёмкой формулировкой, а также приведём небольшую историческую справку, которая и будет призвана в максимальной мере прояснить ситуацию.

Итак, говоря предельно кратко, комбинаторная геометрия — это часть математики, изучающая различные вопросы, которые, с одной стороны, имеют совершенно геометрическую постановку (скажем, касаются взаимного расположения фигур и точек на плоскости), а с другой стороны, легко поддаются комбинаторной интерпретации. Термин <комбинаторная геометрия> восходит, вероятнее всего, к работам выдающегося специалиста в области соответствующих задач Гуго Хадвигера*), и с этим именем мы ещё будем встречаться в дальнейшем. Конечно, термин появился, как это обыкновенно и бывает, позже задач, и классическими примерами последних являются: знаменитая проблема Борсука о разбиении множеств на части (1933), проблемы, связанные с так называемой теоремой Хелли (1913), задача освещения границы выпуклого тела (1957), з а д а ч а о х р о м а т и ч е с к и х ч и с л а х и др. Именно последнюю из перечисленных задач мы и обсудим в этой брошюре.

У задачи о хроматических числах, к формулировке которой мы перейдём лишь в следующей главе, авторов было несколько. Вопервых, ещё в начале сороковых годов XX века её поставили замечательные математики Гуго Хадвигер и Пол Эрдёш**), во-вторых, независимо от Эрдёша и Хадвигера ей занимались приблизительно в то же время Е. Нелсон и Дж. Р. Исбелл. В сороковые годы шла Мировая война, и этим обстоятельством обусловлен тот факт, что поначалу хроматические числа не вызвали слишком бурного *) Г. Хадвигер (1908—1981) — известный немецкий математик.

**) П. Эрдёш (1913—1996) — выдающийся венгерский математик, автор более чем полутора тысяч статей, один из создателей современной венгерской математической школы, а также автор множества известных — и ныне уже ставших классическими — задач комбинаторики, геометрии, теории чисел и теории множеств.

интереса. Потребовалось около 15 лет, чтобы положение изменилось кардинально: после работы Хадвигера 1961 года, посвящённой нерешённым задачам, хроматические числа стали активно изучаться, и за прошедшие с тех пор десятилетия соответствующая наука сделалась одной из самых популярных математических дисциплин в мире. Задачей Эрдёша—Хадвигера занимались многие известные математики, о ней написаны сотни прекрасных статей, имеются монографии, и всё же проблема столь нетривиальна и глубока, что и по сей день остаётся немало неисследованных вопросов, которые связаны с ней и которые, несомненно, поддаются изучению. В этой брошюре мы постараемся дать введение в проблематику: поставим задачу, обсудим ряд ярких и важных результатов, сформулируем некоторые из нерешённых вопросов.



ПОСТАНОВКА И РЕШЕНИЕ ЗАДАЧИ В ОДНОМЕРНОМ СЛУЧАЕ Рассмотрим обыкновенную вещественную прямую, т. е. множество всех вещественных (действительных) чисел, которое принято обозначать или же 1, подчёркивая в последнем случае, что эта прямая одномерна*). Точки на прямой суть действительные числа x, y и т. д., а расстояние между этими точками определяется естественно — как |x-y|. Заметим, что в определении хроматического числа (в данном случае хроматического числа прямой) понятие расстояния будет играть одну из основных ролей.

Определение. Хроматическим**) числом прямой называется величина ( 1), равная минимальному количеству цветов, в которые можно так раскрасить все точки 1, чтобы расстояние между точками одного цвета не могло оказаться равным единице.

Точек на прямой, разумеется, бесконечно много, и, на первый взгляд, определение может показаться не совсем понятным.

Однако, в действительности, если речь идёт о раскраске какого-нибудь множества в несколько цветов, то подразумевается попросту, что это множество представляется в виде объединения своих непересекающихся частей, которым и присваиваются в дальнейшем <цвета>. В нашем случае это можно символически записать так:

1=V1V2...V, (1) где для любой пары индексов i, j (1i, 1j, i=j) выпол *) Интуитивное понятие о размерностях 1, 2 и 3 имеется у каждого из нас; однако в математике используется также и абстрактное (т. е. отвлечённое от повседневной интуиции) понятие размерности, которое позволяет говорить о <четырёхмерных>, <пятимерных>, и даже <бесконечномерных> пространствах. Некоторое представление об этом понятии мы постараемся дать позже, когда речь пойдёт о хроматических числах в <большой размерности>.

**) Слово <хроматический> греческого происхождения; в переводе на русский язык оно означает <цветной>.

няется условие ViVj= (пересечение Vi и Vj пусто). Тем самым, величина ( 1) есть, по сути, наименьшее число, при котором существует равенство (1) с дополнительным свойством: какова бы ни была часть множества вещественных чисел Vi (1i) и каковы бы ни были точки x, y, принадлежащие этой части, расстояние между этими точками не должно равняться единице (|x-y|=1).

Коль скоро определение дано, возникает вопрос: а почему, собственно, мы запрещаем точкам одного цвета находиться именно на расстоянии 1 друг относительно друга Чем единица лучше любого другого вещественного числа и почему бы нам не взять, скажем, число в качестве величины <запрещённого> расстояния Ответ практически очевиден: дело в том, что никакой разницы между числами 1 и с точки зрения определения величины ( 1) нет, и единица фигурирует в определении исключительно для красоты. Иными словами, значение ( 1) вовсе не зависит от того, какое положительное число мы взяли за величину запрещённого расстояния, так как, имея раскраску 1=V1V2...V, в которой между точками одного цвета не может быть расстояния a>0, мы с лёгкостью преобразуем её в раскраску 1=W1W2...W, в которой нет одноцветных точек на расстоянии b>0: для этого мы каждую часть Vi <раздуваем> (или <сжимаем>) в b/a раз, получая, в конечном счёте, новую часть Wi.

-5 -4 -3 -2 -1 0 1 2 3 4 Рис. Задача Эрдёша—Хадвигера ставится теперь очень просто: нужно отыскать значение величины ( 1). Понятно сразу, что ( 1) 2, поскольку одного цвета заведомо не хватит: на всей прямой сколько угодно пар точек, удалённых друг от друга на расстояние 1. Однако это ещё не есть искомое решение, ведь сходу мы даже не знаем, конечно ли наше хроматическое число. Нужно, стало быть, попытаться придумать какую-нибудь (<хорошую>) раскраску прямой, которая бы использовала как можно меньшее количество цветов. Эта раскраска изображена на рис. 1, и имеет она следующий вид: 1=V1V2, где + + V1= [2i, 2i+1), V2= 1\V1= [2i-1, 2i).

i=- i=Ясно, что эта двухцветная раскраска обладает надлежащим свойством, и, следовательно, мы получили теорему:

Теорема I. Имеет место точное равенство ( 1)=2.

Итак, в случае прямой задача Эрдёша—Хадвигера и ставится, и решается очень легко. В следующем параграфе мы займёмся этой задачей для случая плоскости и убедимся в том, что уже тогда сложность её возрастёт принципиально.

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





Как и прежде, хроматическое число мы обозначим греческой буквой, только теперь будем писать ( 2). Естественно, задача Эрдёша—Хадвигера и здесь состоит в нахождении величины.

Лёгкость, с которой мы добились успеха в решении <одномерной> задачи, наводит на мысль, что и в случае плоскости дела будут обстоять довольно хорошо. Тем более обескураживающе выглядит следующий набор результатов: несмотря на популярность задачи и на все усилия, которые были в различное время приложены многими замечательными специалистами по комбинаторной геометрии, известны лишь две весьма прозрачных по своему доказательству классических теоремы сорокалетней давности.

*) Двумя чертами слева выделены тексты упражнений для самостоятельного решения.

**) Вообще-то, в математике существует расширенное представление о том, что такое расстояние или, как говорят, <метрика>. В одной из заключительных частей брошюры мы скажем несколько слов об этом и о том, как трансформируется понятие хроматического числа в зависимости от того, каким определением расстояния пользоваться.

Теорема II. Имеет место неравенство ( 2)4.

Теорема III. Имеет место неравенство ( 2)7.

Иными словами, на плоскости не только не найдено хроматическое число, но даже <зазор> между имеющимися оценками весьма велик. Теорема II была доказана в 1961 году братьями Мозерами, а теорема III принадлежит Хадвигеру A1 1 A(1961 год). Обе они отнюдь не сложны, и мы дадим их полные доказательства.

Дока з ат е льс т во т е оре мы II.

1 В основе доказательства лежит замечатель- A5 Aная точечная конфигурация, предложенная братьями Мозерами и внешне слегка A2 11 Aнапоминающая веретено, в связи с чем 1 она и носит название <мозеровского веретена> (рис. 2). В самом деле, можно представлять себе, что точки A1, A2, A3, AA4 образуют <иглу>, составленную из правильных треугольников с длиной стороРис. ны 1, симметричных относительно общего основания A2A3. То же самое можно сказать и о точках A4, A5, A6, A7: это тоже <игла>, имеющая общую вершину A4 с первой иглой и повёрнутая так, чтобы между вершинами A1 и A7 обеих игл натягивалась <ниточка> длины 1.

Рассмотрим множество A вершин веретена — точки A1, A2,...

..., A7. Непосредственным перебором ситуаций может быть доказана Лемма. Каковы бы ни были три различные точки Ai, Aj, AkA, среди них найдётся пара точек (назовём их A и B), таких, что |A-B|=1.

Допустим, что плоскость удалось раскрасить в три цвета. Тогда и точки множества A отнесены к не более чем трём цветам. Значит, найдутся три точки Ai, Aj, AkA, имеющие один и тот же цвет (иначе количество точек во всём A не могло бы равняться семи), и, следовательно, в силу леммы, две из них окажутся на расстоянии 1, что противоречит определению хроматического числа. Таким образом, наше допущение неверно, ( 2)4, и теорема II доказана.

Разобранное доказательство, основываясь на его главной идее, можно вложить в более широкий контекст. Действительно, для получения оценки ( 2)4 мы пользовались исключительно свойствами некоторой конечной точечной конфигурации — мозеровского веретена. Дадим следующее определение.

Определение. Множество точек A на плоскости называется (M, D)-критической конфигурацией, если мощность множества A (т. е. число элементов в A ; мощность множества X обычно обозначают через #X ) равна M и в то же время в любом подмножестве F множества A, таком, что #F =D+1, найдётся пара точек F1, Fна расстоянии 1.

Определение устроено так, чтобы всякая (M, D)-критическая конфигурация обладала свойством, аналогичным тому, которое было доказано в лемме для мозеровского веретена. Это попросту означает, что веретено является (M, D)-критической конфигурацией с M=7 и D=2, а понятие критической конфигурации в целом есть прямое обобщение конструкции братьев Мозеров. Если из леммы мы вывели оценку ( 2)4, то в точности те же рассуждения при наличии какой-нибудь (M, D)-критической конфигурации позволяют доказать неравенство ( 2)M/D в предположении, что M делится на D нацело, и неравенство ( 2)[M/D]+1 в противном случае (здесь через [a] обозначена целая часть числа a, и, в частности, для веретена [M/D]+1=4).

На первый взгляд, совершенно удивительно, что до сих пор не удалось <соорудить> какую-либо конструкцию, существенно более сложную, чем мозеровская, но критическую и с [M/D]+1>(c M/D>4). Тем более это кажется удивительным, что у нас есть компьютеры, позволяющие производить весьма значительный перебор. И вместе с тем некоторые нетривиальные соображения заставляют предположить, что ( 2)=4. Во всяком случае, в 1994 году А. Сойфер доказал, что не существует (M, D)-критической конфигурации с [M/D]+1>6 (c M/D>6). Это ещё отнюдь не означает, что ( 2)6, но и этот факт весьма замечательный.

Д о к а з а т е л ь с т в о т е о р е м ы III. Имея целью обосновать результат Хадвигера, естественно попытаться явно указать какую-нибудь раскраску плоскости в необходимое число цветов.

Pages:     || 2 | 3 | 4 | 5 |   ...   | 7 |










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

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