2
правки
Изменения
м
'''''Добавил скобки вокруг E[T], оформи так же, а то слабо читается. С дисперсией тоже лучше добавить. Деление на 6 должно появиться под суммой сразу'''''
→Существование треугольников в случайном графе
}}
{{Определение
|definition= Свойство <tex>A</tex> графа <tex>G(n, p(n))</tex> '''асимптотически почти наверное истинно''', если <tex>\lim\limits_{n \rightarrow \infty} p(n) = 1</tex>, где <tex>p(n)</tex> {{---}} вероятность графа <tex>G(n, p)</tex> обладать этим свойством.
}}
{{Определение
|definition= Свойство <tex>A</tex> графа <tex>G(n, p(n))</tex> '''асимптотически почти наверное ложно''', если <tex>\lim\limits_{n \rightarrow \infty} p(n) = 0</tex>, где <tex>p(n)</tex> {{---}} вероятность графа <tex>G(n, p)</tex> обладать этим свойством.
}}
Воспользуемся [[Неравенство Маркова| неравенством Маркова]]:
<tex>P(T > 0) = P(T \geqslant 1) \leqslant E[T] = \sum\limits_{i, j, k}T_{i, j, k}p^3 = C^3_np^3 \sim \dfrac{n^3p^3}{6}p^3 \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>.
}}
{{Теорема
Воспользуемся [[Неравенство Маркова#thCheb| неравенством Чебышева]]:
<tex>P(T = 0) = P(T \leqslant 0) = P(ET E[T] - T \geqslant ETE[T]) \leqslant P(|ET E[T] - T| \geqslant ETE[T]) \leqslant \dfrac{DTD[T]}{(ETE[T])^2}</tex>.
Найдем <tex>ETE[T^2]</tex>:
<tex>ETE[T^2 ] = E[(\sum\limits_{i, j, k}T_{i, j, k})^2]= E([\sum\limits_{i, j, k}(T_{i, j, k})^2) ] + E([\sum\limits_{i, j, k, a, b, c}T_{i, j, k}T_{a, b, c}) ] =</tex>
<tex>= ET E[T] + (C^3_nC^3_{n - 3} + C^3_nC^2_{n - 3})p^6 + 3C^3_n(n - 3)p^5 \sim \dfrac{n^3p^3}{6} + (\dfrac{n^6}{36} + \dfrac{n^5}{4})p^6 + \dfrac{n^4}{2}p^5 \sim \dfrac{n^3p^3}{6} + \dfrac{n^6p^6}{36} + \dfrac{n^4p^5}{2} \sim \dfrac{n^3p^3}{6} + \dfrac{n^6p^6}{36}</tex>
<tex>DT D[T] = ETE[T^2 ] - (ETE[T])^2 \sim \dfrac{n^3p^3}{6} + \dfrac{n^6p^6}{36} - \dfrac{n^6p^6}{36} = \dfrac{n^3p^3}{6}</tex>
<tex>P(T = 0) \leqslant \dfrac{\dfrac{n^3p^3}{6}}{\dfrac{n^6p^6}{36}} = \dfrac{6}{p^3n^3} \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>
<tex>X_i = \sum\limits_{a_1,a_2, \dots , a_i} X_{a_1,a_2, \dots , a_i}</tex>
<tex>EX_i E[X_i] = \sum\limits_{a_1,a_2, \dots , a_i} EX_E[X_{a_1,a_2, \dots , a_i} ] = C_n^iEX_{1, 2, \dots, i} = C_n^i P(1, 2, \dots, i - комп.связности) \leqslant C_n^i (1 - p)^{i(n - i)}</tex>.
<tex>EX E[X] \sum\limits_{i = 1}^{n - 1} EX_i E[X_i] \leqslant \sum\limits_{i = 1}^{n - 1} C_n^i(1 - p)^{i(n - i)}</tex>
Последняя сумма симметрична (слагаемые при <tex>i = k</tex> и <tex>i = n - k</tex> равны), кроме того слагаемое при <tex>i = 1</tex> {{---}} наибольшее (для доказательства достаточно рассмотреть отношения слагаемых при <tex>i \leqslant \dfrac{n}{8}</tex> и <tex>\dfrac{n}{8} < i \leqslant \dfrac{n}{2}</tex>).
{{Теорема
|id=th1
|statement= Пусть <tex>N_z</tex> {{---}} число объектов в графе <tex>G(n, p)</tex>. <tex>A = \{G | N_z(G) > 0 \}</tex> {{---}} свойство. Тогда, если <tex>E[N_z ] \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>, то <tex>A</tex> а.п.н ложно.
|proof=
Воспользуемся [[Неравенство Маркова | неравенством Маркова]]:
<tex>P(N_z > 0) = P(N_z \geqslant 1) \leqslant EZ E[N_z] \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>.
}}
{{Теорема
|id=th2
|statement= Пусть <tex>N_z</tex> {{---}} число объектов в графе <tex>G(n, p)</tex>. <tex>A = \{G | N_z(G) > 0 \}</tex> {{---}} свойство. Тогда, если <tex>EN_z E[N_z] \rightarrow \infty</tex>, при <tex>n \rightarrow \infty</tex>, и <tex>EZE[N_z^2 = ] \leqslant (EZE[N_z])^2(1 + o(1))</tex> то <tex>A</tex> а.п.н истинно.
|proof=
Воспользуемся [[Неравенство Маркова#thCheb | неравенством Чебышева]]:
<tex>P(N_z = 0) = P(N_z \leqslant 0) = P(EN_z E[N_z] - N_z \geqslant EN_zE[N_z]) \leqslant P(|EN_z E[N_z] - N_z| \geqslant EN_zE[N_z]) \leqslant \dfrac{DN_zD[N_z]}{(EN_zE[N_z])^2} \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>.
}}
== Графы , имеющие диаметр два =={{Определение|definition=<tex>A</tex> {{---}} некоторое свойство случайного графа. <tex>p</tex> называется '''пороговой функцией''' (англ. ''threshold function''), если граф <tex>G(n, cp)</tex> при <tex>c < 1</tex> а.п.н не имеет такого свойства, а при <tex>c > 1</tex> а.п.н имеет.}}
{{Теорема
|statement=Пусть рассматривается свойство графа иметь диаметр два. Тогда <tex>p = \sqrt{2} \sqrt{\dfrac{\ln n}{n}}</tex> {{---}} порогпороговая функция.'''''что такое порог?'''''
|proof=
Назовем вершины <tex>u</tex> и <tex>v</tex> плохой парой, если кратчайшее расстояние между <tex>dist(u, </tex> и <tex>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>
