Законы нуля или единицы и закон больших чисел для случайных графов тема автореферата и диссертации по математике, 01.01.05 ВАК РФ
|
Жуковский, Максим Евгеньевич
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Москва
МЕСТО ЗАЩИТЫ
|
||||
|
2012
ГОД ЗАЩИТЫ
|
|
01.01.05
КОД ВАК РФ
|
||
|
|
||||
Московский государственный университет имени М.В.Ломоносова механико-математический факультет
На правах рукописи УДК 519.21
005018661
Жуковский Максим Евгеньевич
Законы нуля или единицы и закон больших чисел для случайных графов
01.01.05 —теория вероятностей и математическая статистика
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата физико-математических наук
1 2 ДПР 2т1
Москва - 2012
005018661
Работа выполнена на кафедре теории вероятностей механико-математического факультета МГУ имени М.В.Ломоносова.
Научные руководители: доктор физико-математических наук,
профессор
Булинский Александр Вадимович, доктор физико-математических наук, профессор
Райгородский Андрей Михайлович Официальные оппоненты: доктор физико-математических наук,
профессор Кузгорин Николай Николаевич Институт системного программирования РАН, заведующий отделом кандидат физико-математических наук Куликов Александр Владимирович кафедра высшей математики МФТИ, ассистент
Ведущая организация: Хабаровское отделение
Института прикладной математики Дальневосточного отделения РАН
Защита диссертации состоится 27 апреля 2012 года в 16 часов 45 минут на заседании диссертационного совета Д 501.001.85 при МГУ имени М.В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, механико-математического факультет, аудитория 16-24.
С диссертацией можно ознакомиться в библиотеке механико-математического факультета (Главное здание, 14 этаж). Автореферат разослан 27 марта 2012 г.
Ученый секретарь диссертационного совета Д 501.001.85 при МГУ, доктор физико-математических наук, профессор
В.Н. Сорокин
Актуальность
Активное изучение случайных графов началось после того, как П. Эр-деш установил, что вероятностный метод помогает решать многие задачи экстремальной теории графов (см., например, работы 1, 2, 3). П. Эрдеш и А. Реньи в 1960 году4 рассмотрели модель случайного графа G(N,p), в которой ребра в полном графе на N вершинах проводятся независимо друг от друга с вероятностью р = p(N). Огромное количество работ посвящено интересным задачам, связанным с исследованиями случайного графа G(N,p). Среди них отметим работы Б. Боллобаша, 3. Палка, А.Д. Барбура, E.H. Гильберта, И.Н. Коваленко, Г.И. Ивченко, И.В. Медведева, Дж. Спенсера, С. Шелла, Е. Семереди и др.
В диссертации основное внимание уделяется предельным вероятностям выполнения свойств первого порядка случайных графов. Эти свойства задаются формулами первого порядка. Они строятся с помощью символов отношения <~, =, логических связок, переменных (в качестве которых выступают вершины графа) и кванторов. Символ отношения ~ выражает свойство двух вершин быть смежными. Говорят, что случайный граф G(N,p), где р = p(N), подчиняется (асимптотическому) закону нуля или единицы, если вероятность любого свойства первого порядка стремится либо к 0, либо к 1 при N —> оо.
Первый результат в этой области был получен в 1969 году Ю.В. Глеб-ским, Д.И. Коганом, М.И. Лиогоньким и В.А. Талановым5 (независимо в 1976 году Р. Фагиным6). Они установили, что закон нуля или единицы верен, если min{p, 1 - р}№ оо при N оо для всех а > 0. В 1988 году Дж. Спенсеру и С. Шелла удалой, распространить этот закон7 на функции р — N~a,a 6 (R \ Q) П (0,1). Нами получено существенное уточнение результата Дж..Спенсера и С. Шелла для свойств первого по-
'Алон Н., Спенсер Дж., Вероятностный метод, Моокиа, БИНОМ. Лаборатория знаний, 2007.
2Кузюрин H.H., Вероятностные приближенные алгоритмы в декретной ппгпшпиации. Дискрет«. анализ и исслед. опер., сер. 2, 2002, 9(2): 97—114.
3Bollobâs В., Random Graphs, 2nd Edition, Cambridge University Press, 2001.
4Erdfls P., Rényi A., On the evolution of random graphs, Magyar Tiid. Akad. Mat,. Kutatô Int. Käzl.,
1960, 5: 17-61.
6Глебский Ю.В., Коган Д.И., Лиогонький М.И., Таланов В.А., Объем и доля выполнимости формул узкого исчисления предикатов, Кибернетика, 1969, 2: 17-26.
"Fagin R., Probabilities in finite models, J. Symbolic Logic, 1976, 41: 50-58.
7Shelah S., Spencer Л.Н., Zero-one laws for sparse random graphs, J. Amer. Math. Soc.., 1988, 1: 97-115.
рядка, заданных формулами, кванторная глубина которых ограничена числом j (определение кванторной глубины приведено далее). Техника, которую использовали упомянутые авторы, не работает в рассмотренном нами случае. Чтобы преодолеть эту трудность, мы доказали теорему о количестве подграфов в случайном графе, обладающих определенными свойствами. Этот результат представляет самостоятельный интерес.
Кроме того, в работе изучены законы нуля или единицы для случайных дистанционных графов G(Gfjst,p(N)) (строгое определение мы приводим в разделе «Краткое содержание диссертации»). Вершинами дистанционного графа являются точки в а ребра отвечают тем парам вершин, которые отстоят друг от друга на некоторое наперед заданное расстояние. Нами получено множество результатов, охватывающих значительный класс последовательностей случайных дистанционных графов. Эти результаты имеют важное значение для задач комбинаторной геометрии. Так, рассмотрение дистанционных графов мотивировано классической задачей комбинаторной геометрии о хроматическом числе пространства8. Впервые полный дистанционный граф, определение которого напоминается ниже и свойства которого изучаются в диссертационной работе, в геометрическом контексте рассмотрели в 1981 году П. Франкл и Р.М. Уилсон9. С помощью этого графа они показали, что хроматическое число пространствам" растет экспоненциально с ростом п. В 1991 году Дж. Кан и Г. Калаи10 применили результаты Франкла и Уилсона для опровержения классической гипотезы Борсука о том, что всякое ограниченное неодноточечное множество в R" может быть разбито нап + 1 часть меньшего диаметра. Таким образом, изучение внутренней структуры дистанционного графа и его подграфов играет исключительно важную роль. Наши результаты показывают, в частности, что для любого графа G выполнено одно из следующих свойств: либо с вероятностью, стремящейся к 1 при N -» оо,
8Райгородский А.М., Проблема Борсука и хроматические числа метрических пространств, Успехи Матам. Наук, 2001, 56(1): 107-146.
"Frankl P., Wilson R., Intersection theoreins with géométrie conséquences, Combinalarica, 1981, 1357-368.
,0Kahn J., Kalai G., A count.erexample to Borsuk's conjecture, Bulletin (new sériés) of the AMS, 1993, 29(1): 60-62.
п случайном дистанционном графе (^(С'у5', £>(//)) содержится подграф, изоморфный б, либо с вероятностью, стремящейся к 1 при N оо, в случайном дистанционном графе не найдется такого
подграфа.
Помимо законов нуля или единицы в диссертационной работе получен закон больших чисел (ЗБЧ) для модели эпидемии на полном графе. В последнее десятилетие целый ряд работ был посвящен построению моделей эпидемии на графах и изучению вероятностных свойств этих моделей. Моделями эпидемии занимались Р. Дюррет, С. Попов, А. Телке, Н. Вормалд, Е. Либенстэин, О. Алвеш, Ф. Машадо, И. Куркова и другие. Активность в этой области связана с тем, что модели эпидемии играют важную роль в изучении эволюции веб-графа. Исследование моделей эпидемии началось с рассмотрения графа, вершины которого являются точками в Такая модель являлась модификацией модели, предложенной К. Равишанкаром. Идея состояла в том, что каждая активная частица обладает некоторой информацией. Она обменивается этой информацией с неактивной частицей, если оказывается с ней в одной точке. Все частицы, обладающие информацией, участвуют в процессе распространения этой информации. Некоторые результаты для этой модели полезны для исследований химических реакций горения11. Модель эпидемии на полном графе была рассмотрена в 2010 году Ф. Машадо, X. Машурианом и X. Матзингером12. Для количества активированных частиц в этой работе доказана центральная предельная теорема. Мы построили более сложную модель, предположив, что каждый раз обмен информацией совершают несколько частиц, причем количество таких частиц случайно, и установили для количества активированных частиц ЗБЧ.
"Ramirez A.F., Sidoraviritis V., Asymptotic behavior of a growth process of boundary branching random walks, C. R. Math. Acad. Sc.i. Paris, 2002, 335(10): 821-826.
12Machado F., Maslmrian H., Matzinger H., CLT for the proportion of infected individuals for an epidemic model on a complete graph, 2010, arXiV:1011.3601vl.
Цель работы
Цель данной диссертации состоит в решении следующих задач: доказать или опровергнуть закон нуля или единицы для свойств первого порядка с ограниченной кванторной глубиной случайного графа (7(./У, Л^0), где а — рациональное число из интервала (0,1]; исследовать предельные вероятности свойств первого порядка для случайных дистанционных графов, если шт{р, 1 — р}Ыа оо при N оо для всех а > 0; установить оптимальный вариант ЗБЧ для модели эпидемии, обобщающей модель Машадо, Машуриана и Матзингера.
Научная новизна
Все результаты диссертации являются новыми. Перечислим основные из них:
1. Доказан закон нуля или единицы для свойств первого порядка с ограниченной числом у кванторной глубиной для случайного графа Эрдеша и Реньи при а € (0,1/0' - 2)).
2. Опровергнут закон нуля или единицы для свойств первого порядка с ограниченной числом ] кванторной глубиной для случайного графа Эрдеша и Реньи
3. Опровергнут закон нуля или единицы для случайного дистанционного графа, если тщ{р, 1 -р}Ма -> оо при N ->■ оо для всех а > 0.
4. Найдена последовательность случайных дистанционных графов, подчиняющаяся закону нуля или единицы.
5. Установлен ЗБЧ для количества активированных частиц в модели эпидемии на полном графе.
Результаты диссертации обоснованы в виде строгих математических доказательств и получены автором самостоятельно. Точные формулировки установленных автором утверждений приведены ниже.
Методы исследования
При доказательстве результатов нами использовалась разнообразная техника. Так, установление законов нуля или единицы потребовало не
только применения теоремы Эренфойхта13, использования свойства полного расширения, метода моментов, но и разработки нового метода подсчета малых подграфов определенного вида в некотором графе при заданном количестве вхождений других подграфов. В диссертационной работе введено понятие нейтральной пары графов, позволившее представить любую пару вложенных друг в друга графов в виде «композиции» нейтральных пар, а также «надежных» и «жестких» пар, предложенных Дж. Спенсером и С. Шелла14. Данное понятие сыграло принципиальную роль в обобщении известных теорем о количестве малых подграфов в случайном графе. При доказательстве законов нуля или единицы для случайных дистанционных графов мы решили задачу о сопоставлении неотрицательных целочисленных решений двух систем линейных уравнений с коэффициентами из {0,1}. Получение предельных теорем в третьей главе данной работы потребовало привлечение различных вероятностных методов и результатов: мы использовали центральную предельную теорему, некоторые неравенства, касающиеся отклонений сумм независимых случайных величин от их математических ожиданий, теорию ветвящихся процессов.
Теоретическая и практическая ценность
Диссертация носит теоретический характер. Полученные результаты дают возможность рассчитывать и оценивать предельные вероятности существования в графе определенных структур. Кроме того, изучение моделей эпидемии, которым посвящена третья глава диссертации, играет ключевую роль в исследовании свойств Интернета.
Апробация работы
По теме диссертации были сделаны доклады на следующих семинарах механико-математического факультета МГУ имени М.В. Ломоносова:
— Большом кафедральном семинаре кафедры теории вероятностей под рук. академика РАН А.Н. Ширяева (2011г.),
— Колмогоровском семинаре кафедры математической логики и тео-
"Ehrenfeucht, A., An application of games to the completnp,ss problem for formalized theories, Warszawa, Pimd. Math, 1960, 49:121-149.
14Shelah S., Spencer J.H., Zero-one laws for sparse random graphs, J. Amer. Math. Soc., 1988, 1: 97-115.
рии алгоритмов (2010г.),
— семинаре «Асимптотический анализ случайных процессов и полей» под рук. профессора A.B. Булинского и доцента А.П. Шашкина (2011г.),
— семинаре под рук. профессора Н.Г. Мощевитина (2011г.),
— семинарах под рук. профессора A.M. Райгородского (2009-2011 гг.), а также
— Петербургском семинаре по теории представлений и динамическим системам (2010г.),
— семинаре д.ф.-м.н. JI.A. Бассалыго в ИППИ им. Харкевича РАН (2011г.),
— семинарах под рук. профессора A.M. Райгородского в МФТИ (2010— 2011 гг.).
Результаты диссертации докладывались на следующих международных конференциях: «Еврокомб 2009» (Бордо, Франция, 2009), «8th French Combinatorial Conference» (Париж, Франция, 2010), «Ломоносов-2010» (Москва, 2010), «X международном семинаре по дискретной математике» (Москва, 2010), международном симпозиуме «Стохастика и ее видение» (Москва, 2010), «Ломоносов-2011» (Москва, 2011), «RSA'15» (Атланта, США, 2011), «IFS Conference» (Будапешт, Венгрия, 2011).
Работа автора поддержана грантом РФФИ 09-01-00294 и грантом Президента МД-8390.2010.1.
Публикации
Результаты диссертации опубликованы в 12 работах автора (8 из них входят в перечень ВАК), список которых приведен в конце автореферата. Все работы написаны без соавторов.
Структура диссертации
Диссертация состоит из введения, трех глав и списка литературы, насчитывающего 56 наименований. Общий объем диссертации составляет 98 страниц.
КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ
Во введении излагается история исследований, относящихся к случайным графам Эрдеша и Реньи, случайным дистанционным графам и моделям эпидемий на графах, а также описывается структура диссертации.
Для точных формулировок результатов главы 1 введем ряд обозначений. Пусть N € N. Рассмотрим множество Djv всех неориентированных графов G = (Vn,E) без петель и кратных ребер с множеством нершин Vat = {1,...,JV}. Назовем случайным графом а модели Эрдеша-Рены№ случайный элемент G(N,p) со значениями во множестве О.^ и распределением Pjvj, на Тн — 2Пл', определенным формулой •
где \Е\ — мощность множества Е, р 6 [0,1].
Свойства первого порядка задаются формулами первого порядка, которые строятся с помощью символов отношения ~,=, логических связок -I, V,Л, переменных х,у,хi,..., кванторов V,3. В качестве переменных выступают вершины графа. Символ отношения ~ выражает свойство двух вершин быть смежными. Пусть ф — формула первого порядка, определяющая свойство Ьф. Множество графов из обладающих свойством Ьф, мы будем обозначать {G N {)}jv или {G t= Ьф}х. Обозначим С класс свойств первого порядка. В дальнейшем, если выполнено равенство lim Рлг,р({<7 1= b}N) = 1, то будем говорить.
JV—>оо
что случайный граф с асимптотической вероятностью 1 обладает свойством L. Кроме того, так как у вероятности уже стоит индекс N, мы будем опускать этот индексу множества{G t= L}n и писать РNiP(G L).
Рассмотрим некоторую функцию р : N [0,1]. Мы говорим, что случайный граф
подчиняется (асимптотическом,у) закону нуля или единицы, если для любого свойства Ь е С выполняется одно из двух соотношений
fon PW)(G 1= L) = 0, jim Рвд)(£? t= L) = 1. (1)
,5Erd6s P., BÄiyi A., On the evolution of random graphs, Magyar Ttid. Akad. Mat. КпШб Int. Käzl., I960, 5: 17-61.
Будем обозначать V класс функций р, для которых случайный граф С(Лг,р) подчиняется закону нуля или единицы.
Обратимся к ослабленным законам. Зафиксируем натуральное число 3- Обозначим £_,■ класс свойств графов, определенных формулами первого порядка, кванторная глубина которых ограничена числом 3 (см. определение кванторной глубины, например, в работе 16). Случайный граф подчиняется закону нуля или единицы, если для любого свойства Ь 6 С] первого порядка выполняется одно из двух равенств в (1). Будем обозначать V) класс функций р = р{М), для которых случайный граф С?(Аг,р) подчиняется ^'-закону нуля или единицы.
Если при определении случайного графа считать, что ребро{¡г,-,,:^}, 1 < 4,4 < М, проведено с вероятностью б [0,1], то будем обозначать такой случайный элемент .....Одним из важнейших примеров этого случайного графа является случайный граф р), где Ям = — неориентированный граф на N вершинах без петель и кратных ребер. А именно, = .....¿V}), если
Итак, G{Qu,p) — это случайный элемент со значениями во множестве
«С* - {6°N = (V° ,£°n) ■ К = Vjv, £°n Ç Sn} и распределением PçNiP на TgN = 2"«*, заданным равенством
Пусть k g N, п = 4fc, N = С"/2. Рассмотрим граф Gfst = (V$st, Efl)\ V$ist = {x = {xu ...,xn) : xi 6 {0,1}, X! + ... + xn = n/2},
Efb = {{x,y} 6 x УГ : xm + ...+ХпУп = к} .
Изучение такого рода графов мотивировано не только задачей о хроматическом числе пространства, но и исследованиями равновесных
Р, k^ijefjv; 0, {xh,xi2} <£ £N-
"Верещагин Н.К., Шень А., Языки и исчисления, Москва, МЦНМО, 2000.
кодов с запрещенным расстоянием (см. работы 17, 18).
Известно, что любую формулу первого порядка, можно привести к предваренной нормальной форме19. Нас интересуют те формулы, н записи которых в этой форме присутствуют только одинаковые кванторы. Обозначим класс рассмотренных формул С1. Пусть {CwJieN — последовательность неориентированных графов без петель и кратных ребер, \V{gNi)\ ~ Ni. Будем говорить, что последовательность случайных графов {С?(^лГ(,Р)}гем подчиняется закону нуля или единицы, j-закону нуля или единицы, закону нуля или единицы с одним квантором, если для любого свойства L € С, свойства L € £j, свойства L € С1 соответственно выполняется одно из двух соотношений
Ит РgNiiP(Nl)(g t= L) = 0, Шп РgNi,m)(G t= L) = 1.
Класс функций р, для которого последовательность {С(^>р)}ге1ч подчиняется закону нуля или- единицы мы будем обозначать ^ ({£лгЛ;6м)' J-закону нуля или единицы - V} ({£/Л',},еН) и, наконец, закону нуля или единицы с одним квантором — Vх ({£jv,}.;eN). Положим
V) = V1 ({^ы n Vj ({^ы.
Вернемся, наконец, к случайным дистанционным графам. Пусть Ni — Естественно определить класс функций Vdist равенством
-past = v ^Gdht} J . Если р е -pdist^ то будем roBopiITbi чт0
чайный дистанционный граф G{G%st,p) подчиняется закону нуля или единицы. Классы функций VfBt, -pUis\ Pj'dist и соответствующие законы определяются аналогичным образом. Основной результат главы 1 содержит
ТЕОРЕМА 1.3.1. Существует последовательность {Щ^, обладающая следующим свойством: если min{p, 1 - p}Na ->• оо при N -> оо для любого а > 0, то р е V .
1'Мак-Вильямс Ф.Дж., Слгон Н.Дж.А., Теория кодов, исправляющих ошибки, Москва, «Связь», 1979.
lsKabat,iansky G., Krouk Е., Semenov S., Error Correcting Codex and Security for Data Networks, Wiley and Sons, 2005. "Верещагин H.K., Шепь А., Языки и исчисления, Москва, МЦНМО, 2000.
Теорема 1.3.1 играет роль не только в изучении структуры дистанционных графов, но и отвечает на естественный вопрос, существует ли последовательность случайных дистанционных графов, подчиняющихся закону нуля или единицы хотя бы в случае р = const (ведь последовательность всех случайных дистанционных графов такому закону не подчиняется). Для доказательства этой теоремы нам потребовалось исследовать одну задачу существования неотрицательных целочисленных решений систем линейных уравнений, коэффициенты которых принадлежат множеству {0,1}. Оказалось, что поставленная задача напрямую связана с проблемой нахождения максимально возможного определителя у матрицы, элементы которой принадлежат множеству {0,1}. Множество всех таких матриц размера к х т ранга к будем обозначать Мкхт■ Зафиксируем произвольное натуральное четное число п. Рассмотрим векторы-столбцы f = (n,n, ...,п)Т £ g = (n/2,n/2, ...,n/2)r € N*. Обозначим М%хт подмножество в Mkxm, состоящее из матриц, удовлетворяющих следующему условию. Матрица А принадлежит множеству тогда и только тогда, когда либо
система Ах = f не имеет решений из множества Z'" (Z™ — множество m-мерных векторов с целочисленными неотрицательными координатами), либо для любого решения х € Z'4n системы Ах = f существует решение у е Щ системы Ay ~ g, удовлетворяющее неравенствам Ui <xui<E {1,2, ...,m}. Несложно показать, что такое решение второй системы найдется далеко не при всех даже сколь угодно больших п. При доказательстве теоремы 1.3.1 перед нами встала задача отыскать такие п, при которых для каждого натурального т множества М%хт и Мкхт совпадают.
Пусть Ак — максимальный среди определителей всех матриц из Мкхк■ Этот максимальный определитель, очевидно, не превосходит числа к\. Известны более точные оценки. Так, Дж. Бреннер и Л. Каммингс?0 в 1972 г. доказали неравенство Ак < Кроме того, при к,
принимающих значения 1,2,3,4,5, определитель Ак в точности равен
20Вгеппег Л., Cummings L., The fiadamard Maximum Determinant, Problem, The. American Mathematical Monthly, 1972, 79(6): 626-630.
1,1,2,3,5 соответственно. Положим 23* = НОК(Д;., Д* — 1,..., 1).
Сформулируем достаточное условие существования «меньшего» решения у системы Ау — g.
Лемма 1.3.1 Для любого к е N существует такое щ, что при любых п > щ, удовлетворяющих условию 2Дь|п, и при всех т £ N справедливо равенство Мкхт — |Х)П.
Мы показали также, что при некоторых к условие 2Д,|п является необходимым, а именно имеет место
Лемма 1.3.2 При к 6 {1,2,3,4,5} существует такое щ, что если п > щ, то равенство Мк*т — ^кхт оыполнемо для любого натурального т тогда и только тогда, когда справедливо соотношение 2Ви|п.
Сформулируем еще один важный результат главы 1. Для этого положим щ{з) = 4где ^ 6 ИП[4,оо) и г 6 N. Возьмем, кроме того, при каждом з 6 {4,5,6} последовательность {т^)}^, обладающую следующим свойством. Существуют сколь угодно большие номера к{з),гг{з), при которых кратно Щ-г, пц2(^(з) не кратно
Щ-!. Пусть ВД = при з е N П [4,оо), М^з) = СиГ ПРИ
7 е {4,5,6}.
ТЕОРЕМА 1.4.1. Пусть тт{р, 1 - р}№ -»■ оо при N оо для любого а > 0. Тогда р е V) ) для ¿в N П [4,оо) и
р V) ) для з е {4,5,6}. Кроме того, р 6
Заметим, что теорема 1.3.1 не позволяет выделить такой класс свойств первого порядка и последовательностей случайных дистанционных графов, что вероятности этих свойств стремятся к 0 или 1 с ростом N. Она также не позволяет ответить на вопрос, для каких свойств и для каких последовательностей упомянутые вероятности не стремятся ни к 0, ни к 1. Доказав теорему 1.4.1, мы решили эти две задачи для случая з е {4,5,6}.
В главе 2 изучаются законы нуля или единицы для свойств первого порядка случайных графов Эрдеша и Реньи. Мы рассматриваем класс функций р(Лг) = Ы~а, а £ (0,1], который изучали Дж. Спенсер и С. Шелла. Они доказали, что для а £ (К\0>) П (0,1] (асимптотический) закон нуля или единицы справедлив. Если же а 6 фп(0,1]. то случайный граф не подчиняются закону нуля или единицы. Нам удалось получить уточнение этого результата и расширить класс функций р(Л^) для достаточно большого класса свойств первого порядка. Основной результат главы 2 содержит
ТЕОРЕМА 2.3.1. Пусть р = 0 < а < у^, з £ К, > 3. Тогда случайный граф С(Ы,р) подчиняет,ся з -закону нуля или единицы. Если а = -р^, то случайный граф С{Ы,р) не подчиняется ¡-закону нуля или единицы.
Кроме того, мы показали, что при з — 2 для всех а £ (0,1] функция р = принадлежит множеству Ту
Для доказательства теоремы 2.3.1 нам потребовалось получить результат о распределении малых подграфов в случайном графе. Прежде чем перейти к ее формулировке, приведем еще ряд необходимых определений.
Рассмотрим графы Я с О, Н с б. Пусть У(Я) = {хи У{С) = {хъ...:х,}., У(д) = {г1,..,г;}, у(н) = ф,гРаф в называется (С, Н)-расширением графа Я, когда
К,**,} £ Е(С) \ Е(Н) {хкл2} е Е(С) \ Е(Н).
Если выполняется соотношение
£ Е(С) \ Е(Н) & {хк,х{2} £ Е(б) \ Е(Н),
то С назовем точным расширением. Положим 1)(Сг, Я) = \ У(Н)|, е(С?,Я) = \ Е(Н)\. Пусть фиксировано число а > 0. Если для
любого такого графа 5, что Я С 5 С С, выполнено неравенство и(5, Я) - а ■ е(3, Я) > 0, то пара (С, Я) называется а-надежной. Если
же для любого такого графа й, что Я С й С С, выполнено неравенство V(С?, 5) — а ■ е((3,5) < 0, то пара (б, Я) называется а-жесткогР1.
Пусть теперь € Кдг и случайная величина А^я^Жь..., 5*)
каждому графу Я из ставит в соответствие количество (<7, Я)-расширений подграфа в 0, индуцированного на {х1,...,хд.} (граф X является подграфом графа У, индуцированным па множество У(Х), если для любых ж, у € У(Х) имеем {т, у} Е Е(Х) {х, у} е Е(У) и У{Х) с У(У)). Дж. Спенсер и С. Шелла для исследования законов нуля или единицы доказали теорему о количестве максимальных расширений подграфов в случайном графе, т.е. таких надежных расширений, для которых в случайном графе не существует «новых» заранее зафиксированных расширений. Ими были рассмотрены максимальные расширен ия, для которых не существует жестких расширений, и максимальные расширения, для которых не существует надежных расширений. Мы расширили их результат, рассмотрев нейтральные пары, возникающие в случае рациональных а.
Более формально, пусть Я С <5 С Г и Т С К, причем |У(Г)| < |У(0)|. Пара (С,Я) называется (К,Т)-максимальной в Г, если у любого такого подграфа Т графа <5, что |У(Т)| = |У(Т)| и Т П Я ф Т, не существует такого точного (К, Г)-расширения К в Г \ (б \ Т), что каждая вершина из У(К) \ У(Т) не соединена ребром ни с одной вершиной из У(С) \ У(Т). Пусть 0 < а < 1 — рациональное число. Рассмотрим графы Я, (7. Пусть Я С б, любая вершина графа Я соединена с некоторой вершиной из У((?) \ У(Н), и для любого такого графа 5, что Я С й С б, справедливо неравенство Я) - а • е(5, Я) > 0, но Я) - а • е((?, Я) = 0. В этом случае пару ((?, Я) будем называть а-нейтпральной.
Обратимся, наконец, к формулировке нашей теоремы 2.2.4 о распределении малых подграфов в случайном графе. Пусть а € (0,1], пара (С, Я) является а-надежной и У(Н) = ...,Хк}, У {О) = {хг, Пусть, кроме того, 2пе,1кга1(г) — множество всех а-нейтральных пар вида (¿.Т,), где |У(Т;)| < \У{в)\, \У(Кг)\У(Тг)\ < г. Рассмотрим случай-
21 Алон Н., Спенсер Дж., Вероятностный, метод, Москва, БИНОМ. Лаборатория знаний, 2007.
ный граф G(N,p(N)) и вершины х\,...,хк £ V. Пусть случайная величина ..., Хк) ставит в соответствие каждому графу Q € Пдг количество таких точных (£?, #)-расширений G графа Н — что пара (G, Я) является (/С,,Т{)-максимальной в Q для каждой нары (Kí,Tí) е Eneutra,(r). Ясно, что Ñ?Sn£jf.{xu -Л) зависит и от N.
ТЕОРЕМА 2.2.4. С асимптотической вероятностью единица для любых вершин Xi,...,Xk выполнено
Как обычно, gi(N) х 9í{N), если найдутся такие числа с, С > 0, что для всех достаточно больших N б N справедливо двойное неравенство egг(Л0 < < Cg2{N). Теорема 2.2.4 обобщает результаты П. Эрде-ша, А. Реньи22, Дж. Спенсера23, Б. Боллобаша (см., например, работу 24) и др. о распределении малых подграфов в случайном графе G(iV,;p). Нам удалось решить неисследованную упомянутыми авторами задачу благодаря введению нового понятия нейтральной пары. Результаты для других видов пар получены в работе Дж. Спенсера.
Прежде чем описать модель эпидемии на полном графе, рассмотренную в главе 3, обратимся к модели, изученной в 25. Пусть {xi,...,xn} — некоторое множество точек. В момент времени t = 1 в точке х\ располагается активная частица, а во всех остальных — неактивные (по одной частице в каждой точке). В точке а;,; находится частица г. В любой момент времени t £ N ровно одна активная частица, номер которой имеет равномерное распределение на множестве номеров активных частиц, имеющихся в момент í, совершает скачок в некоторую точку Xtft) (иными словами, она обменивается информацией с неактивной частицей, находящейся в точке год). При этом случайная величина £(í) также равномерно распределена на {1,.,.,п}. Если частица совершает скачок в точку с неактивной частицой, то эта частица активируется,
"Erdcto Р., Rényi A., On the evolution of random graphs, Magyar Tad. Akad. Mat. Kutatá Int. 1Ш., 1960, 5: 17-il,
23Spencer J.H., Counting extensions, J. Combinatorial Theory, Ser. A, 1990, 55: 247-255.
MBoIIobás В., Random Graphs, 2nd Edition, Cambridge University Press, 2001, 78-91.
25Machado F., Mashurian H., Matzinger H., CLT for the proportion of infected individuals for an epidemic model on a complete graph, 2010, arXiV:1011.3601vl.
а частица, совершившая скачок, остается активной. Активная частица умирает в том и только том случае, когда совершает скачок в точку, в которой находится или побывала ранее активная частица. В частности, если она совершает скачок в точку, где сама находится, то тоже погибает. Мы построили более сложную модель, предположив, что каждый раз скачки совершают несколько частиц, причем количество таких частиц случайно, и получили для нее некоторые предельные законы.
Рассмотрим множества {2:1 (п), ...,а;п(п)}, п в N. Пусть, как и в модели 26, время £ дискретно. Будем считать, что в момент £ = 1 в каждой точке находится одна частица с номером г. В точке Х\ — ЯГ1 (та) располагается активная частица, а во всех остальных — неактивные. В каждый момент времени активная частица совершает скачок с вероятностью р независимо от всех остальных активных частиц, при этом, если частица совершила скачок, то вероятность попадания в каждую точку равна 1 /п. Схема взаимодействия активных и неактивных частиц та же, что и в модели Машадо, Машуриана и Матзингера. Однако если несколько частиц в один момент времени совершают скачки в одну и ту же точку с неактивной частицой, то все они остаются живы, а неактивная частица становится активной. Таким образом, с ненулевой вероятностью найдутся моменты времени, в которые в некоторых точках будет находиться по две и более активных частиц.
Пусть величина Ап(Ь) равна количеству активных частиц в момент времени Ь, величина Ц,(£) равна количеству неактивных частиц в этот момент. Пусть, кроме того, стп — момент, в который процесс Дг(£) останавливается, т.е. <т„ = гшп{£ е N : Ап(Ь) = 0}. Если Ап(Ь) > 0 для всех Ь 6 М, то положим ап = 0. В главе 3 мы изучили предельное распределение количества частиц, которые были активированы в ходе процесса, т.е. случайной величины Хп = п — Оп(ап) при п —¥ оо. Сформулируем основной результат главы.
2"Machado F., Masliurian H., Matzinger H., CLT for the proportion of infected individuals for an epidcmic model on a complete graph, 2010, arXiV:10U.3601vl.
ТЕОРЕМА 3.2.1. Для любого 7 > 3/4 справедливо соотношение
Хп — ЕХп р . .
--► 0, п ->■ оо. (2)
пт
Кроме того, НпнпГ Р (|Х„ — ЕХ,,| > п7) > 0 <?ля любого 7 < 3/4.
П-400
Данный результат оптимален в том смысле, что (2) не выполнено при 7 < 3/4. Отметим также, что сходимость по вероятности в (2) нельзя заменить на сходимость почти наверное ни при каком 7 < 1.
В модели «с одним скачком» можно разбить отрезок времени [1,а„] на достаточно большие части так, что зависимость между количествами живых частиц для моментов из одной части, слабая. Это позволяет доказать центральную предельную теорему. В нашей модели эта зависимость в значительной мере усиливается за. счет того, что с некоторого момента с большой вероятностью количество частиц, совершивших скачки, сильно отклоняется от своего математического ожидания. Поэтому перейти к суммам независимых случайных величин не удается. Поясним, как мы преодолели эту трудность и доказали закон больших чисел. Оказывается, что для моментов времени, не превосходящих (1/2 — а) 1о§1+рп, где а > 0, описанная зависимость достаточно слаба. Благодаря этому удается оценить случайные величины в момент времени [(1/2 - а) ^1+рп), где [•] — целая часть числа. При í > (1/2 - а) 1оя1+р тг упомянутая зависимость усиливается. Тем не менее удается построить такие вспомогательные независимые случайные величины, что момент, в который их сумма перестает быть меньше количества частиц, совершивших скачок, совпадает с количеством активированных частиц. Описанные величины играют ключевую роль при двусторонних оценках исследуемых случайных величин. Эти оценки устанавливаются по индукции, при этом используются неравенства на отклонения сумм независимых случайных величин от их математического ожидания, в том числе неравенство Чернова, а также центральная предельная теорема и аппарат производящих функций, широко применяемый в теории ветвящихся процессов.
Благодарности. Автор признателен профессору Александру Вадимовичу Булинскому и профессору Андрею Михайловичу Райгородскому за постановку задач и неоценимую помощь в работе. Автор также благодарен доценту Д.А. Шабанову за полезные замечания.
Работы автора по теме диссертации
[1] М.Е. Жуковский, Закон больших чисел для модели эпидемии, Доклады Академии Наук, 2012, 442(6): 736-739.
[2] М.Е. Жуковский, Ослабленные законы «нуля или единицы» для случайных дистанционнных графов, Доклады Академии Наук] 2010, 430(3): 314-317.
[31 М.Е, Жуковский, Ослабленный закон нуля или единицы для случайных дистанционных графов, Теория вероятностей и ее применения, 2010, 55: 344-350.
[4| М.Е. Жуковский, Законы нуля или единицы для формул первого порядка с ограниченной кванторной глубиной, Доклады Академии Наук, 2010, 436(1): 14-18.
[5] М.Е. Жуковский, О последовательности случайных дистанционных графов, подчиняющейся закону нуля или единицы, Проблемы передачи информации, 2011, 47(3): 39-57.
[6] М.Е. Жуковский, Ослабленный закон «нуля или единицы» для случайных дистанционных графов, Вест,ник РУДН, 2010, 2(1): 11-25.
[7] М.Е. Жуковский, Оценка количества максимальных расширений в случайном графе, Дискретная математика,, 2012, 24(1): 79-107.
[8] М.Е. Zhukovskii, Zero-one k-law, Discrete Mathematics, 2012, 312: 1670-1688.
[9] М.Е. Zhukovskii, On the zero-one laws and the zero-one j-laws for the random graphs, Abstracts of 8fcc, Orsay, Prance, 2010, 47.
[10] M.E. Zhukovskii, On zero-one laws for random graphs. Abstracts of Conference on Infinite and finite sets, Budapest, Hungary, 2011, 29-30.
[11] М.Е. Жуковский, Ослабленные законы нуля или единицы для случайных дистанционных графов, Тезисы докладов конференции Ломоносов 2010, Москва, 2010, 1-2.
[12] М.Е. Жуковский, Закон больших чисел для модели эпидемии, Тезисы, докладов конференции Ломоносов 2011, Москва, 2011, 1-2.
Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж 100 экз. Заказ №
61 12-1/770
Московский государственный университет им. М.В.Ломоносова механико-математический факультет
На правах рукописи
Жуковский Максим Евгеньевич
ЗАКОНЫ НУЛЯ ИЛИ ЕДИНИЦЫ И ЗАКОН БОЛЬШИХ ЧИСЕЛ
ДЛЯ СЛУЧАЙНЫХ ГРАФОВ
01.01.05 — теория вероятностей и математическая статистика
Диссертация на соискание ученой степени кандидата физико-математических наук
Научные руководители — д.ф.-м.н. А.В. Булинский, д.ф.-м.н. А.М. Райгородский
Москва, 2012
Оглавление
Список основных обозначений 3
Введение 5
1 Законы нуля или единицы для случайных дистанционных графов 15
1.1 Законы нуля или единицы......................15
1.2 Случайные дистанционные графы.................18
1.3 Законы нуля или единицы для случайных дистанционных графов 20
1.4 Ослабленные законы нуля или единицы для случайных дистанционных графов ...........................39
2 Законы нуля или единицы для случайных графов Эрдеша и Реньи 41
2.1 Формулы с ограниченной кванторной глубиной..........41
2.2 Распределение малых подграфов..................42
2.3 Ослабленный закон..........................70
3 Закон больших чисел в модели эпидемии на полном графе 74
3.1 Модели эпидемии на полном графе ................74
3.2 Закон больших чисел для количества активированных частиц . 76
Список литературы 95
Список основных обозначений
N — множество натуральных чисел;
Щ — множество натуральных чисел, кратных к;
Z — множество целых чисел;
Z+ — множество целых неотрицательных чисел;
(0) — множество рациональных чисел;
К. — множество действительных чисел;
Б(М) — и-алгебра борелевских подмножеств М;
\А\ (или $А) — мощность конечного множества А\
[а] — целая часть числа а;
НОК — наименьшее общее кратное;
а\Ь — свойство «а делит 6», т.е. число а является делителем числа 6; 1{Е) — индикатор события Е;
ЕХ — математическое ожидание случайной величины X; ОХ — дисперсия случайной величины X;
(т(Х) — сигма-алгебра, порожденная случайной величиной X, т.е. множество {{со : Х(и) ЕВ}: В е Я(М)};
(х, у) — евклидово скалярное произведение векторов х и у;
||х|| — норма вектора х в евклидовом пространстве;
У(С) — множество вершин графа С;
Е(С) — множество ребер графа С;
г>((7) — количество вершин графа (7;
е{0) — количество ребер графа С;
а{С) — количество автоморфизмов графа С;
С\у — подграф графа С, индуцированный на множество V;
С 1= Ь — предикат, истинный тогда и только тогда, когда граф С обладает свойством Ь;
/(А^) = о(^(АГ)) — для любого числа с > 0 существует такое число N0, что для любого N > N0 выполнено неравенство |/(Л/")| < с|д(ЛГ)|;
/(./V) = 0(д(М)) — найдется такое число С > О, что для любого N е N выполнено неравенство |/(Л01 —
/(А'") = ©(д(Л^)) — найдутся такие числа с, С > 0, что для любого Я 6 N выполнены неравенства с\д(М)\ < |/(А^)| < С\д(М)\.
Введение
Данная работа состоит из трех глав. Первые две посвящены законам нуля или единицы (асимптотическим) для свойств первого порядка случайных графов. В третьей главе речь идет о некоторых предельных теоремах для количества зараженных частиц в модели эпидемии на полном графе.
В первой главе изучены законы нуля или единицы для случайных дистанционных графов. Получено множество результатов, охватывающих значительный класс последовательностей случайных дистанционных графов (см. раздел 1.1). Эти результаты имеют важное значение для задач комбинаторной геометрии. Так, рассмотрение дистанционных графов мотивировано классической задачей комбинаторной геометрии о хроматическом числе пространства (см. [9] и [10]). Впервые полный дистанционный граф, определение которого сформулировано ниже и свойства которого изучаются в данной работе, в геометрическом контексте рассмотрели в 1981 году П. Франкл и P.M. Уилсон. С помощью этого графа они показали, что хроматическое число пространствам" растет экспоненциально (см. [26]). В 1991 году Дж. Кан и Г. Калаи применили результаты Франкла и Уилсона для опровержения классической гипотезы Борсука о том, что всякое ограниченное неодноточечное множество в Мп может быть разбито на п + 1 часть меньшего диаметра (см. [9] и [32]). Таким образом, изучение внутренней структуры дистанционного графа и его подграфов играет исключительно важную роль. Наши результаты показывают, в частности, что любой подграф либо содержится в почти всех дистанционных графах, полученных из полного дистанционного графа удалением ребер, либо не содержится в почти всех таких дистанционных графах. Сейчас с исследованием дистанционных графов связаны одни из самых широко изучаемых разделов комбинаторной геометрии (см. [9], [10], [17]).
В данной работе доказано, что случайный дистанционный граф не подчиняется закону нуля или единицы (асимптотическому) для свойств первого порядка (см. раздел 1.1, а также [52], [54]). Мы ослабили закон, введя ограничение на кванторную глубину формул и установили, какие последовательности подчиняются новому ослабленному закону. Было получено большое
количество неожиданных результатов. Законы, которые удалось установить, помогают выявить новые свойства случайного дистанционного графа. Таким образом, ослабленный закон нуля или единицы представляет отдельный интерес. Перед нами встал вопрос, в каких случаях классический случайный граф, т.е. случайный граф в модели Эрдеша-Реньи (см. [1], [5], [16], [24], [30], [36]), удовлетворяет ослабленному закону. На этот вопрос мы отвечаем во второй главе. Вероятность того, что конкретное ребро проведено, р(А^), в рассматриваемой модели Эрдеша-Реньи является функцией от числа вершин
Изучением асимптотики вероятностей свойств первого порядка (строгие определение см. в главе 1) случайного графа занимались П. Эрдеш и А. Ре-ньи в 1960 году (см. [24]), Ю.В. Глебский, Д.И. Коган, М.И. Лиогонький и В.А. Таланов в 1969 году (см. [4]), Р. Фагин в 1976 году (см. [25]), Дж. Спенсер и С. Шела в 1988 году и 2001 году (см. [44], [47]), М. МкАртур в 1997 году (см. [38]), Р.Х. Гильман, Ю. Гуревич и А. Мясников в 2007 году (см. [27]) и
ДР-
Первый закон нуля или единицы для свойств первого порядка случайного графа в модели Эрдеша и Реньи был доказан в 1969 году Ю.В. Глебским, Д.И. Коганом, М.И. Лиогоньким и В.А. Талановым (независимо в 1976 году Р. Фагиным). Ими было установлено, что если Ь — свойство первого порядка, а Р{Ь) — количество графов из обладающих этим свойством, где ~ множество всех графов без петель и кратных ребер на множестве вершин {1,..., А/"}, то либо
Иными словами, если вероятность ребра в модели Эрдеша-Реньи равна 1/2, то для любого свойства первого порядка либо с вероятностью, стремящейся к 1, случайный граф обладает этим свойством, либо с вероятностью, стремящейся к 1, не обладает. Этот результат легко распространяется на класс функций подчиняющийся следующему закону:
В 1988 году Дж. Спенсеру и С. Шела удалось расширить этот класс функций (см. [44]). Они доказали, что для р = где а Е Ж \ О, а б (0,1), закон нуля или единицы также справедлив. Если же а е <0> П (0,1], то случайный граф не подчиняется закону нуля или единицы. Нам удалось получить важное уточнение этого результата Дж. Спенсера и С. Шела и расширить
N.
либо
= 0.
= 1,
\/а > 0 тт{р, 1 - р}Ма оо, N оо.
(1)
класс функций р(п) для достаточно большого класса свойств первого порядка. Техника, которую использовали упомянутые авторы в своих работах, не работает в рассмотренном нами случае. Чтобы преодолеть эту трудность, мы доказали теорему о количестве подграфов в случайном графе, обладающих определенными свойствами (см. [55] и раздел 2.2). С одной стороны, эта теорема сыграла ключевую роль при доказательстве нашего закона нуля или единицы. С другой стороны, подобными задачами занимались П. Эрдеш и А. Реньи в 1960 году (см. [24]), Дж. Спенсер в 1990 году (см. [46]), П.Е. Хак-селл, И. Кохаякава и Т. Лучак в 1995 году (см. [29]) и др. При этом оставалась неразрешенная задача, которую мы и рассмотрели.
Хотелось бы упомянуть о двух других работах, посвященных законам нуля или единицы для случайных графов. Так, в работе [33] получены законы нуля или единицы для графов, свободных от полных подграфов данного размера. В 2007 году Ю. Гуревичем, Р. Гилманом и А. Мясниковым был сформулирован и доказан закон нуля или единицы для графа с бесконечным количеством вершин (см. [27]). Более детальную историю изучения законов нуля или единицы можно найти в [20], [22], [30], [47].
Остановимся подробнее на исследуемых в первых двух главах объектах. Пусть N еП,0<р<1. Рассмотрим снова множество Г2дг = -[С = (V/v, £?)} всех неориентированных графов без петель и кратных ребер с множеством вершин V/v = {1 Случайный граф в модели Эрдеша-Ренъи это слу-
чайный элемент G(N,p) со значениями во множестве f2/v и распределением Рn,v на
Fn = 2ÜN,
определенным формулой
PN,p{G)=pW{l-p)c»~W.
Изучение случайных графов началось после того, как П. Эрдеш установил, что «вероятностный метод» (см. [1], [6], [16]) помогает решать многие задачи экстремальной теории графов. Помимо прочего, Эрдеш доказал с использованием «вероятностного метода», что для любых натуральных чисел g > 3 и к > 3 существует граф с хроматическим числом к и циклом наименьшей длины д. На самом деле, Эрдеш не был первым, кто применил вероятностную технику к задачам, связанным с конечными структурами. Вероятностный метод использовали также Р. Пэли, А. Зигмунд, Дж. Литтлвуд, А. Оффорд и другие. Вероятностные свойства некоторых комбинаторных структур изучали еще в 1940 году М. Кендалл и Б. Бабинтон-Смит. В 1943 году Т. Селе
впервые применил «вероятностный метод» к экстремальным задачам комбинаторики. По случайным графам в конце 50-х годов XX века было написано несколько работ. Все они послужили основой для изучения свойств случайных графов. Наиболее известны среди них статьи Г.В. Форда и Г.Е. Уленбека (1956 год), E.H. Гильберта (1957 год), Т.Л. Остина, P.E. Фэйгина, В.Ф. Пенне и Дж. Риордана (1959 год) и П. Эрдеша и А. Реньи (1959-1960 года, см [24]).
Именно Эрдеш и Реньи установили, что рассматриваемые ими свойства случайного графа «возникают», в каком-то смысле, внезапно. Пусть вероятность появления ребра р является функцией p(N) от количества вершин N. Тогда, например, для каждого из свойств содержать клику фиксированного размера, быть связным, содержать «гигантскую компоненту» (т.е. компоненту связности, количество вершин в которой имеет порядок N) найдется функция po(N), для которой это свойство не выполнено с вероятностью, стремящейся к 1, если р = о(ро), и выполнено с вероятностью, стремящейся к 1, если ро = о(р). Такая функция po(N) называется пороговой для свойства (пороговой функция называется и если свойство выполнено с вероятностью, стремящейся к 1 при р = о(ро), и не выполнено с вероятностью, стремящейся к 1, при ро = °(р))- Например, для свойства содержать «гигантскую компоненту» функция 1/N является пороговой. На самом деле, у всех монотонных свойств существует пороговая функция. Свойство называется монотонным, если из того что граф Н обладает этим свойством и Н С G следует, что граф G также обладает этим свойством. Пусть С — некоторый класс свойств, для которых существуют пороговые функции. Пусть кроме того, V0 — класс всех пороговых функций этих свойств. Тогда если р = p(N) — такая функция, что
Vpo е V0 (р = о{р0)) V (ро = о(р)),
то для функции р справедлив закон нуля или единицы, т.е. для любого свойства из С вероятность того, что случайный граф G(N, р) обладает этим свойством, стремится либо к 0, либо к 1. Этот факт заставил многих авторов заняться поиском для различных классов свойств С множеств функций Vc> для которых выполнен закон нуля или единицы.
Пожалуй, самым изученным в этом направлении является класс свойств, выражаемых формулами первого порядка (см. [3], [12]). Эти формулы строятся с помощью символов отношения =; логических связок -i, V, А; переменных х,у,хкванторов V, 3. Символы переменных в языке первого порядка обозначают вершины графа. Символ отношения ~ выражает свойство двух вершин быть соединенными ребром, символ отношения = выра-
жает свойство двух вершин совпадать. Обозначим V множество функций р = p(N), для которых выполнен закон нуля или единицы для класса свойств первого порядка. Класс свойств первого порядка обозначим С. Как уже было сказано выше, если для р = p(N) справедливо соотношение (1), то р £ V. Кроме того, все функции р = N~a, а Е M\Q, а Е (0,1), также принадлежат V. Разумеется, р = 1 — N~a £ V, если а £ Е \ Q, а £ (0,1). Известны и другие функции из множества V-
Теорема 1 ([36], [44]). Функцияр содержится eV, если она обладает одним из следующих трех свойств:
• для некоторого 1 £ N
п"1"1/'= 0(р), р = о(п-1-1/(/+1)),
• справедливы равенства
p = n-i-o(i)} р =
• выполнены соотношения
p = n-1+°(1))n-1 = о(р) w ^лл любой такой пары натуральных чиселг, s, что s > г — 1 > 0 ли^о гпр — In п — s In In п —>• —сю, п —>■ оо,
rnp — Inn — s In Inn —> оо, n —> оо.
Итак, пусть р убывает и р —>• 0 при N ^ оо. Тогда если р убывает достаточно медленно (piVa —> оо для каждого а > 0), то функция р принадлежит множеству V независимо от того, какой вид имеет эта функция. Если же р = N~a, а 6 q п (0,1], то функция р перестает принадлежать классу V. Возникает вопрос: как выбрать из множества С такое достаточно большое подмножество /2, чтобы функции р = N~a принадлежали классу V£ и при рациональных а из некоторого интервала. Ответ на этот вопрос таков: можно ограничить кванторную глубину формул, т.е. для каждого j G N рассмотреть класс свойств Cj, выражающихся формулами первого порядка, кванторная глубина которых не превосходит числа j. Мы доказали, что если j > 3, р = N~a, а Е (0,1 /(j — 2)), то р £ Vcj (в главах 1 и 2 мы будем для краткости обозначать это множество Vj). При а = l/(j — 2) существуют свойства из jCj, вероятность которых сходится к константе, отличной от 0 и 1. Если же j = 2, то для всех а £ (0,1] функция р = N~a принадлежит
множеству Vcj (см. раздел 2.1, а также [50], [56]).
На самом деле, как уже было отмечено выше, существует и другая причина рассматривать класс Cj. В данной работе мы доказали, что случайный дистанционный граф не подчиняется закону нуля или единицы, если соотношение (1) выполнено для функции р (см. раздел 1.2, а также [52], [54]). Сформулируем определение случайного дистанционного графа. Рассмотрим граф G%st = (V$st, Ef}st), в котором
V$ist = {х = {хъ ..., хп) : х{е {0,1}, хг + ... + хп = п/2},
Efl = {{Х,у} ev$* х V$ist : (х,у) = п/4} ,
где п Е 4N. В случайном дистанционном графе G(Gf{St,p) ребро {х, у} проведено с вероятностью р тогда и только тогда, когда {х, у} € EffiK Если {х, у} ^ Efjst, то и в случайном графе G{G%st,p) ребро {х, у} не проведено. Нам пришлось уменьшить множество свойств так, чтобы для функций р, удовлетворяющих соотношению (1), был справедлив закон нуля или единицы. Мы доказали (см. раздел 1.2, а также [52]), что для случайных дистанционных графов множество Vcz содержит в себе все функции, удовлетворяющие соотношению (1). Кроме того, для каждого j G N удалось описать последовательности случайных дистанционных графов, подчиняющихся закону нуля или единицы для свойств из класса Cj, при р, удовлетворяющих соотношению (1) (см. раздел 1.2, а также [51]). Тем самым, рассмотрение классов оправдано тем фактом, что случайный дистанционный граф закону нуля или единицы для свойств первого порядка не подчиняется. Именно по этой причине в данной работе мы сначала излагаем законы, полученные для случайных дистанционных графов, после чего переходим к классическим случайным графам.
Формулы второго порядка отличаются от формул первого порядка возможностью квантификации общности и существования не только над атомами, но и над предикатами. Примером свойства второго порядка служит связность графа. Можно показать, что даже в случае р = const закон нуля или единицы для свойств второго порядка случайного графа Эрдеша-Реньи не выполнен. С другой стороны, если функция р удовлетворяет соотношению (1), то случайный граф связен с вероятностью, стремящейся к1. Имеется несколько работ, в которых авторы ищут как можно более широкий подкласс свойств второго порядка, для которого закон нуля или единицы будет выполнен в случае р = const или р, удовлетворяющего соотношению (1).
Огромное количество работ посвящено и другим интересным задачам, связанным с исследованиями случайного графа G(N,p). П. Эрдеш, А. Реньи, К. Шургер, Б. Боллобаш, 3. Палка, А.Д. Барбур и др. внесли значительный вклад в изучение распределения малых подграфов в случайном графе. Распределением количества деревьев занимались П. Эрдеш, А. Реньи, Б. Боллобаш, А.Д. Барбур и др. Вопросам, касающимся связности случайного графа, посвящены работы E.H. Гильберта, T.JI. Остина, П. Эрдеша, А. Реньи, В.Е. Степанова, И.Н. Коваленко, Г.И. Ивченко, И.В. Медведева, Б. Боллоба-ша и др. Поиском гигантской компоненты и определением ее размера занимались Т. Лучак, Дж. Вирман, Б. Боллобаш, П. Эрдеш, А. Реньи и др. При каких условиях случайный граф является гамильтоновым, можно узнать из работ И. Палясти, В.А. Перереплика, Дж.В. Муна, Е.М. Райта, Дж. Комло-ша, Е. Семереди, Л. Поша, А.Д. Коршунова и др. Длину максимального пути для р = с/N изучали М. Айтаи, Дж. Комлош, Е. Семереди, В.Ф. де л а Бега, Б. Боллобаш, Т.И. Фенне, A.M. Фриз и др. В работах А.Дж. Хоффмана, P.P. Синглетона, P.M. Дэмерелла, Е. Бэннэя, Т. Ито, Х.Д. Фридмана, П. Эрдеша, А. Реньи, Б. Боллобаша и др. изучено распределение диаметра случайного графа.
Помимо описанных моделей случайных графов изучались и многие другие. Остан�
