Хроматические числа метрических пространств и некоторые смежные задачи оптимизации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Московский Государственный Университет имени М.В. Ломоносова Механико-Математический Факультет

На правах рукописи УДК 514.177.2+ 517.272+519.157+519.174.7

Митричева Ирина Михайловна

ХРОМАТИЧЕСКИЕ ЧИСЛА МЕТРИЧЕСКИХ ПРОСТРАНСТВ И НЕКОТОРЫЕ СМЕЖНЫЕ ЗАДАЧИ ОПТИМИЗАЦИИ

01.01.09 — дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2010

Работа выполнена на кафедре общих проблем управления Механико-математического факультета Московского государственного университета имени М. В. Ломоносова.

Научные руководители: доктор физико-математических наук,

профессор Протасов Владимир Юрьевич

доктор физико-математических наук Райгородский Андрей Михайлович

Официальные оппоненты: доктор физико-математических наук,

профессор Дольников Владимир Леонидович

кандидат физико-математических наук Карасёв Роман Николаевич

Ведущая организация: Хабаровское отделение Института

прикладной математики ДВО РАН

Защита диссертации состоится 23 апреля 2010 г. в 16 ч. 45 мин. на заседании диссертационного совета Д 501.001.84 при МГУ имени М. В. Ломоносова по адресу: РФ, 119991, Москва, ГСП-1, Ленинские горы, д. 1, МГУ, Механико-математический факультет, ауд. 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан 23 марта 2010 г.

Ученый секретарь диссертационного совета Д 501.001.84 при МГУ доктор физико-математических наук, профессор

А. О. Иванов

Общая характеристика работы

Актуальность темы

В работе изучаются хроматические числа различных метрических пространств с к запрещенными расстояниями, т.е., минимальные количества цветов, в которые можно окрасить все точки пространства таким образом, что никакие две точки одного цвета не будут находиться на запрещенном расстоянии друг от друга.

Впервые задача отыскания хроматического числа была сформулирована в 1950 году Э. Нелсоном. Первоначально речь шла о хроматическом числе евклидова пространства с одним запрещенным расстоянием. Значительную роль в развитии науки о хроматическом числе сыграли Дж. Избелл, Г. Хадвигер \ П. Эрдеш2' 3, М. Гарднер4 и братья Мозеры5, 6.

До обсуждения произвольных метрических пространств дело дошло в 1976 году, когда М. Бенда и М. Перлес рассмотрели пространство векторов с рациональными координатами с евклидовым расстоянием в нем 7.

Развитие науки о хроматических числах шло одновременно по нескольким направлениям: множество результатов было получено для евклидова пространства R" в малых размерностях6 •8. Параллельно с этим шла работа над асимптотическими верхними и нижними оценками. Первая нетривиальная (линейная по п) нижняя оценка хроматического числа евклидова пространства с одним запрещенным расстоянием была получена Д. Райским 9. Затем Д. Ларман, К. Роджерс, П. Эрдеш, В. Шош и Ж. Надь доказали квадратичную по п нижнюю оценку 8 • 10. Позже П. Франкл и Р. Уилсон получили экспоненциальное ограничение снизу для указанной величины 11. A.M. Райгородскому принадлежит наилучшая на данный момент константа в нижней экспоненциальной оценке классического хроматического числа8. Кроме того, им были получены общие верхняя и нижняя экспоненциальные оценки для произвольного числа запрещенных расстоя-

1Н. Hadwiger, Ungelöste Probleme N 40, Elemente der Math., 16 (1961), 103 - 104.

2P. Erdös, Some unsolved problems, UTA MKI Kozl, 6 (1961), 221 - 254.

3P. Erdös, On some problems of elementary and combinatorial geometry, Ann. Math. Pure Appl., (4) 103 (1975), 99-108.

4M. Gardner, A new collection оj brain teasers, Scientific American, 206 (Oct. 1960), 1T2 - 180.

5 L. Moser and W. Moser, Solution to Problem 10, Can. Math. Bull., 4, (1961), 187-189.

6 А. Сойфер, Хроматическое число плоскости: его прошлое, настоящее и будущее, Матем. просвещение, 8 (2004).

'M. Benda and M. Perles, Colorings of metric spaces, Geombinatorics, 9 (2000), 113 - 126.

s A.M. Райгородский, Проблема Борсука u хроматические числа метрических пространств, Успехи Матем. Наук, 56 (2001), N1,107 - 146.

9 Д.Е. Райский, Реализация всех расстояний при разбиении пространства Rn кап+1 часть, Матем. заметки, 7 (1970), N3, 319 - 323.

10 D.G. Larinan and С. A. Rogers, The realization of distances within sets in Euclidean space, Mathematik», 19 (1972), 1 - 24.

11 P. Frankl and R_ "Wilson, Intersection theorems with geometric consequences, Combinatorica, 1 (1981), 357 - 368.

ний 12 '13. Наилучшая верхняя оценка для одного запрещенного расстояния была доказана Ларманом и Роджерсом 10.

В задаче о хроматическом числе пространства (R",ii), где I! х 11= 1х<1> наилучшая нижняя оценка принадлежит Райгород-

скому 13,14 а верхняя — Дж.-Х. Канг и 3. Фюреди 15.

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

В диссертации мы рассматриваем, главным образом, асимптотические нижние оценки хроматических чисел вещественного пространства R" с различными метриками при запрете нескольких расстояний и пространства векторов с рациональными координатами. Новизна нашего подхода состоит в том, что мы впервые применяем к данной задаче методы решения конечномерных экстремальных задач. С помощью методов выпуклой оптимизации удается улучшить старые оценки и получить новые.

Также в работе затрагивается еще одна задача комбинаторной геометрии — проблема Борсука. В 1933 году Ворсук высказал гипотезу, согласно которой всякое ограниченное множество в R" может быть разбито на (п-Ы) часть меньшего диаметра 16. В некоторых маленьких размерностях гипотеза была доказана, но для пространств размерности больше некоторого N гипотеза опровергнута17 •18. В настоящее время идет борьба за уменьшение значения N. Кроме того, для числа Борсука (то есть минимального числа частей, на которое всегда можно так разбить ограниченное множество, что диаметр каждой части будет меньше диаметра исходного множества) были доказаны асимптотические верхние и нижние оценки. Верхняя (экспоненциальная) оценка принадлежит О. Шрамму 19, а нижняя была доказана Каном - Калаи и Райгородским и представляет собой константу в степени

^П 8 , 17 , 20 , 21

12 Н.Г. Мощевитин, A.M. Райгородский, О раскрасках пространства К" с несколькими запрещенными расстояниями, Матем. заметки, 81 (2007), N5, 733 - 743.

13 A.M. Райгородский, О хроматическом числе пространства с .метрикой 1„ Успехи и&тем. наук, 59 (2004), N5, 161 - 162.

14 A.M. Райгородский, О хроматических числах метрических пространств, Чебышевский сборник, 5 (2004), N1(9), 175- 185.

15 J.-H. Kang, Z. Füredi, Distance graphs on Z" with I,-norm, Theoretical Comp. Sei. 319 (2004), N1 -3, 357 - 366.

16 К. Borsuk, Drei Sätze über die n-dimensionale euklidische Sphäre, Fund. Math., 20 (1933), 177-190

1TJ. Kahn, G. Kalai, A counterexample to Borsuk's conjecture. Bull. Amer. Math. Soc. (N.S.) 29 (1993),

no. 1, 60-62.

"A.M. Райгородский, О размерности в проблеме Борсука, Успехи матем. наук, 52 (1997), N6, 181 -182.

"Schramm О. Illuminating sets of constant width, Mathematika, 35 (1988), 180 - 189.

20A.M. Райгородский, Об одной оценке в проблеме Борсука, Успехи матем. наук, 54 (1999), N2,185 -186.

21 A.M. Райгородский, Проблема Борсука для {0,\)-многогранников и кросс-политопов, Доклады

В настоящей работе рассматривается связь между двумя названными задачами и доказывается условный результат, касающийся усиления оценок для хроматического числа и числа Борсука.

Цель работы '

1) Изучение свойств хроматических чисел различных метрических пространств с одним и несколькими запрещенными расстояниями при росте размерности пространств, получение асимптотических нижних оценок этих величин;

2) применение современных методов выпуклой оптимизации к задачам оценки хроматических чисел;

3) изучение связи задачи о хроматическом числе с задачей Борсука.

Основные методы исследования

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

Научная новизна

Результаты работы являются новыми и состоят в следующем.

1) Получены новые асимптотические нижние оценки хроматических чисел конечномерного пространства с евклидовой метрикой и с метрикой 11 при запрете нескольких расстояний. Доказанные оценки является наилучшими в рамках использованного метода.

2) Исследовано изменение асимптотической нижней оценки хроматического числа пространства (Мп, р) с одним запрещенным расстоянием при "непрерывном" изменении метрики р от Ь к ¿23) Разработана техника решения специального класса задач выпуклой

многомерной минимизации, применимая для получения асимптотических нижних оценок хроматических чисел.

4) Изучена связь задачи о хроматическом числе и задачи Борсука. Получены ограничения на сумму показателей оценок для задачи о хроматическом числе и задачи Борсука.

Теоретическая и практическая ценность

Диссертация носит теоретический характер. Результаты диссертации могут найти применение при изучении задачи о хроматическом числе мет-

РАН, 371 (2000), 600 - 603.

рического пространства, линейно-алгебраического метода в комбинаторике, проблемы Борсука, при исследовании дистанционных графов в различных метрических пространствах.

Апробация результатов

Результаты диссертации докладывались автором на следующих научных семинарах и конференциях:

• Международная конференция „Шестой Чехословацкий Симпозиум по Комбинаторике, Теории Графов, Алгоритмам и Приложения!^'в г. Прага (Чехия, 2006 г.).

• Международная конференция „Горизонты Комбинаторики" в г. Бала-тональмади (Венгрия, 2006 г.).

• IX международный семинар „Дискретная математика и ее приложения", посвященный 75-летию со дня рождения академика О.Б. Лупа-нова (Москва, 2007 г.).

• Международная конференция „Фестиваль Комбинаторики и Информатики" в г. Кестхей (Венгрия, 2008 г.).

• Международная конференция „Европейская Комбинаторика!' в г. Бордо (Франция, 2009 г.).

• Кафедральный семинар кафедры математической статистики и случайных процессов механико-математического факультета МГУ, 2007г.

• Семинар под руководством д. ф.-м. н., профессора C.B. Конягина на механико-математическом факультете МГУ, 2007г.

• Семинар „Дискретный аналиЗ'под руководством д. ф.-м. н., профессора A.A. Сапоженко на факультете ВМиК МГУ, 2010г.

• Семинар „Линейно - алгебраические и вероятностные методы в комбинаторике?'под руководством д. ф.-м. н. A.M. Райгородского в МГУ, 2006 - 2010гг.

Публикации

Основные результаты диссертации опубликованы в 8 работах автора, список которых приведён в конце автореферата [1-8].

Структура и объем диссертации

Диссертация состоит из введения, 7 глав и списка литературы. Полный объём диссертации — 77 страниц, список цитируемой литературы содержит 51 наименование.

Краткое содержание работы

Диссертация состоит из введения и семи глав.

Во введении изложена краткая история вопроса, приведены ссылки на основные работы в данной области.

В первой главе даются необходимые определения и приводятся (без доказательства) формулировки как известных оценок, так и результатов, полученных автором диссертации.

Задача о хроматическом числе состоит в отыскании величины х(Х, р,Л), равной наименьшему количеству цветов, в которые можно так раскрасить все точки метрического пространства X с метрикой р, чтобы точки х, у 6 X с р(х, у) € А были разного цвета. Величина х(Х, р, Л) называется хроматическим числом пространства X с метрикой р и множеством запрещенных расстояний А.

Проблема Борсука состоит в отыскании минимального числа (называемого числом Борсука) f(n) частей меньшего диаметра, на которые разбивается любое ограниченное неодноточечное множество в R71.

В качестве первого параметра определенной выше величины х{Х, р, А) в диссертации рассматриваются пространства R" и Q", в качестве метрики берутся широко используемые метрики /2 и а также гибридная метрика, совмещающая в себе li и ¿2-

Из-за большого количества параметров в случае запрещения нескольких расстояний от величины х(Х, р, Л) мы переходим к величине

Х(Х, р; k) = max х{Х, р, А), И=к

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

Замечая, что даже '2, {а}) зависит от а, но что сама эта зависи-

мость возникает лишь при a g Q, полагаем отдельно

Ы<Г> h; к)= max x(Qn, ¿2, {оь . ■., а*}),

Xq(QV2;£)= max Y(QV2.{ai.-..,a*}). ai,...,ote(J

Для полноты картины возвращаемся к случаю К" и вместо одной величины h', к) вводим две:

Xr(R", h\ к) = h\ к)= max X(Rn, к, {аь... ,ак}), XQ(Rn,l2-,k) = max у(Г,12,{аь...,аЛ).

Итак, основными объектами исследования здесь являются величины Хк№п,12;к), xQ(KVa;*), xA®n,hik), xQ(®n,h;k),

причем

Xr(®V2; i) = х<г(К"Л; I) - x(RVa, {l})

и

3CQ(Q",i2;l) = x(Qn>h, {!}) Xa(Qn,hi !)• Подчеркнем, что уже при к > 2 все изучаемые нами величины, вообще говоря,различны.

Для каждой пары (X,Y) е {Q,K} х {Q,K} при р € {l\,h} зададим величину хх(Уп, Р1 к) соотношением

(У", р; к) = (хх(Уп, Pi к) + о(1))".

Строго говоря, речь идет даже не о функциях xx(Yn, р\ к), а о классах эквивалентности (функции эквивалентны, если отличаются на о( 1)). Такое определение оправдано, поскольку все полученные нами оценки имеют вид

Xx{Yn,Plk)>(amst + o{ 1))".

Для константы в правой части неравенств введем следующие обозначения:

*)>(& +о(1))п. M®n>hlk)> (6 + о(1))п.

В случае, когда говорится о константе, которая не является наилучшей на данный момент, мы добавляем к соответствующей букве верхний индекс 0. Мы записываем константы в основании экспонент с точностью до третьего знака после запятой.

A.M. Райгородским8 показано, что .

XQ(R",i2; 1) = 5b(RVa; 1) > Xn(Qn,hl 1) > (<1 + o(l))n, где Ci = 1.239...;

XH(Rn, hi 2) > Xr(Qu, hi 2) > (C2° + 0(1))",

где C2° = 1.439...;

Xq(QV2;1)> (6 + 0(1))", 6

где & = 1.173...;

для любых X, У е (<0>, К} имеют место неравенства

где К\ — 1.366...;

Хх(Уп,1г-,2)>(к°2 + о(1)Г,

где >4 = 1.607....

Во второй главе единым методом доказаны оценки хроматического числа вещественного пространства М" со стандартной евклидовой метрикой при запрете двух и более расстояний. Доказана Теорема 1

Имеют место неравенства

Теорема 1 соответствует теоремам 7 и 8 диссертации.

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

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

ХК(КП, /2; 2) > к\ 2) > (Са + о{I))

1П

где Сг = 1.465.

Хн(Г\ 12; 3) > хЖ, 3) > (Сз° + о(1))п,

где = 1.664...;

хк(м"Л;4) > Ш«Г,12-А) > «? + о(1))п,

где С2 = 1.836...

тах.

Здесь

Д = {х 6 ^ : х > 0, (ж, е) = 1}

где е = (1, ...,1), неравенство х > 0 понимается покоординатно,

d

b = (0,1,..., d-1), f(x) — J2 xi In:Ei ~■• функция энтропии, h(v) — разность

i=i

между максимальным и минимальным возможными скалярными произведениями векторов V е Д.

Для ее решения был применен принципиально новый подход. Она была сведена к семейству выпуклых экстремальных задач специального вида (минимизация выпуклой функции на границе многогранника), для которых был разработан эффективный метод решения. Это позволило нам получить следующие результаты:

1) вычислены значения констант Ct для к = 1,..., 20. Эти значения являются наилучшими для данного метода. В частности, уже при к = 3,4 они улучшают известные ранее оценки, а именно, = 1,667..., £4 = 1,848....

2) получены аналитические выражения для оценок ("fc при всех к > 20. Мы высказываем гипотезу, что эти оценки также оптимальны для данного метода.

В четвертой главе доказаны условные результаты, касающиеся хроматических чисел. Справедлива Теорема 2

Имеют место неравенства

lim sup ЫК", h\ 2) + limsup Xq(Q", W, 2) > C2 4- £1 + ¿1,

n—too n-400

гдеб^ = 0.043...;

lim sup xk(R", l2-1) + Um sup xQ(Qn, h\ 1) > C1 + 6 + S2,

n—>00 n—>00

где S2 = 0.005....

Теорема 2 включает в себя результаты теорем 9 и 10 диссертации. В пятой главе получены результаты относительно пространства (Rn, h) с несколькими запрещенными расстояниями. Доказана Теорема 3

Для любых X, Y Е {Q, R} имеют место неравенства XX(Vn,h;2)>(K2 + o(l)r,

где К2 = 1.691...;

5fc(yVi;3)>(K§ + o(l))",

где к§ = 2.000...;

Хх(УпЛ;4)>(К° + 0(1)У\

где к\ = 2.250....

Теорема 3 соответствует теореме 14 диссертации.

Как и в случае евклидовой метрики, задача получения нижних оценок хроматических чисел была сведена к некоторой выпуклой экстремальной задаче, которая, однако, существенно отличалась от задачи из главы 3. При помощи алгоритмов выпуклой минимизации были получены оптимальные значения параметров Например, кз = 2.003..., «4 = 2.334....

В шестой главе мы проследили за изменением оценок хроматического числа при своего рода „непрерывном " переходе от метрики 1\ к метрике /г-В качестве смешанной метрики рассматривалась величина

Р*(х, у) = у/(ц - ш)2 + ... + (хг - у1)2 + |хт - у1+г\ + • • - + \хп - уп\.

Положив = мы вычислили оценки величины рс, 1) при раз-

личных значениях ¿о от 0 до 1 с шагом 0.01. Полученные результаты представлены на графике.

Значения в концах отрезка соответствуют известным оценкам величин Хк(Ж.п, ¿1; 1) и 1г\ 1). Полученная зависимость оказывается достаточ-

но близкой к линейной. Мы формулируем гипотезу о выпуклости данной функции.

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

Райгородский22 показал, что

Нт (х(п) + /(п)) > 2.464... + 0.004.

п—>оо

Нам удалось улучшить этот результат. С использованием результатов главы 2 была доказана

Теорема 4

Для каждого натурального п либо х(п) > 4-5, либо /(<£) > г + 5, где а = 5 = 0.017.

Теорема 4 отражает результат теоремы 15 диссертации.

22А.М. Райгородский, О числах Борсука и Эрдехиа - Хадвигера, Матем. заметки, 79 (2006), N6, 913 -924.

Благодарности

Автор выражает глубокую признательность научным руководителям д. ф. - м. н., профессору В.Ю. Протасову и д. ф. - м. н. A.M. Райгородско-му за постановку задач, постоянное внимание к работе, ценные указания и моральную поддержку.

Автор благодарен сотрудникам кафедры общих проблем управления за прекрасную доброжелательную атмосферу.

Публикации автора по теме диссертации

[1] И.М. Шитова (Митричева), О хроматических числах метрических пространств с двумя запрещенными расстояниями, Доклады РАН, 413 (2007), N2, 178 - 180.

[2j A.M. Райгородский, И.М. Шитова (Митричева), О хроматических числах вещественных и рациональных пространств с несколькими вещественными или несколькими рациональными запрещенными расстояниями,, Математический сборник, 199 (2008), N4, 107 - 142. В работе И.М. Митричевой принадлежит вывод общей экстремальной задачи для получения оценок хроматического числа и ее решение с использованием алгоритмов дискретной оптимизации, ею были получены результаты теорем 4-1, 4-2, 5.1, 5.2, 5.3. A.M. Райгородско-му принадлежит идея применения линейно-алгебраического метода в комбинаторике и метода альтернирования, а также результаты теорем 2.1, 2.3.

[3] A.M. Райгородский, И.М. Шитова (Митричева), О хроматических числах евклидова пространства и о проблеме Ворсука, Математические заметки, 83 (2008), N4, 636 - 639.

В работе И.М. Митричевой принадлежит решение задачи об оценке хроматического числа и числа Борсука, а также получение конечных численных результатов. A.M. Райгородскому принадлежит постановка данной задачи.

[4] Е.С. Горская, И.М. Митричева, В.Ю. Протасов, A.M. Райгородский, Оценка хроматических чисел евклидова пространства методами выпуклой оптимизации, Математический сборник, 200 (2009), N6, 3 - 22. В работе И.М. Митричевой принадлежит техника получения оценок хроматического числа (сведение дискретной задачи к задаче выпуклой минимизации). Решение выпуклой экстремальной задачи и окончательные численные результаты были получены Е.С. Горской. О применении современных' методов выпуклой теории оптимизации

в данной задаче написал В.Ю. Протасов. Основная идея применения линейно-алгебраического метода в комбинаторике принадлежит

A.M. Райгородскому.

I.M. Shitova (Mitricheva), On the chromatic numbers of metric spaces with few forbidden distances, Abstracts of Sixth Czech-Slovak International Sympozium (2006), 115.

I.M. Shitova (Mitricheva), On the chromatic numbers of metric spaces with few forbidden distances, Abstracts of EMS Conference cHorizon of Combinatorics> (2006).

И.М. Шитова (Митричева), Хроматические числа метрических пространств с несколькими запрещенными расстояниями и их связь с проблемой Борсука, Материалы IX Международного семинара „Дискретная математика и ее приложений', посвященного 75-летию со дня рождения академика О.Б. Лупанова (Москва, 18-23 июня 2007 г.).

I.M. Shitova (Mitricheva), A solution to an extremum problem concerning the chromatic numbers of spaces with several forbidden distances, with E.S. Gorskaya, V.J. Protasov, A.M. Raigorodskii, Abstracts of „Fete of Combinatorics and Computer Science", Keszthely, Hungary (2008), 110. В работе И.М. Митричевой принадлежит метод получения оценок хроматического числа. Е.С. Горской принадлежит решение выпуклой экстремальной задачи и окончательные численные результаты.

B.Ю. Протасову принадлежит идея применения современных методов выпуклой теории оптимизации в данной задаче. A.M. Райгородскому принадлежит идея использования линейно-алгебраического метода в комбинаторике.

Подписано в печать

Формат 60x90 1/16. Усл. печ. л. /£>

Тираж -{00 экз. Заказ //

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета МГУ имени М.В.Ломоносова

Обозначения

Введение

1 История вопроса, постановки задач и формулировки результатов

1.1 Оценки хроматических чисел пространств /2) и (((2П, 12) при запрете одного и нескольких расстояний.

1.1.1 Постановки задач.

1.1.2 Известные безусловные результаты.

1.1.3 Известные условные результаты.

1.1.4 Новые безусловные результаты.

1.1.5 Новые условные результаты.

1.2 Оценки хроматических чисел пространств (Мп, /х) и ((р)™, ¿х) при запрете одного и нескольких расстояний.

1.3 Изменение нижней оценки величины Р\ {&}) при „непрерывном" изменении метрики от 1\ к ¿2.

1.3.1 Известные результаты.

1.3.2 Метрика рь

1.4 Условные нижние оценки величины ¿2", {а}) и числа Бор-сука

2 Доказательства теорем 7 и

2.1 Переформулировки задач на языке теории графов.

2.2 Основные шаги доказательства теорем 7 и 8.

2.3 Оптимизация оценок из раздела 2.2.

2.3.1 Асимптотика для суммы, дающей верхнюю оценку числа независимости графа (З^.

2.3.2 Асимптотика для суммы, дающей верхнюю оценку числа независимости графа 6?2.

2.3.3 Асимптотики нижних оценок хроматических чисел графов Сх, Сг и завершение доказательств теорем 7,

3 Доказательства оптимальных нижних оценок величины

ХК(МП, ¡2] к) в случае к >

3.1 Метод получения оценок. Экстремальная задача.

3.2 Численные результаты. Оценки хроматических чисел.

4 Доказательства новых условных оценок хроматических чисел и комментарии к ним

4.1 Доказательства теорем 9-11.

4.1.1 Доказательства теорем 9,

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

4.2 Комментарии к доказательствам теорем 9-11.

4.2.1 Несколько замечаний

4.2.2 Общий подход к получению условных оценок.

5 Доказательство нижней оценки величины Хм2)

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

5.2 Получение нижних оценок величины к] к) в случае к >

6 Изменение нижней асимптотической оценки при „непрерывном" изменении метрики от 1\ к ¿

6.1 Описание метода решения задачи и основная лемма.

6.2 Формулировка экстремальной задачи.

6.3 Решение экстремальной задачи.

6.4 Практическая реализация алгоритма и новые результаты

7 Доказательство условных оценок величины х(Мп, {о}) и числа Борсука

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

Обозначения

• 1 —

глава

• 1.2 — раздел 2 главы

• 1.2.3 — параграф 3 раздела 2 главы

• (Мп, ¿2) — евклидово пространство со стандартной метрикой

• (Qn, ¿2) — пространство векторов с рациональными координатами с евклидовой метрикой

• (Rn, li) — евклидово пространство с метрикой где

Zi(x,y) = \xi-yi\-\-----b \хп - уп\

• (Qn5 h) — пространство векторов с рациональными координатами с метрикой ¿

• < х, у > — скалярное произведение векторов в (Мп,/2)

• х * у — прямое произведение векторов

• а(п) ж Ь(п) — существуют такие константы ci,c2 > 0, что при всех п выполнено cib(n) < а(п) < С2б(п)

• В записях вида (const+ о{1))п. будут появляться различные значения константы const. Все они будут обозначаться (k или Cjt

• В записях вида xQ(QV2;A0>(6; + o(i)r. будут появляться различные значения константы const. Все они будут обозначаться & или

В записях вида

Хл(Цп^1]к)>(кк + о(1))п. будут появляться различные значения константы const. Все они будут обозначаться к к или к®.

В работе изучаются хроматические числа различных метрических пространств с к запрещенными расстояниями, т.е., минимальные количества цветов, в которые можно окрасить все точки пространства таким образом, что никакие две точки одного цвета не будут находиться на запрещенном расстоянии друг от друга.

Впервые задача отыскания хроматического числа была сформулирована в 1950 году Э. Нелсоном. В тот момент речь шла о хроматическом числе евклидова пространства с одним запрещенным расстоянием. Значительную роль в развитии науки о хроматическом числе сыграли Дж. Избелл, Г. Хадвигер, П. Эрдеш, М. Гарднер и братья Мозеры (см. [1, 2, 3, 4, 5]). История возникновения задачи о хроматическом числе освещена в обзоре А. Сойфера (см. [6])

До обсуждения произвольных метрических пространств дело дошло в 1976 году, когда М. Бенда и М. Перлес написали статью [7], в которой рассматривалось пространство векторов с рациональными координатами с евклидовым расстоянием в нем.

Развитие науки о хроматических числах шло одновременно по нескольким направлениям: множество результатов было получено в малых размерностях (см. [6, 8]). Параллельно с этим шла работа над асимптотическими верхними и нижними оценками. Первая нетривиальная (линейная) нижняя оценка хроматического числа евклидова пространства с одним запрещенным расстоянием была получена Д. Райским (см. [9]). Затем Д. Ларман, К. Роджерс, П. Эрдеш, В. Шош и Ж. Надь доказали квадратичную нижнюю оценку (см. [8, 10]). Позже П. Франки и Р. Уилсон получили экспоненциальное ограничение снизу для указанной величины (см. [11]). A.M. Райгородскому принадлежит наилучшая на данный момент константа в нижней экспоненциальной оценке классического хроматического числа (см. [8]). Кроме того, им были получены общие верхняя и нижняя экспоненциальные оценки для произвольного числа запрещенных расстояний (см. [12, 13]). Наилучшая верхняя оценка для одного запрещенного расстояния была доказана Ларманом и Роджерсом см. [10]).

В задаче о хроматическом числе пространства (Мп, ¿1) наилучшая нижняя оценка принадлежит А.М. Райгородскому (см. [13, 14]), а верхняя — Дж,-X. Канг и 3. Фюреди (см. [15]).

В данной работе мы рассматриваем главным образом асимптотические нижние оценки хроматических чисел вещественного пространства Мп с различными метриками при запрете нескольких расстояний и пространства векторов с рациональными координатами. Также в работе затрагивается еще одна задача комбинаторной геометрии — проблема Борсука.

В 1933 году Борсук высказал гипотезу, согласно которой всякое ограниченное множество в Мп может быть разбито на (п+1) часть меньшего диаметра (см. [16]). В некоторых маленьких размерностях гипотеза была доказана, но для пространств размерности больше некоторого N гипотеза опровергнута (см. [17, 18]). В настоящее время идет борьба за уменьшение значения N. Кроме того, для числа Борсука (то есть минимального числа частей, на которое всегда можно так разбить ограниченное множество, что диаметр каждой части будет меньше диаметра исходного множества) были доказаны асимптотические верхние и нижние оценки. Верхняя (экспоненциальная) оценка принадлежит О. Шрамму (см. [19]), а нижняя была доказана Ка-ном - Калаи и Райгородским и представляет собой константу в степени л/п (см. [8, 17, 20, 21]).

Диссертация состоит из семи глав. В первой главе освещается история вопроса, даются основные определения и приводятся без доказательства формулировки как известных оценок, так и результатов, полученных автором диссертации. Во второй главе единым методом доказаны оценки хроматического числа вещественного пространства Кп со стандартной евклидовой метрикой при запрете двух и более расстояний. При этом оценка, доказанная для двух запрещенных расстояний, является на данный момент наилучшей из известных, а оценки для трех и более запрещенных расстояний были улучшены (они рассмотрены в третьей главе). Также во второй главе сформулирована общая задача, решение которой позволяет получить более точные по сравнению с известными оценки для евклидова пространства и трех и более запрещенных расстояний. В третьей главе с привлечением дополнительных соображений выпуклого анализа решена общая задача. В четвертой главе доказаны некоторые так называемые условные результаты, касающиеся хроматических чисел. В пятой главе получены результаты относительно пространства (Мп, ¿1) с несколькими запрещенными расстояниями. В шестой главе мы проследили за изменением оценок хроматического числа при своего рода „непрерывном " переходе от метрики к метрике ¿2 и получили численные оценки для промежуточных метрик. В седьмой, заключительной главе, содержатся условные результаты, связывающие задачу о хроматическом числе с задачей Борсука.

Автор выражает глубокую признательность научным руководителям д. ф. -м. н., профессору В.Ю. Протасову и д. ф. - м. н. A.M. Райгородскому за постановку задач, постоянное внимание к работе, ценные указания и моральную поддержку.

Автор благодарен сотрудникам кафедры общих проблем управления за прекрасную доброжелательную атмосферу.

1. Н. Hadwiger, Ungelöste Probleme N 40, Elemente der Math., 16 (1961), 103 - 104.

2. P. Erdös, Some unsolved problems, MTA MKI Kozl., 6 (1961), 221 254.

3. P. Erdös, On some problems of elementary and combinatorial geometry, Ann. Math. Pure Appl., (4) 103 (1975), 99-108.

4. M. Gardner, A new collection of brain teasers, Scientific American, 206 (Oct. 1960), 172 180.

5. L. Moser and W. Moser, Solution to Problem 10, Can. Math. Bull, 4, (1961), 187-189.

6. А. Сойфер, Хроматическое число плоскости: его прошлое, настоящее и будущее, Матем. просвещение, 8 (2004).

7. М. Benda and М. Perles, Colorings of metric spaces, Geombinatorics, 9 (2000), 113 126.

8. A.M. Райгородский, Проблема Борсука и хроматические числа метрических пространств, Успехи Матем. Наук, 56 (2001), N1, 107 146.

9. Д.Е. Райский, Реализация всех расстояний при разбиении пространства Rn на п + 1 часть, Матем. заметки, 7 (1970), N3, 319 323.

10. D.G. Larman and С.A. Rogers, The realization of distances within sets in Euclidean space, Mathematika, 19 (1972), 1 24.

11. P. Frankl and R. Wilson, Intersection theorems with geometric consequences, Combinatorica, 1 (1981), 357 368.

12. Н.Г. Мощевитин, A.M. Райгородский, О раскрасках пространства Е" с несколькими запрещенными расстояниями, Матем. заметки, 81 (2007), N5, 733 743.

13. A.M. Райгородский, О хроматическом числе пространства с метрикой lq, Успехи матем. наук, 59 (2004), N5, 161 162.

14. A.M. Райгородский, О хроматических числах метрических пространств, Чебышевский сборник, 5 (2004), N1(9), 175 185.

15. J.-H. Kang, Z. Füredi, Distance graphs on Ъп with l\-norm, Theoretical Comp. Sei. 319 (2004), N1 3, 357 - 366.

16. К. Borsuk, Drei Sätze über die n-dimensionale euklidische Sphäre, Fund. Math., 20 (1933), 177-190

17. J. Kahn, G. Kalai, A counterexample to Borsuk's conjecture. Bull. Amer. Math. Soc. (N.S.) 29 (1993), N1, 60-62.

18. A.M. Райгородский, О размерности в проблеме Борсука, Успехи матем. наук, 52 (1997), N6, 181 182.

19. Schramm О. Illuminating sets of constant width, Mathematika, 35 (1988), 180 189.

20. A.M. Райгородский, Об одной оценке в проблеме Борсука, Успехи матем. наук, 54 (1999), N2, 185 186.

21. A.M. Райгородский, Проблема Борсука для (0,1)-многогранников и кросс-политопов, Доклады РАН, 371 (2000), 600 603.

22. L.A. Szekely, Erdös on unit distances and the Szemeredi Trotter theorems, Paul Erdös and his Mathematics, Bolyai Series Budapest, J. Bolyai Math. Soc., Springer, 11 (2002), 649 - 666.

23. A.M. Райгородский, О хроматическом числе пространства, Успехи Матем. Наук, 55 (2000), N2, 147 148.

24. A.M. Райгородский, Проблема Эрдеша Хадвигера и хроматические числа конечных геометрических графов, Доклады РАН, 392 (2003), N3, 313 - 317.

25. A.M. Райгородский, Проблема Эрдеша Хадвигера и хроматические числа конечных геометрических графов, Матем. сборник, 196 (2005), 123 - 156.

26. A.M. Райгородский, О нижних оценках для чисел Борсука и Хадвигера, Успехи Матем. Наук, 59 (2004), N3, 177 178.

27. A.M. Райгородский, О числах Борсука и Эрдеша Хадвигера, Матем. заметки, 79 (2006), N6, 913 - 924.

28. A.M. Райгородский, Хроматические числа дистанционных графов, Чебышевский сборник, 6 (2006), N3 (15), 159 170.

29. A.M. Raigorodskii, Some problems in combinatorial geometry, and the linear algebra method in combinatorics, Chebyshev Sbornik, 7:3 (2006), 168 188.

30. A.M. Райгородский, О хроматическом числе пространства с двумя запрещенными расстояниями, Доклады РАН, 408 (2006), N5, 601 604.

31. P. Brass, W. Moser, J. Pach, Research problems in discrete geometry, Springer, 2005.

32. Ф. Харари, Теория графов, Москва, „Мир", 1973.

33. N.G. de Bruijn and P. Erdos, A colour problem for infinite graphs and a problem in-the theory of relations, Proc. Koninkl. Nederl. Acad. Wet., Ser. A, 54 (1951), N5, 371 373.

34. L. Babai and P. Ffankl, Linear algebra methods in combinatorics, Part 1, Department of Computer Science, The University of Chicago, Preliminary version 2, September 1992.

35. A.M. Райгородский, Линейно-алгебраический метод в комбинаторике, Москва, МЦНМО, 2007.

36. В. Bolobas, Random Graphs, Cambridge Univ. Press, Second Edition, 2001.

37. N. Alon and J. Spencer, The probabilistic method, Wiley Interscience Series in Discrete Math, and Optimization, Second Edition, 2000.

38. H. Алон, Дж. Спенсер, Вероятностный метод, Бином: Лаборатория знаний, Москва, 2007.

39. R.C. Baker, G. Harman, J. Pintz, The difference between consecutive primes, II, Proceedings of the London Mathematical Society, 83 (2001), 532 562.

40. Э.М. Галеев, М.И. Зеликин, С.В. Конягин и др., Оптимальное управление,, Москва, МЦНМО, 2008.

41. Г.Г. Магарил-Ильяев, В.М. Тихомиров, Выпуклый анализ, М. Эдиториал УРСС, 2000.

42. В.Ю. Протасов, К вопросу об алгоритмах приближенного вычисления минимума выпуклой функции по ее значениям, Матем. заметки, 59 (1996), N1, 95 102.

43. A.M. Райгородский, И.И. Тимирова, О проблеме Нелсона Эрдеша -Хадвигера для одной серии метрических пространств, Чебышевский сборник, 9(2008), N1, 125 - 134.Работы автора по теме диссертации

44. И.М. Шитова (Митричева), О хроматических числах метрических пространств с двумя запрещенными расстояниями, Доклады РАН, 4132007), N2, 178 180.

45. A.M. Райгородский, И.М. Шитова (Митричева), О хроматических числах вещественных и рациональных пространств с несколькими вещественными или несколькими рациональными запрещенными расстояниями, Матем. сборник, 199 (2008), N4, 107 142.

46. Е.С. Горская, И.М. Митричева, В.Ю. Протасов, A.M. Райгородский, Оценка хроматических чисел евклидова пространства методами выпуклой оптимизации, Математический сборник, 200 (2009), N6, 3 22.

47. A.M. Райгородский, И.М. Шитова (Митричева), О хроматических числах евклидова пространства и о проблеме Борсука, Матем. заметки, 832008), N4, 636 639.

48. I.M. Shitova (Mitricheva), On the chromatic numbers of metric spaces with few forbidden distances, Abstracts of Sixth Czech-Slovak International Sympozium (2006), 115.

49. I.M. Shitova (Mitricheva), On the chromatic numbers of spaces with few forbidden distances, Abstracts of EMS Conference "Horizon of Combinatorics" (2006).