Предельные распределения характеристик случайных дистанционных графов

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

Одним из тех, кто первым применил данный метод к задачам экстремальной комбинаторики, был венгерский математик Т. Селе. С помощью вероятностных соображений он доказал, что существует турнир на п вершинах, который содержит не менее п/2п~1 гамильтоновых путей (1943, [1]). Селе не построил явную конструкцию такого турнира, но показал, что множество турниров, удовлетворяющих данному требованию, не пусто. Это является характерной чертой такого способа доказательств. Именно поэтому этот метод также называется неконструктивным.

Широкое применение метода к теории чисел привело к появлению вероятностной теории чисел ([2] — [3]). Одним из первых применений неконструктивного метода к данной отрасли математики было новое, более простое доказательство теоремы Г. Харди и С. Рамануджана (1917, [4]), принадлежащее П. Турану (1934, [5]).

Примечательно, что примерно в это же время в вычислительной математике стремительно развивается применение статистических методов испытаний, более известных под названием «Метод Монте-Карло» (1949, [6]). Статистические методы вычислений использовались еще в XVIII — XIX вв. Самым широкоизвестным таким методом, в том или ином виде входящем во многие университетские учебники по теории вероятностей, является метод определения числа 7 г с помощью бросания иглы Бюффона (например, [7]).

Наибольшее применение вероятностный метод получил в экстремальной теории множеств, а также в теории графов и гиперграфов. Одним из первых результатов в этих областях была теорема П. Эрдеша, Ч. Ко и Р. Радо (1938, [8]) об экстремальных свойствах совокупностей подмножеств конечного множества. Именно выдающийся венгерский математик Эрдеш считается основателем вероятностного метода. В 50-е годы он занялся систематическим развитием метода, внеся тем самым неоценимый вклад в становление комбинаторики (в том числе — вероятностной).

Результаты, получаемые вероятностным методом, можно условно разделить на две группы. К первой группе относятся факты, которые формулируются в терминах существования комбинаторных структур, обладающих рядом определенных свойств. Основная идея доказательства подобных фактов может быть описана следующим образом: мы строим вероятностное пространство, в котором роль элементарных событий играют некоторые комбинаторные структуры, и затем показываем, что такие структуры обладают необходимыми свойствами с положительной вероятностью ([8] — [15] и др.). Вторая группа состоит из результатов, которые сами по себе являются теоретико-вероятностными. Эти результаты связаны с изучением определенных классов комбинаторных объектов, например, случайных графов или случайных матриц ([15] — [22]).

В диссертации приведены результаты, которые в соответствии с изложенной выше классификацией можно отнести ко второй группе. А именно, рассмотрена модель случайного дистанционного графа специального вида.

Как часто бывает в математике, изучение вероятностных свойств графа было начато независимо и практически одновременно несколькими исследователями. А именно, Дж. Фордом и Дж. Уленбеком (1956, [23]), Э. Гильбертом (1957, [24]), Т. Остином, Р. Фэйгином, В. Пенне и Дж. Риорданом (1959, [25]), П. Эрдешом и А. Реньи (1959, [17] — [19]). Тем не менее, только последние двое авторов предложили методы, которые легли в основу вероятностного построения теории случайных графов.

Эрдеш и Реньи рассмотрели две близких модели случайного графа — G (N, M) и G (N, p). В обеих моделях в роли элементарных событий в вероятностном пространстве O/v выступают графы на N вершинах без петель, кратных ребер и ориентации. В первом случае рассматриваются только графы с М ребрами (М < Сдг), и вероятность каждого из этих графов полагается равной 1 /С£2 ¦ Во второй модели количество ребер не фиксировано, то или иное ребро между вершинами графа проводится с вероятностью р независимо от других ребер.

Рассмотрим второй случай более подробно. Пусть N? N, 0 < р < 1. Рассмотрим множество nN = {G = (VN, E)} всех неориентированных графов без петель и кратных ребер с множеством вершин Vn = {!,•••, N}- Случайный граф в модели G (N, p) Эрдеша-Ренъи — это случайный элемент со значениями во множестве Г2дг и распределением РN, p на.

TN = определенным формулой.

Задачам, связанным с исследованиями случайного графа G (N, p), посвящено огромное количество работ. П. Эрдеш, А. Реньи ([17], [18]), К. Шургер ([26]), Б. Боллобаш ([27]), 3. Палка ([28]), А. Д. Барбур ([29]) и др. произвели значительный вклад в изучение распределения малых подграфов в случайном графе. Распределением количества деревьев занимались П. Эрдеш, А. Реньи ([18]), Б. Боллобаш ([30]), А. Д. Барбур ([29]) и др. Вопросам, касающимся связности случайного графа, посвящены работы E.H. Гильберта ([31]), T.JI. Остина и др. ([25]), П. Эрдеша, А. Реньи, В. Е. Степанова ([32], [33]), Г. И. Ивченко ([34]), Б. Боллобаша ([35]) и др. Поиском гигантской компоненты и определением ее размера занимались Т. Лучак ([36], [37]), Дж. Вирман ([37]), Б. Боллобаш ([30]), П. Эрдеш, А. Реньи ([18]) и др. При каких условиях случайный граф является гамильтоновым, можно узнать из работ И. Палаш-ти ([38] - [40]), В. А. Перепелицы ([41]), Дж. Муна ([42]), Е. Райта ([43], [44]) и др. Длину максимального пути для р = c/N изучали М. Айтаи, Дж. Комлош, Е. Семереди ([45]), В.Ф. де ля Вега ([46]), Б. Боллобаш ([47], [48]), Т. И. Фенне, A.M. Фриз ([48]) и др. В работах А. Хоффмана, Р. Синглетона ([49]), Р. Дэме-релла ([50]), Е. Баннаи, Т. Ито ([51]), Х. Д. Фридмана ([52], [53]) и др. изучено распределение диаметра случайного графа.

Тем не менее во многих приложениях модель Эрдеша-Реньи мало применима. Поэтому разрабатывались другие модели, которые призваны описывать зарождение или рост тех или иных реальных структур. Это могут быть биологические, социальные, транспортные сети и др. В связи со своим стремительным развитием в последние годы особенное место среди этих структур занимает Интернет. Множество работ посвящено исследованию так называемых веб-графов, вершины которых суть какие-либо структурные единицы в Интернете: речь может идти о страницах, сайтах, хостах, владельцах и пр., а ребра — гиперссылки между вершинами ([16], [54]).

Также представляют интерес модели, которые естественным образом обобщают модель Эрдеша-Реньи. А именно, фиксируется некоторый граф Н = (V, E), а затем ребра этого графа удаляются независимо друг от друга с одной и той же вероятностью. Понятно, что случай полного графа на п вершинах соответствует классической модели. Граф Н может как отображать некоторую реальную структуру, так и иметь геометрическое происхождение.

Именно такой случайный граф, который называется случайным дистанционным графом, рассмотрен в данной диссертации.

Дадим определение случайного дистанционного графа. Рассмотрим полный дистанционный граф на N вершинах Qfjst = ?fist), в котором.

Vdjst = {х = {хъ ., хп): Xi Е {0,1}, хг + .+хп = п/2}, ST = {{х, у} е V$jst х V§ st: <�х, у) = п/4}, где п G 4N, N = Сп'2, (х, у) — скалярное произведение векторов х и у. В случайном дистанционном графе G в модели Qdlst (N, p) ребро {х, у} проведено с вероятностью р тогда и только тогда, когда {х, у} е 8f^st. Если {х, у} ^ то и в случайном графе ребро {х, у} не проведено.

Рассмотрение подобных графов глубоко мотивировано задачами комбинаторной геометрии ([55] - [57]). Впервые полный дистанционный граф в геометрическом контексте рассмотрели в 1981 году П. Франкл и P.M. Уилсон. С помощью этого графа они показали, что хроматическое число пространства Жп растет экспоненциально ([56], [57]). В 1991 году Дж. Кан и Г. Калаи применили результаты Франкла и Уилсона для опровержения классической гипотезы Ворсука о том, что всякое ограниченное неодноточечное множество в Rn может быть разбито на п+1 часть меньшего диаметра ([55], [58] — [60]).

Также этот граф имеет непосредственное отношение к теории кодирования, в частности максимальные клики в нем это матрицы Адамара (см. [61], [62]).

Наконец, имеется некоторая литература о моделях случайных подграфов регулярных графов (у нас как раз частный случай такой модели). Однако наш граф достаточно сложный для анализа его свойств с помощью этих результатов напрямую (см. [63], [64], [65]).

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

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

1. Metropolis N., Ulam S., The Monte Carlo method, Journal of the American Statistical Association, 44 № 247 (1949), 335 341.

2. Севастьянов Б. А., Курс теории вероятностей и математической статистики, М.: Наука, 1982. Erdos Р., Ко С., Rado R., Intersection theorems for systems of finite sets, Quarterly Journal of Mathematics, Oxford, 12 № 2 (1961), 312 320.

3. Erdos P., On a combinatorial problem, I, Nordisk Mat. Tidskrift, 11 (1963), 5 10.

4. Erdos P., On a combinatorial problem, II, Acta Mathematica of the Academy of Sciences, Hungary, 15 (1964), 445 447.

5. Beck J., On 3-chromatic hypergraphs, Discrete Mathematics, 24 (1978), 127 137.

6. Spencer J., Coloring n-sets red and blue, J. Combinatorial Theory, Series A, 30 (1981), 112 113.

7. Эрдеш П., Спенсер Дж., Вероятностные методы в комбинаторике, М.: Мир, 1976.

8. Райгородский A.M., Вероятность и алгебра в комбинаторике, М.: МЦ-НМО, 2010.

9. Алон Н., Спенсер Дж., Вероятностный метод, М.: Бином, 2007.

10. Райгородский A.M., Модели случайных графов, М.: МЦНМО, 2011.

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

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

13. Erdos P., Renyi A., On the strength of connectedness of a random graph, Acta Math. Acad. Sci. Hungar., 12 (1961), 261 267.

14. Bollobas В., Random Graphs, New York: Academic Press, 1985.

15. Luczak Т., Janson S., Rucinski A., Random Graphs, New York: A Wiley-Interscience, 2000.

16. Колчин В. Ф., Случайные графы, M.: Физматлит, 2000.

17. Ford G., Uhlenbeck G., Combinatorial problems in the theory of graphs, /, Proc. Nat. Acad. Sci. 42 (1956), 122 128.

18. Gilbert E., Enumeration of labelled graphs, Canadian Journal of Math., 8 (1957), 405 411.

19. Austin Т., Fagen R., Penney W., Riordan J., The number of components in random linear graphs, Annals Of Math. Statistics 30 (1959), 747 754.

20. Schiirger K., Limit theorems for complete subgraphs of random graphs, Per. Math. Hungar, 10 (1979), 47 53.

21. Bollobas В., Threshold functions for small subgraphs, Math. Proc. Camb. Phil. Soc., 90 (1981), 197- 206.

22. Palka Z., On the number of vertices of given degree in a random graph, J. Graph Theory See Q4 (1982).

23. Barbour A., Poisson convergence and random graphs, Math. Proc. Camb. Phil. Soc., 92 (1982), 349 359.

24. Bollobas В., The evolution of random graphs, Trans. Amer. Math. Soc., 286 (1984), 257- 274.

25. Gilbert E., Random graphs, Annls. Math. Statist., 30 (1959), 1141 1144.

26. Stepanov V. E, Combinatorial algebra and random graphs, Theory Probab. Applies., 14 (1969), 373 399.

27. Stepanov V.E., Phase transitions in random graphs, Theory Probab. Applies., 15 (1970), 187 203.

28. Ivchenko G.I., The strength of connectivity of a random graph, Theory Probab. Applies., 18 (1973), 188 195.

29. Bollobas В., Degree sequences of random graphs, Discrete Math., 33 (1981), 1 19.

30. Luczak Т., Component behavior near the critical points of the random graph process, Random Structures and Algorithms, 1 (1990), 287 310.

31. Luczak Т., Pittel В., Wierman, J. The structure of a random graph near the point of the phase transition, Trans. Amer. Math. Soc. 341 (1994), 721 748.

32. Palasti I., A recursion formula for the number of Hamilton cycles having one edge in common with a given Hamilton cycle, Mat. Lapok 20 (1969), 289 -305.

33. Palasti I., On the common edges of the Hamilton cycles of a linear complete graph, Mat. Lapok 20 (1969), 71 98.

34. Palasti I., On Hamilton cycles of random graphs, Per. Math. Hungar. 1 (1970), 107 112.

35. Перепелица В. А., О двух задачах из теории графов, Докл. АН СССР 194 № 6 (1970), 1269 1272.

36. Moon J., Two problems on random trees, Lecture Notes in Mathematics, 303 (1972), 197- 206.

37. Wright E., For how many edges is a graph almost certainly Hamiltonian?, J. Lond. Math. Soc, 8 (1974), 44 48.

38. Wright E, Large cycles in labelled graphs, Math. Proc. Camb. Phil. Soc. 78 (1975), 7 17.

39. Ajtai M, Komlos J, Szemeredi E. The longest path in a random graph, Combinatorica 1 (1981), 1 12.46. de la Vega W, Long paths in random graphs, Studia Sci. Math. Hungat, 14 (1979), 335 340.

40. Bollobas В., Long paths in sparse random graphs, Combinatorica, 2 (1982), 223 228.

41. Bollobas В., Fenner Т., Frieze A., Long cycles in sparse random graphs, In Graph Theory and Combinatorics. Proc. Cambridge Combinatorial Conf. in honour of Paul Erdos, Academic Press (1984), 59 64.

42. Hoffman A., Singleton, R., On Moore graphs with diameters 2 and 3, IBM J. Res. Der. 4 (1960), 497- 504.

43. Damerell R., On Moore graphs, Math. Proc. Camb. Phil. Soc. 74 (1973), 227- 236.

44. Bannai E., Ito Т., On finite Moore graphs, J. Fac. Sci. Univ. Tokyo, Sect. IA. Math. 20 (1973), 191 -208.

45. Friedman H., A design for (d, k) graphs, IEEE Trans. Cornput. 15 (1966), 253- 254.

46. Friedman H., On the impossibility of certain Moore graphs, J. Combinatorial Theory (B), 10 (1971), 245 252.

47. Bollobas В., Riordan O., Mathematical results on scale-free random graphs. Handbook of graphs and networks, Wiley-VHC, Weinheim, 2003, 1 34.

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

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

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

51. Kahn J., Kalai G., A counterexample to Borsuk’s conjecture, Bulletin (new series) of the AMS, 29 (1993), 60 62.

52. Райгородский A.M., Вокруг гипотезы Борсука, Итоги науки и техникиСер. «Современная математика», 23 (2007), 147 164.

53. Raigorodskii A.M., Three lectures on the Borsuk partition problem, London Mathematical Society Lecture Note Series, 347 (2007), 202 248.

54. Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А., Теория кодов, исправляющих ошибки, М.: Связь, 1979.

55. Холл М., Комбинаторика, М.: Мир, 1970.

56. Chung F., Horn P., Lu L., The giant component in a random subgraph of a given graph, Proceedings of WAW2009, Lecture Notes in Computer Science 5427, 38 49.

57. Ajtai M., Komlos J., Szemeredi E., Largest random component of a k-cube, Combinatorica 2 (1982), 1 7.

58. Frize A., Krivelevich M., Martin R., The emergence of a giant component of pseudo-random graphs, Random Structures and Algorithms 24 (2004), 42 -50.

59. Феллер В., Введение в теорию вероятностей и её приложения, М.: 1964.

60. Karp R., The transitive closure of a random digraph, Random structures and Algorithms, 1 (1990), 73 94.

61. Ярмухаметов A.P., О связности случайных дистанционных графов специального вида, Чебышевский сборник, X, выпуск 1(29) (2009), 95 108.

62. Ярмухаметов А. Р., Древесные компоненты в случайных дистанционных графах спецаильного вида, Современная математика и ее приложения, 202 011), 98 110.

63. Ярмухаметов А. Р., Гигантская компонента в случайных дистанционных графах специального вида, Математические заметки, 3 (92) (2012), 463 479.

64. Ярмухаметов А. Р., О некоторых свойствах случайных дистанционных графов специального вида, Труды МФТИ, 4 № 1 (2012), 4 10.

65. Ярмухаметов А. Р., Гигантская и мелкие компоненты в случайных дистанционных графах специального вида, Математические заметки, 6 (92)2012), 949 953.

66. Yarmukhametov A.R., Tree components in random distance graphs of special form, Journal of Mathematical Sciences, 3 (187) (2012), 360 373.