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

• Митричева, Ирина Михайловна
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Митричева, Ирина Михайловна

Обозначения

Введение

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. Райгородскому за постановку задач, постоянное внимание к работе, ценные указания и моральную поддержку.

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

Список литературы диссертационного исследования кандидат физико-математических наук Митричева, Ирина Михайловна, 2010 год

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).