Законы нуля или единицы и закон больших чисел для случайных графов тема диссертации и автореферата по ВАК РФ 01.01.05, кандидат физико-математических наук Жуковский, Максим Евгеньевич

• Жуковский, Максим Евгеньевич
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Жуковский, Максим Евгеньевич

Оглавление

Список основных обозначений

Введение

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

1.1 Законы нуля или единицы

1.2 Случайные дистанционные графы

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

1.4 Ослабленные законы нуля или единицы для случайных дистанционных графов

2 Законы нуля или единицы для случайных графов Эрдеша и Реньи

2.1 Формулы с ограниченной кванторной глубиной

2.2 Распределение малых подграфов

2.3 Ослабленный закон

3 Закон больших чисел в модели эпидемии на полном графе

3.1 Модели эпидемии на полном графе

3.2 Закон больших чисел для количества активированных частиц

Список литературы

Список основных обозначений

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. Дэмерелла, Е. Бэннэя, Т. Ито, Х.Д. Фридмана, П. Эрдеша, А. Реньи, Б. Боллобаша и др. изучено распределение диаметра случайного графа.

Помимо описанных моделей случайных графов изучались и многие другие. Остановимся на самых известных. Модель G(N, М) по своим свойствам и по количеству опубликованных статей о ней похожа на C(7V, р). Пусть М — натуральное число из отрезка [1,Сдг], а Пдг,м ~ множество всех графов G = (Удг,Е) с условием \Е\ = М. Тогда случайным графом G{N,M) называется случайный элемент с равномерным распределением на множестве Как уже было отмечено, граф G(N,M) похож по своим свойствам на G(N,p). Многие авторы, исследовавшие граф G(N,p), посвятили часть своих работ и графу G(N,M), получив для него схожие результаты. Случайный дистанционный граф и граф G(N,p) являются частным случаем графа G(N, {Pi^n^eii,-.^})- Если при определении случайного графа считать, что некоторые пары вершин соединены с различными вероятностями, т.е. ребро {xi1}xi2}, 1 < xi,¿2 < N, проведено с вероятностью р^2 е [0,1], то будем обозначать такой граф G(N, {р^2}{г,г2^{1,...,щ)- Одним из важнейших примеров этого случайного графа является случайный граф G(Gn,v)i где Qn = (V/V; £/v) — неориентированный граф на N вершинах без петель и кратных ребер. А именно, G(QN,p) = G(N, {i>»1t2}illi2e{ 1,...,лг>), если

Заметим, что случайный дистанционный граф, это есть не что иное, как граф

р, {xiltxi2} £ SN]

0, {xi, ) Xi2

С(Ом,р), где Ом ~~ дистанционный граф а в случае графа Эрдеша и

Реньи Ом — это полный граф на N вершинах.

Упомянем еще одну модель случайного графа, случайный регулярный граф. Пусть натуральное число г не превосходит N — 1 и гИ — четное число. Пусть, кроме того, £1Г{Ы) — множество всех г-регулярных графов на множестве вершин У/у Тогда случайный элемент СГ(Л^), имеющий равномерное распределение на называется случайным регулярным графом. Эта

модель менее изучена, чем р) и С (ТУ, М), так как получение короткой асимптотической формулы для числа г-регулярных графов на N вершинах является сложной задачей. В 1960 году Р. Рид установил точную формулу для этого числа. К сожалению, эту формулу редко удается применить. Для нахождения асимптотики ее используют только в случае г < 3. Задачами такого рода занимались также Ф. Харари, Е.М. Палмер, Е.А. Бендер, Е.Р. Кэнфилд, А. Бекеши, Р. Бекеши, Дж. Комлош, Б. Боллобаш.

В третьей главе нами рассмотрено обобщение известной модели эпидемии на полном графе. В последнее десятилетие огромное количество работ было посвящено построению моделей эпидемии на графах (см., например, [14], [15], [21], [35], [39], [40], [48]) и изучению их вероятностных свойств. Подобными задачами занимались Р. Дюррет, С. Попов, А. Телке, Н. Вормалд, Е. Ли-бенстэин, О. Алвеш, Ф. Машадо, И. Куркова и другие. Такая активность связана с тем, что модели эпидемии играют существенную роль в изучении эволюции веб-графа. Изучение моделей эпидемии началось с рассмотрения графа, вершины которого являются точками в Zd. В момент Ь = 0 в каждой вершине находится частица. Все частицы неактивны, за исключением одной, которая находится в точке 0. Время Ь дискретно. Как только частица становится активной, она начинает симметричное случайное блуждание на Zбí, не зависящее от всех остальных активных частиц. Частица становится активной, если в ее точку совершает скачок некоторая активная частица. Эта модель является дискретным вариантом модели, предложенной в 1996 году Р. Дюрретом. В 1999 году А. Телке и Н. Вормалд (см. [48]) доказали, что почти наверное точка 0 будет посещена активными частицами бесконечно много раз. Кроме того, в 2001 году С. Попов доказал, что то же самое верно в размерности с1 > 3 в модели, в которой в момент Ь = 0 в каждой точке х ^ 0 неактивная частица находится с вероятностью а/||х||2, а некоторая положительная константа.

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

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

Модель эпидемии на полном графе была рассмотрена в 2010 году Ф. Ма-шадо, X. Машурианом и X. Матзингером в [37]. Они рассматривали следующую ситуацию. Пусть {жх, ...,хп} — некоторое множество точек. В момент времени £ = 0 во всех точках находится по одной частице. В точке Х\ располагается активная частица, а во всех остальных — неактивные. В каждый момент времени Ь ровно одна активная частица, номер которой имеет равномерное распределение на множестве номеров активных частиц в момент

совершает скачок в некоторую точку х^) (обменивается информацией с частицей, находящейся в точке х^))- При этом случайная величина £(£) имеет равномерное распределение на {1, ...,п}. Если частица прыгает в точку с неактивной частицой, то эта частица активируется. Активная частица умирает, если прыгает в точку, в которой находится или побывала ранее активная частица (при этом активная частица, которая находилась в этой точке, выживает). В частности, если она прыгает в точку, в которой находится, то тоже погибает. Пусть величина Рп(£) равна количеству неактивных частиц в момент £, а ап — момент, в который погибает последняя активная частица. Для случайной величины Хп = п — Оп{ап) в [37] доказана центральная предельная теорема. Мы построили более сложную модель, предположив, что каждый раз скачки совершают несколько частиц, причем количество таких частиц случайно, и получили для нее закон больших чисел (ЗБЧ), см. главу 3.

Для доказательства основных результатов диссертации мы использовали разнообразную технику. Так, установление законов нуля или единицы потребовало не только применения теоремы Эренфойхта (см. [23], [30], [45] и раздел 1.1), использования свойства полного расширения, метода моментов, но и разработки нового метода подсчета малых подграфов определенного вида в некотором графе при заданном количестве вхождений других подграфов. Мы также ввели понятие нейтральной пары графов, позволившее представить любую пару вложенных друг в друга графов в виде «композиции» нейтральных пар, а также «надежных» и «жестких» пар, предложенных Дж. Спенсером и С. Шела (см. [44]). Данное понятие сыграло ключевую

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Жуковский, Максим Евгеньевич, 2012 год

Список литературы

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

[2] A.B. Булинский, А.Н. Ширяев, Теория случайных процессов, Физматлит, Москва, 2005.

[3] Н.К. Верещагин, А. Шень, Языки и исчисления, Москва, МЦНМО, 2000.

[4] Ю.В. Глебский, Д.И. Коган, М.И. Лиогонький, В.А. Таланов, Объем и доля выполнимости формул узкого исчисления предикатов, Кибернетика 2, 1969, с. 17-26.

[5] В.Ф. Колчин, Случайные графы, 2-е издание, Физматлит, Москва, 2004.

[6] H.H. Кузюрин, Вероятностные приближенные алгоритмы в дискретной оптимизации, Дискретн. анализ и исслед. опер., сер. 2, 2002, 9(2): 97-114.

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

[8] В.В. Петров, Предельные теоремы для сумм независимых случайных величин, Наука, Москва, 1987.

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

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

[11] A.M. Райгородский, К.А. Михайлов, О числах Рамсея для полных дистанционных графов с вершинами в {0, 1}"*, Матем. сборник, 2009, 200(12): 63-80.

[12] В.А. Успенский, Н.К. Верещагин, В.Е. Плиско, Вводный курс математической логики, МГУ, Физматлит, Москва, 1997.

[13] А.Н. Ширяев, Вероятность, том 1, 4-е издание, МЦНМО, Москва, 2007.

15

16

17

18

19

20

21

22

23

24

25

26

27

28

0. Alves, F. Machado, S. Popov, Phase transition for the frog model, Electron. J. Probab., 2002, 7(16): 1-25.

0. Alves, F. Machado, S. Popov, The shape theorem for the frog model, Ann. Appl. Probab., 2002, 12(2): 534-547.

B. Bollobas, Random Graphs, 2nd Edition, Cambridge University Press, 2001.

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

J. Brenner, L. Cummings, The Hadamard Maximum Determinant Problem, The American Mathematical Monthly, 1972, 79(6): 626-630.

H. Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, The Annals of Mathematical Statistics, 1952, 23(4): 493-507.

K.J. Compton, 0—1 laws in logic and combinatorics, Proc. NATO Advanced Study Institute on Algorithms and Order (I. Rival, ed.), Reidel, Dordrecht, 1988, 353-383.

R. Durrett, Random Graph Dynamics, Cambridge University Press, New York, 2007.

H.-D. Ebbinghaus, J. Flum, Finite model theory, 2nd Edition, Springer, 1999.

A. Ehrenfeucht, An application of games to the completness problem for formalized theories, Warszawa, Fund. Math., 1960, 49: 121-149.

P. Erdos, A. Renyi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutato Int. Kozl., 1960, 5: 17-61.

R. Fagin, Probabilities in finite models, J. Symbolic Logic, 1976, 41: 50-58.

P. Frankl, R. Wilson, Intersection theorems with geometric consequences, Combinatorica, 1981, 1: 357-368.

R.H. Gilman, Y. Gurevich, and A. Miasnikov, A geometric zero-one law, 2007, arXiv:0706.0271.

Y. Gurevich, Chapter Zero-one laws, Book Current trends in theoretical computer science, edited by G. Rozenberg and A. Salomaa, World Scientific Series in Computer Science, Volume 40, 1993.

P.E. Haxell, Y. Kohayakawa, T. Luczak, Turan's extremal problem in random graphs: forbidding even cycles, J. Combin. Theory, Ser. B, 1995, 64: 273-287.

[30] S. Janson, T. Luczak, A. Ruciriski, Random Graphs, New York, Wiley, 2000.

[31] G. Kabatiansky, E. Krouk, S. Semenov, Error Correcting Codes and Security for Data Networks, Wiley and Sons, 2005.

[32] J. Kahn, G. Kalai, A counterexample to Borsuk's conjecture, Bulletin (new series) of the AMS, 1993, 29(1): 60-62.

[33] P.G. Kolaitis, H.J. Promel and B.L. Rothschild, Ki+\-free graphs: asymptotic structure and a 0—1 law, Transactions of the American Mathematical Society, 1987, 303(2): 637-671.

[34] I. Kurkova, S. Popov, M. Vachkovskaia, On infection spreading and competition between independent random walks, Electron. J. Probab., 2004, 9(11): 1-22.

[35] E. Lebensztayn, F. Machado, S. Popov, An improved upper bound for the critical probability of the frog model on homogeneous trees, J. Statist. Phys., 2005, 119(1-2): 331-345.

[36] T. Luczak, J. Spencer, When does the zero-one law hold?, J. Amer. Math. Soc., 1991, 4: 451-468.

[37] F. Machado, H. Mashurian, H. Matzinger, CLT for the proportion of infected individuals for an epidemic model on a complete graph, 2010, arXiV: 1011.3601vl.

[38] M. McArtur, The asymptotic behavior of L^ on sparse random graphs, Logic and Random Structures, 1997, 33: 53-63.

[39] S. Popov, Frogs in random environment, J. Statist. Phys., 2001, 102(1/2): 191-201.

[40] A.F. Ramirez, V. Sidoravicius, Asymptotic behavior of a stochastic combustion growth process, J. Eur. Math. Soc. (JEMS), 2004, 6(3): 293-334.

[41] A.F. Ramirez, V. Sidoravicius, Asymptotic behavior of a growth process of boundary branching random walks, C. R. Math. Acad. Sci. Paris, 2002, 335(10): 821-826.

[42] H.P. Rosenthal, On the span in Lv of sequences of independent random variables, Proc. 6th Berkeley Symp. Math. Statist. Probability, v.2. Berkeley — Los-Angelos: Univ. of California press, 1972, 149-168.

[43] H.P. Rosenthal, On the subspaces of LP (p > 2) spanned by sequences of independent random variables, Israel J. Math., 1970, 8(3): 273-303.

[44] S. Shelah, J.H. Spencer, Zero-one laws for sparse random graphs, J. Amer. Math. Soc., 1988, 1: 97-115.

[45] T. Shwentick, On Winning Ehrenfeucht Games and Monadic NP, Ann. Pure Appl. Logic, 1996, 79(1): 61-92.

[46] J.H. Spencer, Counting extensions, J. Comb. Th., Ser. A, 1990, 55: 247-255.

[47] J.H. Spencer, The Strange Logic of Random Graphs, Number 22 in Algorithms and Combinatorics, Springer-Verlag, Berlin, 2001.

[48] A. Teles, N. Wormald, Branching and tree indexed random walks on fractals, J. Appl. Probab., 1999, 36: 999-1011.

[49] M.E. Жуковский, Закон больших чисел для модели эпидемии, Доклады Академии Наук, 2012, 442(6): 736-739.

[50] М.Е. Жуковский, Законы нуля или единицы для формул первого порядка с ограниченной кванторной глубиной, Доклады Академии Наук, 2011, 436(1): 14-18.

[51] М.Е. Жуковский, О последовательности случайных дистанционных графов, подчиняющейся закону нуля или единицы, Проблемы передачи информации, 2011, 47:3, 39-57.

[52] М.Е. Жуковский, Ослабленные законы нуля или единицы для случайных дистанционных графов, Теория вероятностей и ее применения, 2010, 55: 344-350.

[53] М.Е. Жуковский, Ослабленный закон нуля или единицы для случайных дистанционных графов, Доклады Академии Наук, 2010, 430(3): 314-317.

[54] М.Е. Жуковский, Ослабленный закон «нуля или единицы» для случайных дистанционных графов, Вестник РУДН, 2010, 2(1): 11-25.

[55] М.Е. Жуковский, Оценка количества максимальных расширений в случайном графе, Дискретная Математика, 2012, 24(1): 79-107.

[56] М.Е. Zhukovskii, Zero-one k-law, Discrete Mathematics, 2012, 312: 1670— 1688.