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

• Автор: Жуковский, Максим Евгеньевич
• Шифр специальности: 01.01.05
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Москва
• Количество страниц: 98 с.

Оглавление
Список основных обозначений
Введение
1 Законы нуля или единицы для случайных дистанционных графов
1.1 Законы нуля или единицы
1.2 Случайные дистанционные графы
1.3 Законы нуля или единицы для случайных дистанционных графов
1.4 Ослабленные законы нуля или единицы для случайных дистанционных графов
2 Законы нуля или единицы для случайных графов Эрдеша и Реньи
2.1 Формулы с ограниченной кванторной глубиной
2.2 Распределение малых подграфов
2.3 Ослабленный закон
3 Закон больших чисел в модели эпидемии на полном графе
3.1 Модели эпидемии на полном графе
3.2 Закон больших чисел для количества активированных частиц
Список литературы

Список основных обозначений
N — множество натуральных чисел;
/cN — множество натуральных чисел, кратных /с;
Z — множество целых чисел;
Z+ — множество целых неотрицательных чисел;
Q — множество рациональных чисел;
R — множество действительных чисел;
В (Ж) — сг-алгебра борелевских подмножеств R;
|Л| (или §А) — мощность конечного множества А;
[а] — целая часть числа а;
НОК — наименьшее общее кратное;
аЪ свойство «а делит Ь», т.е. число а является делителем числа b;
1(E) — индикатор события Е
ЕХ — математическое ожидание случайной величины X;
DX — дисперсия случайной величины X;
<у(Х) — сигма-алгебра, порожденная случайной величиной X, т.е. множество {{ш : Х(и) £ В} : Be i3(K)};
(х, у) — евклидово скалярное произведение векторов х и у;

[|х|| — норма вектора х в евклидовом пространстве;
У(Є) — множество вершин графа (7;
Е(Є) — множество ребер графа С;
у{С) — количество вершин графа (7;
е((7) — количество ребер графа (7;
а((7) — количество автоморфизмов графа (7;
(7у — подграф графа <7, индуцированный на множество V;
(7 N Ь — предикат, истинный тогда и только тогда, когда граф С обладает свойством Ь]
/(ІГ) = о((ЛГ)) -- для любого числа с > 0 существует такое число Л, что для любого N > N0 выполнено неравенство |/(АГ)| < сд(ІГ)|;
/(/7) = <7(ф(ІУ)) — найдется такое число С > 0, что для любого ІУ Є N выполнено неравенство |/(ЛГ)| < Сд(М);
/(-/V) = 0(д(ЛГ)) — найдутся такие числа с, С > 0, что для любого Я Є N выполнены неравенства с|(ЛГ)| < |/(ЛГ)| < Сд(Ы).

Вектор

п + 1 п
1 3 п

2 п — 4 2п +

является решением системы Л(5)х = В Предположим, что существует искомое решение у системы А(5)у — Тогда у§ £ {0,1}. Если уд = О, то 5уь = п, но число п не кратно 5. Если же у§ = 1, то Ьу — 2 = п, но число п + 2 не кратно 5.
Если 5|(п — 2), то векторы ¥ и § снова оставим без изменений, а матрицы А(5) и Л(5) определим равенствами
А(5)
Вектор
/1 1 1 0 0 0 ( 1 і 1 0 0 0
1 0 1 1 0 0 0 -і 0
1 1 0 1 1 0 , А(5) = 0 0 -1
0 1 1 1 0 1 0 0 0
0 1 0 1 0) 0 0 0 -5 1
"V _ ( п + 3 п — 2 Зп — 1 п - - 2 2п + 1 f
Л. - 1 К 5 ’ 5 5 5 ’ 5 5 5 ) -1
является решением системы Л(5)х = f. Предположим, что существует искомое решение у системы Н(5)у = g. Тогда у§ £ {0,1}. Если у = О, то 55 = п, но число п не кратно 5. Если же у§ — 1, то Ьу$ + 1 = п, но число п — 1 не кратно 5. Получили противоречие. Следовательно, число п кратно 5.
Пусть 8|(п — 4). Рассмотрим матрицу А(5), определенную равенством
А(5)
/ 1 1 о о о
10 10 0 10 0 1 о

V о і і і і

Вектор
"3п п п п п'
Т’ 4’ 4’ 4’I
является единственным решением системы Л(5)х = Но у системы А(5)у = g нет решений. Таким образом, число п кратно 8. Лемма доказана.