Изменения
Issues
|definition= Свойство <tex>A</tex> '''ассимптотически почти наверное ложно''', если <tex>\lim\limits_{n \rightarrow \infty} p(n) = 0</tex>
}}
'''''Здесь стоит написать, что такое n и p(n).'''''
== Существование треугольников в случайном графе ==
{{Теорема
|statement=Если <tex>p(n) = o(\dfrac{1}{n})</tex>, то <tex>G(n, p)</tex> а.п.н не содержит треугольников.'''''Лучше не сокращать а.п.н, я думаю, или в скобочках разок написать, что это'''''
|proof=
Пусть <tex>T</tex> {{---}} число треугольников в графе, <tex>T_{i,j,k}</tex> {{---}} индикаторная случайная величина, равная <tex>1</tex>, если вершины <tex>i</tex>, <tex>j</tex> и <tex>k</tex> образуют треугольник.
Воспользуемся [[Неравенство Маркова| неравенством Маркова]]:
<tex>P(T > 0) = P(T \geqslant 1) \leqslant ET E[T] = \sum\limits_{i, j, k}T_{i, j, k}p^3 = C^3_np^3 \sim \dfrac{n^3}{6}p^3 \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>.
}}
'''''Добавил скобки вокруг E[T], оформи так же, а то слабо читается. С дисперсией тоже лучше добавить. Деление на 6 должно появиться под суммой сразу'''''
{{Теорема
|statement=Если <tex>p(n) = \omega(\dfrac{1}{n})</tex>, то <tex>G(n, p)</tex> а.п.н содержит треугольник.
|proof=
Пусть <tex>T</tex> {{---}} число треугольников в графе, <tex>T_{i,j,k}</tex> {{---}} индикаторная случайная величина, равная <tex>1</tex>, если вершины <tex>i</tex>, <tex>j</tex> и <tex>k</tex> образуют треугольник.
|statement=Если <tex>c \geqslant 3</tex>, <tex>n \geqslant 100</tex>, <tex>p = \dfrac{c\ln n}{n}</tex>. Тогда <tex>P(G - связен) \rightarrow 1</tex>.
|proof=
Пусть <tex>X</tex> {{---}} индикаторная величина, равная <tex>0</tex>нулю, если <tex>G</tex> связен, и <tex>k</tex>, если <tex>G</tex> содержит <tex>k</tex> компонент связности.
<tex>X_i</tex> {{---}} число компонент связности размера <tex>i</tex>.
{{Теорема
|statement=Пусть рассматривается свойство графа иметь диаметр два. Тогда <tex>p = \sqrt{2} \sqrt{\dfrac{\ln n}{n}}</tex> {{---}} порог.
'''''что такое порог?'''''
|proof=
Назовем вершины <tex>u</tex> и <tex>v</tex> плохой парой, если <tex>dist(u, v) > 2</tex>'''''мб лучше написать про расстояние явно, но думаю, всем будет понятно'''''. <tex>B_{i, j}</tex> {{---}} индикаторная величина, равная <tex>1</tex>, если <tex>i</tex> и <tex>j</tex> плохая параявляются плохой парой.
<tex>N_z = \sum\limits_{i, j} B_{i,j}</tex>
<tex>P(B_{i, j}) = (1 - p)(1 - p^2)^{n - 2}</tex>
Сначала докажем, что при <tex>c > sqrt{2}</tex>, граф а.п.н не имеет диаметр два, равный двум. Для этого оценим матожидание <tex>N_z</tex>.
<tex>EN_z = C_n^2(1 - p)(1 - p^2)^{n - 2} \approx \dfrac{n^2}{2}(1 - c\sqrt{\dfrac{\ln n}{n}})(1 - \dfrac{c^2\ln n}{n})^{n - 2} \leqslant \dfrac{n^2}{2}e^{-c^2\ln n} = \dfrac{n^{2 - c^2}}{2}</tex>
При <tex>c > \sqrt{2}</tex> последнее выражение стремится к <tex>0</tex>, по [[#th1 | первой теореме вышедоказанному ]] граф а.п.н. не имеет диаметр два, равный двум.
Рассмотрим <tex>c < \sqrt{2}</tex>:
<tex>\sum EB_{i,j}B_{i,l} \leqslant n^{3 - 2c}</tex>
В итоге: <tex>EN_z^2 \leqslant n^{2 - c^2} + n^{4 - 2c^2} + n^{3 - 2c^2}</tex>. Из этого следует, что <tex>EN_z \leqslant (EN_z)^2(1 + o(1))</tex>, а значит граф а.п.н имеет диаметр два , равный двум при <tex>c > \sqrt{2}</tex>.
}}
