Экстремальные характеристики вложений случайных графов в геометрические графы

Теория случайных графов — это современный и бурно развивающийся раздел комбинаторной теории вероятностей, который появился в середине XX века и за прошедшие десятилетия оформился в многогранную и глубоко проработанную самостоятельную дисциплину. В основе теории лежит очень важная идея, состоящая в том, что мощные методы теории вероятностей должны существенно помочь исследованиям свойств графов, дать принципиально новый ракурс для рассмотрения классического комбинаторного объекта. И действительно, зачастую нам интересно знать, с какой «степенью достоверности» выполнено то или иное свойство графа: скажем, граф, скорее, связен, или же, напротив, более правдоподобно предположение о его несвязности. Разумеется, строгий смысл в понятие достоверности вкладывается именно с помощью вероятности.

Серьезным стимулом развития теории случайных графов как самостоятельного раздела теории вероятностей стала и та роль, которую случайные графы играют в различных приложениях. Здесь можно говорить и об алгоритмических аспектах теории графов, и о применении моделей случайного графа для статистического анализа различных сложных сетей — в том числе социальных, биологических и пр. (см. [1], [2], [3]). Во всяком случае на нынешнем этапе своего становления наука о случайных графах имеет как значительную теоретическую, так и огромную практическую со ставляющие.

Систематическое изучение случайных графов было инициировано П. Эрдешем и А. Реньи, которые предложили простейшую и ставшую уже классической модель случайного графа, основанную на схеме испытаний Бернулли (см. [4], [5], [6]). Впрочем, разрозненные работы о случайных графах появлялись и гораздо раньше, поскольку сама идея крайне естественна. Достаточно интересную библиографию подобного сорта можно найти, например, в книге [7].

За те без малого полвека, которые прошли с момента появления упомянутых публикаций, модель Эрдеша — Реньи была очень глубоко исследована (см. [1], [7], [8], [9]). С одной стороны, это привело к изучению многочисленных более сложных моделей, которые подчас точнее отражают реальность (см. [1], [2]). С другой стороны, это позволило по-новому взглянуть на самые разные задачи комбинаторного анализа, допускающие интерпретацию в терминах графов. Имея на руках мощные вероятностные технологии для изучения свойств графов, мы можем отныне с тем же успехом применить их (при необходимости, серьезно доработав) и для исследования других классических проблем комбинаторики.

Среди классических проблем, лежащих на стыке комбинаторики и геометрии и допускающих указанную теоретико-графовую интерпретацию, особое место занимает задача Нелсона — Эрдеша — Хадвигера о раскраске метрического пространства. Речь идет об отыскании минимального количества цветов, в которые можно так покрасить все точки пространства, чтобы между точками одного цвета не было расстояния из заданного наперед множества вещественных положительных чисел. Иными словами, ищется хроматическое число графа, вершинами которого служат точки метрического пространства, а ребрами — пары точек, отстоящих друг от друга на некоторое расстояние из упомянутого множества.

Проблеме Нелсона — Эрдеша — Хадвигера посвящено огромное количество работ (см., например, [10], [11], [12], [13], [14], [15], [16], [17], [18]). По-видимому, первым, кто предложил использовать технику теории вероятностей для изучения свойств «графов расстояний» (т.е. графов с множеством вершин — точек в пространстве и ребер — пар точек на заданном расстоянии), был все тот же Эрдеш. Позднее вероятностный метод применялся в этой области неоднократно (см., например, [13], [19], [20]).

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

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

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

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

диссертации

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

введение

) в пространстве данной размерности.

Говоря точнее, речь идет прежде всего о случайном графе G (n, p), с рассмотрения которого Эрдешем и Реньи на рубеже 50ых — бОых годов прошлого столетия, по существу, и началась вся современная и многогранная вероятностная теория случайных графов (см. [1] - [9]).

Как уже упоминалось во введении, вероятностная трактовка комбинаторных и геометрических задач, допускающих теоретико-графовые интерпретации, исключительно' важна и плодотворна. Ее актуальность подтверждается и обилием работ, опубликованных крупнейшими специалистами в соответствующих областях за прошедшие с середины XX века десятилетия (см. [8], [13] - [16], [19], [20]).

Также не вызывает сомнений значимость той конкретной комбинаторно-геометрической проблемы, вероятностной интерпретации которой посвящена данная диссертация, — проблемы Нелсона — Эрдеша — Хадвигера о раскраске метрического пространства. Достаточно опять же процитировать лишь некоторые из книг и обзоров, в которых она детально изучается (см. [10] - [18]).

Интересующая нас вероятностная характеристика — это величина t (d, п, р, х), равная максимальному к, при котором в модели G (n, p) с большой вероятностью случайный граф содержит такой индуцированный подграф на к вершинах, что у него хроматическое число не меньше х и он изоморфен какому-либо графу расстояний в Если при всех к вероятность описанного события мала, то величина t (d, n, p, x) полагается равной нулю.

Задача об отыскании величины t (d, n, p, x) глубоко мотивирована работами Эрдеша (см., например, [21]). Кроме того, именно в такой постановке она рассматривалась в цикле работ A.M. Райгородского [22] - [24].

Подобные задачи вероятностной теории случайных графов и комбинаторной геометрии исключительно важны для осознания природы графов расстояний, которые до сих пор отнюдь не классифицированы и удовлетворительно не охарактеризованы. Кроме того, представляет интерес и разработка тех новых вероятностных методов, которые возникают в процессе изучения таких задач: очевидно, что область применения этих методов выходит далеко за рамки геометрической теории графов.

Цель и задачи исследования

Цель исследования в разработке вероятностных методов теории случайных графов и в получении с помощью этих методов достаточно точных оценок величины t (d, n, p, x) при различных соотношениях и зависимостях между параметрами.

Научная новизна полученных результатов

Все результаты диссертации являются новыми.

Практическая значимость полученных результатов

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

Основные положения диссертации, выносимые на защиту

1. Пусть при п —> оо выполнено: d (n) = const или d (n) —"¦ оо. Тогда для любого е > 0 существует N, такое, что при всех п > N и при любых х, d 1 и 2 имеем теорема 3).

2. Пусть при п —" оо выполнено: d (n) = const или d (n) —> оо. Тогда для любого е > 0 существует N, такое, что при всех п > N и при любых х, ^ > 1 и

Р>

2(d + 2)!)i 2 d-1

1 + е) (d + 2)8+з In п имеем теорема 3).

1 + е) с/ + 2)8 Inn

Р'

3. Пусть р таково, что рпа —> оо и (1 — р) па —> оо для любого фиксированного, а > 0. Тогда, каковы бы ни были заданные наперед d: х < (здесь ~~ хроматическое число пространства, см. § 1.2) и е, найдется по, начиная с которого при всех п выполнена оценка t (d, n, p, X) > 2(1-е)Йг (теорема 4).

1-р

Личный вклад соискателя

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

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

Результаты диссертации докладывались на IX международном семинаре «Дискретная математика и ее приложения», посвященном 75-летию со дня рождения академика О. Б. Лупанова (Москва, 2007 г.), на Ломоносовских чтениях в Московском государственном университете, а также на кафедральном семинаре кафедры математической статистики и случайных процессов механико-математического факультета МГУ, на семинаре проф. Б. М. Гуревича в МГУ, на семинаре проф. С. В. Конягина в МГУ и на семинарах д.ф.-м.н. A.M. Райгородского в МГУ.

Опубликованность результатов

Результаты диссертации опубликованы в работах [37] -[40] списка литературы. Всего по теме диссертации опубликовано 4 работы.

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

В диссертации имеется введение, общая характеристика работы, три главы, список литературы. Полный объем 64 страницы, из них 5 страниц занимает список литературы (40 наименований).

1. В. Bollobas, Random Graphs, Cambridge Univ. Press, Second Edition, 2001.

2. R. Durrett, Random Graph Dynamics, Cambridge Univ. Press, 2006.

3. A.M. Райгородский, Экстремальные задачи теории графов и анализ данных, НИЦ «Регулярная и хаотическая динамика», 2009.

4. P. Erdos, A. Renyi, On random graphs /, Publ. Math. Debrecen, 6 (1959), 290 297.

5. P. Erdos, A. Renyi, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci., 5 (1960), 17 61.

6. P. Erdos, A. Renyi, On the evolution of random graphs, Bull. Inst. Int. Statist. Tokyo, 38 (1961), 343 347.

7. В. Ф. Колчин, Случайные графы, Москва, Физматлит, 2002.

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

9. S. Janson, Т. Luczak, A. Rucinski, Random Graphs, Wiley, New York, 2000.

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

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

12. A.M. Райгородский, Хроматические числа, Москва, МЦНМО, 2003.

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

14. V. Klee, S. Wagon, Old and new unsolved problems in plane geometry and number theory, Math. Association of America, 1991.

15. P.K. Agarwal, J. Pach, Combinatorial geometry, Wiley, New York, 1995.

16. L.A. Szekely, Erdos on unit distances and the SzemerediTrotter theorems, Paul Erdos and his Mathematics, Bolyai Series Budapest, J. Bolyai Math. Soc., Springer, 11 (2002), 649 666.

17. A. Soifer, Chromatic number of the plane: a historical essay, Geombinatorics (1991), 13 15.

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

19. М. Penrose, Random Geometric Graphs, Oxford University Press, 2003.

20. B. Aronov, J. Pach, M. Sharir, G. Tardos, Distinct distances in three and higher dimensions, Combinatorics, Probability and Computing, 13 (2004), 283 293.

21. P. Erdos, Unsolved Problems, Congress Numerantium XV Proceedings of the 5th British Comb. Conf. 1975, (1976), 681.

22. A.M. Райгородский, Проблема Нелсона Эрдеша — Ха-двигера и вложения случайных графов в геометрические, Доклады РАН, 403 (2005), N2, 169 — 171.

23. A.M. Райгородский, Раскраски пространств и случайные графы, Фундаментальная и прикладная математика, 11 (2005), N6, 131 141.

24. A.M. Райгородский, Проблема Нелсона Эрдеша — Ха-двигера и реализация случайных графов в пространстве, Успехи матем. наук, 61 (2006), N4, 195 — 196.

25. В. Bollobas, Threshold functions for small subgraphs, Math. Proc. Camb. Phil. Soc., 83 (1981), 433 436.

26. Ф. Харари, Теория Графов, Москва, «Мир», 1973.

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

28. L. Moser and W. Moser, Solution to problem 10, Canad. Math. Bull., 4 (1961), 187 189.

29. H. Hadwiger, Uneldste Probleme N40, Elemente der Math., 16 (1961), 103 104.

30. O. Nechushtan, On the space chromatic number, Discrete Math., 256 (2002), 499 507.

31. JI.JI. Иванов, Оценка хроматического числа пространства R4, Успехи матем. наук, 61 (2006), N5, 371 372.

32. D. Coulson, A 15-colouring of 3-space omitting distance one, Discrete Math., 256 (2002), 83 90.

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

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

35. В. Bollobas, The chromatic number of random graphs, Com-binatorica, 8 (1988), 49 56.

36. B. Bollobas, Martingales, isoperimetric inequalities, and random graphs, Proceedings, Eger (1987) (A. Hajnal, L. Lovasz, V.T. Sos, eds.), Colloq. Math. Soc. Janos Bolyai, 52 (1987), North Holland, Amsterdam, 113 — 139.

37. C.B. Нагаева, О вложимости конечных графов расстояний с большим хроматическим числом в случайные графы, Доклады РАН, 418 (2008), N1, 19 22.

38. С. В. Нагаева, A.M. Райгородский, О вложимости конечных графов расстояний с большим хроматическим числом в случайные графы, Итоги науки и техники, «Современная математика и ее приложения», 62 (2009), 47 66.

39. С. В. Нагаева, A.M. Райгородский, О реализации случайных графов графами расстояний в пространствах фиксированной размерности, Доклады РАН, 424 (2009), N3, 315 317.