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

На правах рукописи

Кокоткин Андрей Александрович

ВЕРОЯТНОСТНЫЙ ПОДХОД К ЗАДАЧАМ О ГРАФАХ РАССТОЯНИЙ И ГРАФАХ ДИАМЕТРОВ

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

Автореферат

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

2 О НОЯ 2014 005555742

Москва —

2014

005555742

Работа выполнена на кафедре анализа данных факультета инноваций и высоких технологий Федерального государственного автономного образовательного учреждения высшего профессионального образования "Московский физико-технический институт (государственный университет)".

Научный руководитель: доктор физико-математических наук, профессор Райгородскпй Андрей Михайлович. Место работы: Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Московский государственный университет имени М.В. Ломоносова'. Официальные оппоненты:

• доктор физико-математических наук, профессор, зав. кафедрой теории вероятностей п дискретной математики ФГБОУ ВПО "Иркутский государственный университет" Кузьмин Олег Викторович;

• кандидат физико-математических наук, доцент кафедры математических и естественно-научных дпецннлнн ФГБОУ ВПО "Российский государственный университет туризма и сервиса" Лавренченко Сергей Александрович.

Ведущая организация: Хабаровское отделение Федерального государственного бюджетного учреждения науки Института прикладной математики Дальневосточного отделения Российской академии наук.

Защита состоится 18 декабря 2014 года в 13:00 на заседании диссертационного совета Д 002.017.02 при Федеральном государственном бюджетном учреждении науки «Вычислительный центр имени A.A. Дородницына Российской академии наук» по адресу 119333, г. Москва, ул. Вавилова, д. 40, конференц-зал.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН и на сайте http://wvvvv.ccas.ru/.

Автореферат разослан 11 ноября 2014 года.

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

профессор В.В.Рязанов

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

Актуальность работы

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

Дискретная геометрия как наука оформилась на рубеже XIX ХХвв. Одним из ее основоположников можно считать Минковского1, который исследовал расположение целочисленных векторов по отношению к выпуклым телам в пространстве и доказал фундаментальную теорему о выпуклом теле. Столь же значимые результаты в этой теме получили Вороной2, Коркин, Золотарев3 и другие. Сейчас это отдельный раздел теории чисел и геометрии, называемый геометрией чисел4.

С геометрией чисел тесно связано еще одно направление дискретной геометрии. К этому направлению прежде всего относятся следующие три задачи. Первая классическая задача Ньютона о плотиеишеи упаковке шаров в пространстве5,6,7. Вторая задача, двойственная к первой, это задача о редчайшем покрытии пространств шарами. Наконец, третья задача, о контактном числе — наибольшем количестве шаров, касающихся данного шара в пространстве8,9.

Еще одно направление исследований в дискретной геометрии было инициировано Клейн, Эрдешем и Секерешсм в 1934 году, которые доказали существование такого числа N(n), что среди любых N точек общего положения на плоскости найдется выпуклый п-угольник10,11,12,13,14.

1II- Minkowski, Géométrie lier Zahlen. RG Tellblier, Leipzig-Berlin. 1953.

2Г. Вороной Собрание сочинений в .4-х томах, 1952.

3Л. Korkine, G. Zolotaleff, Sur les formes quadratiques positives. Math. Л1111. 11 (2). 1877. 212-292.

4Дж. Кассслс, Геометрия чисел, Москва, Мир, 19G5.

5Л. Тот, Расположения на плпс.костин. сфере и в пространстве, Москва, Фнзмалит, 1958.

6К. Роджерс, Укладки и покрытия, Москва, Мир, 19G8.

7Дж. Конвей, II. Слоэн, Упаковки шаров, решетки и группы, Москва, Мир, 1990.

8К. Schutte, B.L. van der Waordon, Das Problem der dreizehn Kugeln. Math. Л1111. 125, 1953. 325 331.

90. Мусин, Проблема двадцати пяти сфер. УМН. 58 (352). 2003, 153-154.

10Р. Erdôs. G. Szekeres, A comhinatorial problem in geometry, Compositio Math.. 2. 1935, 4G3-470.

nIIarborth, Ileiko, Konvexe Funfecke in ehenen Punktmengen, Elem. Math. T. 33 ( 5), 1978. 11G-118.

12J. Ilorton, Sets with no empty mirera 7-gons, Caliadian Math. Bulletin T. 2G (4), 1983. 4S2-484.

«M. Ovcrmars, Finding sets of points without empty convex 6-gons, Discrète and Computational Geometry T. 2!) (1), 2003, 153-158.

14B. Кошелсв Задача Эрдаиа Ссксрсша о nt/стых шестиугольниках па плоскости, Моделирование и анализ информационных систем, lfi (2). 2009, 22-74.

Следующий класс проблем дискретной геометрии также предложен Эрдешим. Первый вопрос, который был им поставлен, — о наибольшем числе единичных расстояний в множестве из п точек на плоскости и в пространстве15. Второй, не менее важный, наоборот, о числе различных расстояний в таком n-точечном множестве16'17.

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

единица .

Теперь очертим круг задач, характерных для вероятностной комбинаторики. Основной метод, используемый здесь, это вероятностный метод. Его основоположником считается Эрдеш21. Вероятностный метод позволил доказать или опровергнуть ряд гипотез, державшихся долгое время22'23.

Одним из основных объектов и одновременно инструментов исследования становится случайный граф. В 1959 году Эрдеш и Реньи24 дают первую модель случайного графа. Сразу же возникает огромное количество задач об исследовании самых разных характеристик случайного графа, о критических вероятностях для всевозможных его свойств, о рас-

15Р. Erdós, On a set of distances of n points. Aniel. Math. Monthly. 53, 1946, 218-250.

16P. Brass, W. Moser, J. Pach, Research problems in discrete geometry, Springer, New York, 2005.

17A.M. Raigorodskii, Coloring Distance Graphs and Graphs of Diameters, Thirty Essays on Geometric Graph Theory, J. Pach ed., Springer, 2013, 429 - 4C0.

18K. Borsuk, Diri Satze iibtr die n-dimensionale eukltdische Sphare, Fundamenta Math., 20, 1933, 177-190.

19P.K. Agarwal, J. Pach, Combinatorial Geometry, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley and Sons, 1995.

20A.M. Raigorodskii, Three lectures on the Borsuk partition problem, London Mathematical Society Lecture Note Series, 347 (2U07), 202-248.

21P. Erdós, Some Remarks on the Theory of Graphs, Bulletin of the American Mathematical Society, 53. 1947, 292-294.

22П. Эрдёш, Дж. Спенсер, Вероятностные методы в комбинаторике Издательство Мир, 1976.

23Н. Ллон, Дж. .Спенсер, Вероятностный метод Бином. Лаборатория знаний, 2007.

24Р. Erdós, A. Kcnyi, On random graphs, I, Publ. Math. Dcbrcccn, 0, 1959, 290 297.

прсдсленни какой-либо случайной величины на этом графе. Наша работа посвящена двум свойствам: "быть графом расстояний" и "быть графом диаметров".

В настоящее время теория графов переживает очередной расцвет в связи с применением ее к исследованиям социальных и биологических и информационных сетей. Теперь, когда стало возможным эмпирически вычислить некоторые характеристики графа, описывающего сеть Интернет, и графов других социальных сетей, выяснилось, что модель Эрдеша-Реньи ни при каких параметрах (а ои в этой модели всего один вероятность ребра) не может служить сколько-нибудь адекватной моделью для этих графов. В 1999 году Барабаши и Альберт25 предложили новую модель случайного графа, а Боллобаш26 и Риордан27 уточнили се и доказали, что в ней выполняется по крайней мере два ключевых свойства веб-графа: степенной закон распределения вершин н малый диаметр. С тех пора эта тема получила широкое развитие, были предприняты как

ч 9Я

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

Цель работы

Цель работы состоит в исследовании двух различных свойств случайного графа в модели Эрдеша-Реньи. Во-первых, изучается свойство быть изоморфным графу расстоянии; во-вторых, — свойство быть изоморфным графу диаметров.

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

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

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

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

25A.-L. Barabasi, R. Albert. Emergence of sealing in random networks Science, 28fi, 19!)'J. 500 1)12.

26B. Bollobas, Random Graphs, Cambridge Univ. Press, Second Edition, 2001.

27B. Bollobas, O.Riordan The degree, sequence nf a scale-free random graph process Random Structures and Algorithms, 1S(3), 2ПП1, 27Э-29П.

2SA.M. Райгородский, Модели интернета, Интеллект, Долгопрудный, 2013.

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

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

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

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

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

Апробация работы

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

— на кафедральном семинаре кафедр дискретной математики и анализа данных (ФИВТ, МФТИ, 2012 2014);

— на семинаре "Вероятностные и алгебраические методы в комбинаторике" под руководством профессора A.M. Райгородского (механико-математический факультет МГУ, 2009-2012);

— на международной конференции "Fete of combinatorics and computer science" (Кестхей, Венгрия, 11-15 августа 2008);

— на международной конференции "Четвертая польская конференция по комбинаторике" (Бедлево. Польша, 17-21 сентября 2012).

Публикации

Результаты диссертации опубликованы в 5 работах автора (4 из которых входят в перечень ВАК), список которых приведен в конце автореферата.

Структура диссертации

Диссертация состоит из введения, трех глав, заключения и списка литературы, насчитывающего 68 наименовании. Общин объем диссертации составляет 69 страниц.

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

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

Содержание главы 1

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

Хроматическое число пространства Rd — это наименьшее ко-

личество цветов, в которые можно так покрасить чтобы среди точек одного цвета не нашлось пары точек на расстоянии единица, то есть

= min {k е N : 3VU ..., Vk, ^ = V U ... U Vk,

Vi, Vx,y e Vi, p{x,y) ф 1},

где p — обычное евклидово расстояние.

Легко показать, что для любого d величина конечна. Проблема

отыскания хроматического числа пространства была впервые поставлена на рубеже 40х-50х годов XX века,. Несмотря на значительный интерес, вызванный этой проблемой, она до сих пор, по существу, остается нерешенной. Конечно, ^(R1) = 2, однако уже для плоскости лучшее, что мы знаем, это оценка

4 < х(К2) ^ 7. Для трехмерного пространства мы имеем29'30

6 «С х(К3) < 15,

29D. Coulson, A 15-colouring of 3-space omitting distance one. Discrete mathematics, 2Г>6. 2002. 83-90.

30O. Nechushtan, Note on the. space chromatic number. Discrete Mathematics, 25G. 2002. 499-507.

41 42

наконец для растущей размерности '

(1.239. :. + o(l))d < х(^) ^ (3 + o(l))d.

Поставленная задача может быть переформулирована в терминах теории графов. Прежде всего дистанционным графом (или графом расстояний) назовем конечный граф G = (V, Е), вершины которого суть точки евклидова пространства, а ребра соединяют только пары точек, отстоящих друг от друга на расстояние единица. Иными словами,

У С Rd, \V\ < оо, ЕС {(х,у) eVxV: р(х,у) = 1}.

Напомним, что хроматическое число x{G) графа G = (V, Е) — это наименьшее количество цветов, в которые можно так покрасить его вершины, чтобы вершины одного цвета не соединялись ребром, то есть

x(G) = min{fceN: 3Vu...,Vk, V = V1U...UVk,

Vг, Vx,y € Vi, (x,y)£E}.

П. Эрдеш и H. де Брёйн33 фактически доказали, что = max\;(G),

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

В этой главе мы сначала рассматриваем случай евклидовой плоскости. Тот факт, что Х(К2) ^ 7, означает, конечно, что для любого графа расстояний G = (К, Е) на плоскости x{G) ^ 7. Как следствие, a(G) ^ ф-, коль скоро через u(G) мы обозначили число независимости графа G, то есть наибольшее количество его вершин, никакие две из которых не соединены ребром:

a(G) = шах{|К'| : V' С V, Vx,y е V, (х,у) ф Е}.

31А.М. Райгородскнй, Проблема Борсука и хроматические числа метрических пространств, Утехи матем. наук, 5(>(1). 2001. 107-14U.

32D. Larman, С. Rogers, The realization of distances within sets in Euclidean space, Mathematika, 19, 1U72. 1-24.

33N.G. de Bruijn and P. Erdôs. A colour problun for infinité gmphs and a problem in the theory of relations. Troc. Koniiikl. Nederl. Aead. Wct., Scr. Л, 54 (5), 1У51, 371 373.

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

Теоремы 1—4. Пусть к 6 {1,2,3,4}. В любом графе расстояний G = (V, Е) па п вершинах найдется такой индуцированный подграф G' = (V, Е'), что \V'\ ^ и x(G') ^ к, где я = 4.36...

Для доказательства этих теорем использовался новый результат, являющийся усилением известной теоремы Ла.рмана-Роджерса34.

Теорема 8. Пусть в задан некоторый граф расстояний G = (V, Е), = п. Предположим, существуют такие числа к 6 N и ь>о € (0,1), что для любого индуцированного подграфа G' = (V', Е') с \V'\ ^ [г/оп] выполнено x{G') > к. Тогда для всякого набора измеримых множеств Si, S2,..., Sk в Kd с условием, что множество S = Si U S2 U ... U Sk имеет верхнюю плотность v ^ щ, верно, что каково бы пи было а > О, найдется Si, на котором реализуется расстояние а.

Наиболее интересным является случай к = 4. Фактически он означает, что в каждом графе расстояний на плоскости есть индуцированный подграф, который почти целиком совпадает с исходным графом (содержит не менее 91.7% его вершин) и допускает раскраску в 4 цвета. Если бы в этом утверждении величину 91.7 удалось заменить на 100, то, ввиду теоремы Эрдеша-де Брёйна, это бы означало, что х(®2) = 4.

Зачастую задачи теории графов допускают нетривиальную интерпретацию в терминах случайного графа. Напомним, что одной из наиболее популярных моделей случайного графа является модель, предложенная Эрдешем и А. Реньн35 на рубеже 50х-60х годов XX века. Речь идет о вероятностном пространстве G(n,p) = (fin, Вп,Рп). Здесь

П„ = {G = (V, Я) : |V| = n}-

34D. Lannan, С. Rogers, The realization of distances within sets in Euclidean space, Mathematika, 19, 11)72, 1-24.

35B. Bollobas, Random Graphs, Cambridge Univ. Press, Second Edition, 2001.

множество всевозможных графов на п вершинах (без петель и кратных ребер), сигма-алгебра В„ представляет собой множество всех подмножеств i2„, а

P„(G)=pl*l(l-p)c2-l*l.

Иначе говоря, можно считать, что ребра случайного графа появляются независимо друг от друга с вероятностью р. Заметим, что в модели Эрдеша-Реньи величина р может зависеть от п.

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

р'{п) =

= sup |р € [0,1] : P„(G реализуется в R2 как граф расстояний) > ^|.

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

Теорема 5. При р = где с < 1, выполнено

Рn(G реализуется на плоскости как граф расстояний) —> 1, п —> оо.

Теорема 6. При р = где с > tg = 14.797..., выполнено

Рn(G реализуется на плоскости как граф расстояний) —> 0, п —» оо.

Теоремы 5 и 6, доказанные в параграфе 1.4, означают, что — ^ р"(п) ^ со сколь угодно малым положительным е и п ^ щ(е). Тем самым, мы знаем порядок роста пороговой вероятности. В параграфе 1.5 мы вводим более общую величину

Р'Лп) =

= sup € [0,1] : P,,(G реализуется в как граф расстояний) > ^ j-. Нам удалось показать, что для размерностей 3-8 также верна

Теорема 11. Положим

с3 = 55.272 ..., С\ — 164.528 ..., с5 = 504.285

с6 = 1365.170..., с7 = 3624.758..., с8 = 8675.785 ... Тогда при каждом d и р = где с > с^, выполнено

Pn(G реализуется в как граф расстояний) —> 0, п —> оо. Иными словами,

1 - е cd + e

-^ Pd(n) ^-.

п п

причем величина c,i растет как экспонента. В одномерном случае порядок роста другой. В пункте 1.5.2 мы доказали, что имеет место следующая

Теорема 12. Для любого г > 0 существует такое щ, что при всех п ^ щ выполнено

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

</6In2 — £ . \/6Ы2 + е

„4/3 „4/3 •

Содержание главы 2

Вторая глава (как и третья) посвящена исследованию некоторых вероятностных характеристик, связанных с классической проблемой Бор-сука. Напомним, что эта проблема состоит в отыскании числа Борсука — величины /(d), равной минимальному количеству частей меньшего диаметра, на которые можно разбить произвольное множество диаметра 1 в пространстве R'':

f{d) = min{/ : V Г2 С Rd, diamfi = 1, 3 Пь ..., Qf : П = П^.-.иП/,

V г diam П; < 1}.

Гипотеза Борсука30, предложенная своим автором в 1933 году, состояла в том, что /(d) = d+1. И ровно шестьдесят лет эта гипотеза оставалась ни

36K. Borsuk, Drei Sätze über die Tl-dimensionale euklidische Sphäre, Fundamenta Math., 20, 1933

доказанной, нн опровергнутой. Лишь в 1993 году Кан и Калан37 нашли контрпримеры к гипотезе в размерностях d ^ 2015. Сейчас известно, что гипотеза Борсука верна при d ^ 3 и ложна при d ^ 6438.

С проблемой Борсука тесно связано понятие графа диаметров. Назовем графом диаметров в Rd любой граф G = (V,E), вершины которого — точки Rd, а ребра — пары вершин, отстоящих друг от друга на максимальное в множестве вершин расстояние:

V С Rd, \V\ < оо, Е = < {х, у} : |х - у| = diam V := max |х - у| 1 .

I. х,уЕК J

Понятно, что минимальное число частой меньшего диаметра, на которые разбивается V (число Борсука множества V), — это в точности хроматическое число x{G) графа G. Однако было бы некорректно сказать, что f(d) — это максимум таких хроматических чисел. Дело в том, что равенство хроматического числа числу Борсука справедливо лишь в случае конечных множеств; для бесконечных множеств равенства, вообще говоря, нет: например, если взять в качестве V сферу в Rd, то очевидно, что хроматическое число ее графа диаметров (являющегося паросочетанием) равно двум, тогда как ее число Борсука есть d + 1 ввиду классической теоремы Борсука-Улама-Люстериика-Шнирсльмана39.

На плоскости н в пространстве гипотеза Борсука доказана. Более того, существует достаточно много примеров графов диаметров в R2 и R3 с хроматическими числами 3 и 4 соответственно. Интересно оценить, стало быть, насколько эти примеры часты или редки.

Положим

ud(n,p) = max {k : Р„,р (3 H = (W, F) С G : \W\ = k,

H = G\w, H - граф диаметров в x{H) = d + l) > ^ j ,

37J. Kahn, G. Kalai, A counterexample to BoTsuk's conjecture. Bull. Amer. Math. Soc. (N.S.), 29(1), 1УУЛ, (i0-ti2

38T. Jenrich, Л 64-dimensional two-distance counterexample to Borsuk's conjecture, 2013, http://arxiv.org/abs/1308.020Gv5.

39J. MatouSek, Using the Borsuk-Ulam theorem, Universitext, Springer, Berlin, 2003.

u'd(n,p) = шах {А;: Р„,р (3 Я = (W, F) С G : \W\ = k, Н = G|jv, Я — связный граф диаметров в Rd, х{Н) = d + l) >

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

Рп,р (3 Я = (W,F)CG: \W\ = к, Я = G\w, Я - граф диаметров в

то полагаем u,i(n,p) = 0 и аналогично поступаем с величиной u'd(n,p).

В этой главе сформулированы и доказаны теоремы, полученные нами в [1, 3], верные для размерностей d = 2, d = 3. В том случае, когда теоремы верны для обеих величин udl и u'd, мы пишем ud.

Теорема 13. Пусть р = о(^). Тогда при всех достаточно больших п £ N выполнено и\{п,р) = 0.

Теорема 14. Пусть q := 1 — р = о (¿у)- Тогда при всех достаточно больших п £ N выполнено U2(n,p) = 3.

Теорема 15. Пусть q = о но при этом qn15 -» оо. Тогда при всех достаточно больших п £ N выполнено и\{п,р) = 4.

Теорема 16. Положим т(п) = рп и а(п) = ginn. Пусть т(п) и а(п) стремятся к бесконечности с ростом п. Тогда для любого £ > 0 существует такое по, что при п ^ щ выполнено

Rd, x(H) = d + l)

U2{n,p) ^ (2 + е) log J_(np).

Теорема 17. Полоэюим т(п) = ^^ и cr(n) = ginn. Пусть т(п) и сг(п) стремятся к бесконечности с ростом п. Тогда для любого £ > 0 существует такое щ, что при п ^ по выполнено

Теорема 18. Зафиксируем некоторое число а € (0, и положим т(п) = рп°. Пусть с некоторым С > 0 начиная с некоторого п выполнено 1 < т(п) < С. Тогда для любого е > 0 существует такое щ, что при п ^ щ имеет место неравенство

«/ \ /„ „ .Inn

и2{п,р) ^ (2 — 2а — £)-.

Р

Теорема 19. Пусть найдется такое с < I, что р < Тогда при всех достаточно больших п 6 N выполнено и${п,р) = 0.

Теорема 20. Пусть q = о (^fs) • Тогда при всех достаточно больших п € N выполнено щ(п,р) = 4.

Теорема 21. Положим т(п) = рп и <т(п) = ginn. Пусть т(п) и а(п) стремятся к бесконечности с ростом п. Тогда для любого е > 0 существует такое щ, что при п ^ щ выполнено

и"з(п,р) ^ (2 + е) log 1 (пр).

1-р

Теорема 22. Пусть для всякого а > 0 выполнено рпа —» оо и ginn —¥ ос при п —> оо. Тогда для любого е > 0 существует такое щ, что при п ^ щ выполнено

из(п.р) ^ (2 - е) log_i_(np).

Теорема 23. Зафиксируем некоторое а € (0, и положим т(п) = рпа. Пусть с некоторым С > 0 начиная с некоторого п выполнено 1 < т(п) < С. Тогда для любого е > 0 существует такое щ, что при п ^ по имеет место неравенство

иЦп,р) > (2-4а-е)—.

Видно, что при разумных условиях на асимптотику вероятности ребра теоремы 16 н 17 дают асимптотику величины и*2(п,р) и эта асимптотика имеет вид 2 log_i_ (пр). Более того, если р стремится к нулю, то в условиях

1-Р

теоремы 17 выполнено 21ogj_(np) ~ 2^. Поэтому теорема 18 просто

1-Р р

дает аналог оценки из теоремы 17, который лишь в константу раз хуже, но работает на большем диапазоне значений р. Полностью аналогичная картина имеет место в теоремах 21-23. При этом утверждения теорем 1G и 21 совсем идентичны, в теореме 22 практически та же оценка, что и в теореме 17, но более узкий диапазон допустимых вероятностей ребра, а в теореме 23 и диапазон уже, чем в теореме 18, и оценка послабее.

В параграфе 2.3 мы доказываем теоремы 13-18, в которых идет речь о величине и"2{п,р). Величине и*3(п,р) мы посвящаем параграф 2.4, здесь доказаны теоремы 19-23. Содержание главы 3

В этой главе сформулированы и доказаны результаты о величинах ud{n,p) и u'd(n,p), введенных в главе 2, верные для произвольной фиксированной размерности. Эти результаты мы получили в работе [5|.

Теорема 24. Пусть для всякого а > 0 выполнено рпа —> оо и ginn —>•

00 при п —> оо. Тогда для любого d и для любого е > 0 существует такое по, что при п ^ щ выполнено

ud{n,p) > (2 - е) log_j_(np).

Таким образом, нижняя оценка справедлива в любой размерности, но в чуть разных условиях (для размерности 2 ограничений меньше). Повторим, однако, что если для размерностей 2 и 3 эта оценка выполнялась также для величины со штрихом, то при d ^ 4 метод немного другой и на величину со штрихом он не распространяется.

Теорема 25. Зафиксируем некоторое а € (0, j) и положим т(п) = рпа. Пусть с некоторым С > 0 начиная с некоторого п выполнено

1 < т(п) < С. Тогда для любого d и любого £ > 0 существует такое по, что при п ^ по имеет лгесто неравенство

v , .Inn Ud(n,p) > (2 - 2 а-г)-.

Теорема 26. Пусть р — это либо константа, либо произвольная функция, которая стремится к нулю при п оо, но при этом ограничена снизу величиной где с > 1. Тогда для любого d и для любого е > О существует такое по, что при щ выполнено

«З(п.Р) < (2 + e)(d + 1) log.(np).

i-р

Теорема 26 дает абсолютно универсальную верхнюю оценку, работающую даже в более широком диапазоне, нежели теорема 1G. В этом ее большой плюс. Однако при d = 2,3 значение полученной в ней оценки несколько хуже ранее известных. Следующая теорема устраняет эту проблему ценой сокращения диапазона допустимых вероятностей ребра.

Теорема 27. Пусть р — это константа. Тогда для любого d и для любого е > 0 существует такое щ, что при п ^ по выполнено

ud(n'P) ^ (2 + е)

logi(np).

i-р

Теорема 27 отлично согласуется с теоремами 16 и 21. Тем не менее, в ней р — константа. Слегка оторваться от этого ограничения можно. Но сделать это довольно тяжело, т.к. доказательство теоремы 27 опирается на ряд тонких утверждений, многие из которых с трудом обобщаются на случаи непостоянных вероятностей. Отмстим также, что при d ^ 4 нижние и верхние оценки начинают отличаться друг от друга, так что асимптотику найти уже не удастся.

Наконец, обобщением и даже усилением теорем 13 и 19 служит следующая

Теорема 28. Пусть d ^ 3 и найдется такое с < 2(с(— 1)1п(й— 1), что р < Тогда при всех достаточно больших п € N выполнено и^(п,р) = 0.

Теоремы 26, 28 доказаны в параграфе 3.2, теоремы 24, 25 — в параграфе 3.3, наконец, теореме 27 посвящен четвертый параграф. В пятом параграфе рассмотрены сложности обобщения последней теоремы на случай убывающей вероятности ребра р.

В заключении даны возможные направления дальнейших исследований.

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

Автор признателен профессору Андрею Михайловичу Райгородскому за постановку задач и неоценимую помощь в работе.

Список публикаций по теме диссертации

[1] A.A. Кокоткин, A.M. Райгородский, О реализации случайных графов графами диаметров, Труды МФТИ, 4 (2012), N1. 19 - 28.

[2] A.A. Кокоткин, A.M. Райгородский, О больших подграфах графа расстояний, имеющих маленькое хроматическое число, Современная математика. Фундаментальные направления, 51 (2013), 64 - 73.

[3] A.A. Кокоткин, A.M. Райгородский, О реализации подграфов случайного графа графами диаметров на плоскости и в пространстве, Труды МФТИ, 6 (2014), N2, 44 - 60.

[4] A.A. Кокоткин, О реализации подграфов случайного графа графами диаметров в евклидовых пространствах, Доклады РАН, 456 (2014), N6, 1 - 3.

[5] A.A. Кокоткин, О больших подграфах графа расстояний, имеющих маленькое хроматическое число, Математические заметки, 96 (2014), N 2, 318 - 320.

Подписано в печать 16.10.2014г. Бумага офсетная. Печать цифровая. Заказ № 119 Тираж 100 экз. Типография «КОПИЦЕНТР» 119234, г. Москва. Ломоносовский пр-т, д.20 Тел. 8 (495)213-88-17