Предельные распределения характеристик случайных дистанционных графов тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

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

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

01.01.05 — теория вероятностей и математическая статистика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

На правах рукописи УДК 519.21

Ярмухаметов Андрей Ринатович

Москва — 2012

1 о ПОР, ¿012

005055043

005055043

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

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

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

доктор физико-математических наук Кабатянский Григорий Анатольевич, Институт проблем передачи информации имени A.A. Харкевича РАН, главный научный сотрудник

кандидат физико-математических наук Шабанов Дмитрий Александрович, Московский государственный университет имени М.В.Ломоносова, механико-математический факультет, ассистент кафедры теории вероятностей

Хабаровское отделение института прикладной математики Дальневосточного отделения РАН

Защита диссертации состоится 7 декабря 2012 года в 16 часов 45 минут на заседании диссертационного совета Д 501.001.85 при Московском государственном университете имени М.В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, механико-математического факультет, аудитория 16-24.

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

Автореферат разослан 6 ноября 2012 г.

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

В.Н. Сорокин

Актуальность

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

Активное изучение случайных графов началось после того, как П. Эр-деш установил, что вероятностный метод помогает решать многие задачи экстремальной теории графов. П. Эрдеш и А. Реньи в 1959 году 12 рассмотрели модель случайного графа G(N,p), в которой ребра в полном графе на N вершинах проводятся независимо друг от друга с вероятностью р = p(N). Огромное количество работ посвящено различным задачам, связанным с исследованиями случайного графа G(N,p). Среди них отметим работы Б. Боллобаша, С. Шелла, Е. Семереди, Дж. Спенсера, 3. Палка, А.Д. Барбура, E.H. Гильберта, И.Н. Коваленко, Г.И. Ивченко, В.Ф. Колчнна, В.Е. Степанова и др.

Диссертация посвящена изучению экстремальных характеристик случайных подграфов полного дистанционного графа Qn, у которого вершины — векторы из {0, 1}™ с условием ||.т|| = у/п/2. а ребра — пары векторов, отстоящих друг от друга па расстояние у/п/2. В дальнейшем вероятностное пространство таких случайных подграфов называется пространством случайных дистанционных графов и обозначается Qdist(N,p), где N — количество вершин в полном графе, р — вероятность появления ребра в случайном подграфе этого графа. Таким образом, модель, рассматриваемая в работе, является обобщением классической модели Эрдеша - Реньи.

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

1Erdos P., Rcnyi A., On random graphs /, Publ. Math. Dcbrcccn, 6 (1959), 290 - 297.

2 Erdös P., Rcnyi A., On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutatö Int. Közl., 5 (1960). 17 -Gl.

^РайгородскиП A.M., Проблема Барсука и хроматические числа метрических пространств,

Впервые полный дистанционный граф Qx, свойства которого изучаются в диссертационной работе, в геометрическом контексте рассмотрели в 1981 году П. Франкл и P.M. Уилсон4. С помощью этого графа они показали, что хроматическое число пространства Rn растет экспоненциально с ростом п. В 1991 году Дж. Кан и Г. Калаи° применили результаты Франкла и Уилсона для опровержения классической гипотезы Борсука о том. что всякое ограниченное неодноточечное множество в К" может быть разбито на п + 1 часть меньшего диаметра. Таким образом, изучение внутренней структуры дистанционного графа и его подграфов играет исключительно важную роль.

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

В диссертации получена пороговая вероятность для свойства связности случайных графов в вероятностном пространстве Gdlst(N,p), а также пороговая вероятность для возникновения гигантской компоненты в них. В работе также изучено предельное распределение числа древесных компонент в случайном дистанционном графе в зависимости от вероятности ребра р. Кроме того, доказано, что, как и в классической модели Эрде-ша - Реньи, фазовый переход от связности к ее отсутствию совпадает с переходом от связности к наличию изолированных вершин. Также получен результат о предельной вероятности связности в предположении, что вероятность ребра находится "внутри" этого фазового перехода.

Цель работы

Цель данной диссертации состоит в нахождении пороговых вероятностей связности и наличия "гигантской компоненты" случайного графа в модели Qdlst{N,p), исследовании предельного распределения числа древесных компонент в случайном графе в этой же модели в зависимости от вероятности ребра р.

Успехи Матсм. Наук, 56(1) (2001), 107 - 146.

1 Fratikl P., Wilson R., intersection theorems with geometric conscquences, Combinatorica. 1 (1981). 357 - 368.

5Kahn J.. Kalai G.. A counterexample to Borsuk's conjecture, Bulletin (new scries) of the AMS. 29(1) (1993). GO -62.

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

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

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

1. Доказано, что пороговая вероятность связности случайного графа в модели равна 1п М/Ых, где Л^ - степень вершины полного дистанционного графа (который является регулярным).

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

3. Доказано, что пороговая вероятность наличия гигантской компоненты в случайном графе в модели д4ы{М,р) равна

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

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

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

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

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

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

По теме диссертации были сделаны доклады на следующих семинарах механико-математического факультета МГУ имени М.В. Ломоносова:

• Кафедральном семинаре кафедры математической статистики и случайных процессов под рук. профессора A.M. Зубкова (2009 и 2011 гг.),

• Семинаре под руководством профессора A.M. Райгородского (2008 - 2011 гг., неоднократно)

Результаты диссертации докладывались на десятом международном семинаре "Дискретная математика и ее приложения" (г. Москва, 2010 г.), на международной конференции "8-я французская конференция по комбинаторике" (г. Париж, Франция, 2010 г.), на международной конференции "Конечные и бесконечные множества", посвященной 80-летию Хайнала (г. Будапешт, Венгрия, 2011).

Работа автора поддержана грантами РФФИ 09-01-00294 и 12-01-00683.

Публикации

Результаты диссертации опубликованы в 6 работах автора, из них 4 — из списка ВАК. Работ в соавторстве нет. Список работ приведен в конце автореферата.

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

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

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

В гласе 1 сформулированы основные определения и результаты диссертации. Для точных формулировок этих результатов введем ряд обозначений. Пусть IV е N. Рассмотрим множество ПЛ- всех графов С = (1дг, Е) без петель, кратных ребер и ориентации с множеством вершин = {1,..., ЛГ}. Назовем случайным графом в модели Эрдсша-Реиьи вероятностное пространство

С(ЛГ,р) = (Пх,?х,Гх.р): где = 2а", Р„.р(С) = р\Е\1~р)с1-\Е\_ р € (о, 1).

Положим п = 4к, к 6 N. N = С^2 и рассмотрим полный дистанционный граф Он = (Улг,5д'), у которого

Ул- = {х= {хи...,хп) + ... + хп = 2к = ^у.

= {{х,у} Ул- : (х.у) = к = ,

где (х, у) — скалярное произведение векторов х и у.

Таким образом, вершины полного дистанционного графа являются точками из {0,1}п и этих вершин ровно N. При этом ребра графа 9к суть пары его вершин, удаленных друг от друга на расстояние у/Ц. Именно этим и обусловлено название графа. Изучение такого рода графов мотивировано не только задачей о хроматическом числе пространства, но и исследованиями равновесных кодов с запрещенным расстоянием'.

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

где — множество всех остовных подграфов <3 = (Удг, Е) полного дистанционного графа =

= р|£|(1 - Р) где р € (01

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

Граф gN - регулярный. Обозначим через N\ степень каждой из его вершин. В соответствии с формулой Стирлинга

/ »\2 2\/21п2 N .л , г ,дт \ а/ \/7Г \/1п N

где S^N) = о(1).

Имеется некоторая литература о моделях случайных подграфов регулярных графов (у нас как раз частный случай такой модели)8. Однако наш граф достаточно сложный для анализа его свойств с помощью этих результатов напрямую.

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

В дальнейшем будем употреблять выражение "модель Gdlst{N,p)'\ подразумевая всю последовательность вероятностных пространств Qdist(N,p) при N Є N.

Будем говорить, что случайный граф в модели Qdlst{N,p) обладает некоторым свойством асимптотически почти наверное (кратко а.п.н.), если вероятностная мера T>n,p множества графов из Г2дг, обладающих этим свойством, стремится к 1 при N ^ ос.

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

Теорема 1. Пусть р, = Тогда

а) если существует такое с > 1, что при всех достаточно больших N выполнено неравенство р > ср„, то случайный граф в модели Qd,st{N,p) а.п.н. связен;

б) если существует такое с < 1, что при всех достаточно больших N выполнено неравенство р < ср., то случайный граф в модели gdlst(N,p) а.п.н. не связен.

8Chung 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.

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

N

Е

к=1

С* (!-?)*<"-*>.

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

При доказательстве пункта б) установлено, что при данных условиях количество изолированных вершин в случайном графе в модели 0агз1(1\[,р) стремится к бесконечности.

При доказательстве пункта а), так же как и в классическом случае устанавливается, что математическое ожидание количества компонент связности размера, меньшего чем ЛГ, стремится к нулю. Среди всех промежуточных результатов выделим следующее важное свойство полного дистанционного графа.

Утверждение 2.2. Число общих соседних вершин для двух любых различных вершин графа Як при достаточно больших IV не меньше, чем

ЛГ, = 10- М

1пЛГ

С помощью этого свойства и регулярности доказывается, что количество ребер между любым ¿-элементным подмножеством вершин графа и его дополнением не меньше, чем тт(г, N — г)-^1. Глава 3 посвящена теореме о предельном распределении количества древесных компонент в случайном графе в модели 0аы(М,р). Приведем

формулировку теоремы.

Теорема 2. Пусть Х^.к — число к-вершиппых древесных компонент (к >2) в случайном графе С в модели Оаы(М.р). Тогда имеют место следующие результаты:

1. если р = о(■ Л^-1), то а.п.н. имеет место равенство Х^.к = 0;

2. если р ~ с-для некоторого с > 0, то величина Xдгд. ил«е-ет асимптотически пуассоновское распределение с параметром

ск-1кк-2

3. если р ■ N^1 ■ N1 +00 и ркЫ^ - 1п N - (к - 1) 1п 1п N -> -эо при Л^ —> оо , то для любого фиксированного / б К а.п.н. выполняется неравенство Xлг,* > I;

4. если рАгА/-! — 1п N — (к — 1) 1п1п N -4 с при N->-00 для некоторого с € К, то величина имеет асимптотически пуассоновское pacnpeдeJleнue с параметром

л - е"с •

5. если ркЫ\ — 1пN — (к — фпЬД' —¥ 4-ос при N —» ос, то а.п.н. имеет место равенство Х^.ь = 0.

Результат теоремы очень похож на результат для классической модели Эрдеша - Реньи, хотя и с некоторыми отличиями. Распределение количества древесных компонент в классическом случае можно подсчитать, используя формулу Кэли, утверждающую, что число различных деревьев на к нумерованных вершинах равняется кк~2. Откуда следует, что количество различных /с-вершинных деревьев в полном графе размера N равняется В диссертации доказано утверждение о

количестве деревьев в графе

Утверждение 3.2. Обозначим через число различных к-

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

1. Пусть 2 < к < АГ/74. Тогда при достаточно больших N имеет место равенство

= ЛГ - ЛГ*-1 ■ 1 + й''(А0).

где |б'(Л0| <

2. Пусть 2 < к < N. Тогда имеет место неравенство

Tk.N<N■Nt1■l^■

Это утверждение применяется также в теореме о наличии гигантской компоненты в случайном дистанционном графе, содержащейся в главе 4.

Теорема 3. Пусть р, = Тогда:

а) если существует такое с < 1, что при всех достаточно больших N выполнено неравенство р < ср„, то найдется такая константа /3 > О, что случайный граф в модели Яаш(АТ,р) а.п.н. будет состоять из компонент, количество вершин в каждой из которых не превосходит р 1п /V;

б) если существует такое с > 1, что при всех достаточно больших N выполнено равенство р = ср„, то найдется такая константа 0 > О, что случайный граф в модели ЯЛЫ{Ы,р) а.п.н. будет содержать ровно одну компоненту размера

N(1 - 1С) + о{№-8),

где £с = 1 ]Сь=1 ^тг(се~с)к, и при этом все остальные компоненты будут иметь размер, не превосходящий /31п N.

Пункт а) теоремы доказывается с помощью теории ветвящихся процессов. Для каждой вершины А графа строится ветвящийся процесс, с помощью которого доказывается, что количество вершин в компоненте связности, содержащей А, превосходит PlnN с вероятностью, меньшей чем о(М'1), при достаточно больших N и некотором фиксированном Р = /3(с). Так как вероятность объединения меньше, чем сумма вероятностей, то отсюда непосредственно вытекает утверждение пункта а).

Пункт б) является существенно более сложным. Сначала доказывается, что существует ¡3 = /3(с), такое, что количество вершин, содержащихся в компонентах связности, размер которых не превосходит Р 1п N. равняется МЬС + 0(№'8). Стоит отметить, что большинство из этих компонент являются деревьями, количество вершин, содержащихся в недревесных компонентах связности, равняется о(1п М). Также доказывается, что

зуют связный подграф в случайном графе.

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

Теорема 4. При р > ср, (где с > 2/3, р„ из теоремы 1) случайный граф в пространстве а.п.п. состоит из гигантской компо-

ненты и. возможно, из изолированных вершин.

Иными словами, теорема 4 говорит о том, что переход от связности графа к ее отсутствию совпадает с переходом от связности к наличию изолированных вершин.

Теорема 5. Пусть р = (1п М+с+53(N^/N1 (где сёК, ¿3(ЛГ) = о(1)/ Тогда

Т>кар{С связен) ехр(- ехр(-с)) при N эо.

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

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

Работы автора по теме диссертации

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

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

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

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

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

[6] Ярмухаметов А.Р., Древесные компоненты в случайных дистанционных графах специального вида, Современная математика и ее приложения, 20 (2011), 98 - 110.

Подписано в печать 03.11.2012 Формат 60x88 1/16. Объем 1.0 п.л. Тираж 100 экз. Заказ № 1259 Отпечатано в ООО «Соцветие красок» 119991 г.Москва, Ленинские горы, д.1 Главное здание МГУ, к. А-102

Введение

1 История и формулировки результатов

1.1 Основные определения и история задачи

1.2 Постановка основной задачи

1.3 Формулировки результатов.

2 О связности случайного дистанционного графа

2.1 Доказательство пункта б) теоремы 1.

2.2 Схема доказательства пункта а) теоремы 1.

2.3 Доказательства утверждений 2.2, 2.3, 2.4, 2.5, 2.6.

2.3.1 Доказательство утверждения 2.2.

2.3.2 Доказательство утверждения 2.3.

2.3.3 Доказательство утверждения 2.4.

2.3.4 Доказательство утверждения 2.5.

2.3.5 Доказательство утверждения 2.6.

3 О распределении количества древесных компонент в случайном дистанционном графе

3.1 Вспомогательные утверждения и леммы.

3.1.1 Формулировки вспомогательных утверждений.

3.1.2 Доказательство утверждения 3.1.

3.1.3 Доказательство утверждения 3.2.

3.1.4 Формулировка и доказательство леммы 1.

3.1.5 Формулировка и доказательство леммы 2.

3.1.6 Доказательство утверждения 3.3.

3.1.7 Доказательство утверждения 3.4.

3.1.8 Доказательство утверждения 3.5.

3.2 Доказательство теоремы 2.

3.2.1 Доказательство пункта

3.2.2 Доказательства пунктов 2 и 4.

3.2.3 Доказательство пункта

3.2.4 Доказательство пункта

4 О гигантской компоненте в случайном дистанционном графе

4.1 Вспомогательные утверждения и леммы.

4.1.1 Формулировки вспомогательных утверждений и лемм

4.1.2 Доказательство утверждения 4.1.

4.1.3 Доказательство утверждения 4.2.

4.1.4 Доказательство утверждения 4.3.

4.1.5 Доказательство утверждения 4.4.

4.1.6 Доказательство утверждения 4.5.

4.2 Завершение доказательства пункта б) теоремы 3.

4.3 Доказательство пункта а) теоремы 3.

4.3.1 Ветвящиеся процессы.

4.3.2 Завершение доказательства пункта а) теоремы 3.

4.4 О предельной вероятности связности внутри фазового перехода 56 4.4.1 Доказательство теоремы 4.

Открытие того, что детерминированные утверждения могут быть доказаны с помощью вероятностных соображений, позволило уже в первой половине 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. Ярмухаметов А.Р., Древесные компоненты в случайных дистанционных графах спецаильного вида, Современная математика и ее приложения, 202011), 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.