Изменения

|definition= '''Биномиальная модель случайного графа''' (англ. ''binomial random graph model'') <tex>G(n, p)</tex> {{---}} модель, в которой каждое ребро входит в случайный граф независимо от остальных ребер с вероятностью <tex>p</tex>. <tex>G(n, p) = (\Omega_n, F_n, P_{n, p})</tex> {{---}} [[ Вероятностное пространство, элементарный исход, событие | вероятностное пространство]]. <tex>|\Omega_n| = 2^{C^2_n}</tex>, <tex>P_{n, p}(G) = p^m(1 - p)^{C^2_n - m}</tex>, где <tex>m</tex> {{---}} число ребер в графе.

|definition= Свойство <tex>A</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>\lim\limits_{n \rightarrow \infty} p(n) = 0</tex>, где <tex>p(n)</tex> {{---}} вероятность графа <tex>G(n, p)</tex> обладать этим свойством.

|statement=Если <tex>p(n) = o(\dfrac{1}{n})</tex>, то <tex>G(n, p)</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^3p^3}{6}p^3 \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>.

<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>

|statement= Пусть <tex>Z_nN_z</tex> {{---}} число объектов в графе <tex>G(n, p)</tex>. <tex>A = \{G | Z_nN_z(G) > 0 \}</tex> {{---}} свойство. Тогда, если <tex>EZ_n E[N_z] \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>, то <tex>A</tex> а.п.н ложно.

<tex>P(Z_n N_z > 0) = P(Z_n N_z \geqslant 1) \leqslant EZ E[N_z] \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>.

|statement= Пусть <tex>Z_nN_z</tex> {{---}} число объектов в графе <tex>G(n, p)</tex>. <tex>A = \{G | Z_nN_z(G) > 0 \}</tex> {{---}} свойство. Тогда, если <tex>EZ_n 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> а.п.н истинно.

<tex>P(Z_n N_z = 0) = P(Z_n N_z \leqslant 0) = P(EZ_n E[N_z] - Z_n N_z \geqslant EZ_nE[N_z]) \leqslant P(|EZ_n E[N_z] - Z_nN_z| \geqslant EZ_nE[N_z]) \leqslant \dfrac{DZ_nD[N_z]}{(EZ_nE[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>u</tex> и <tex>v</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>EN_z^2 = E(\sum B_{i, j})^2 = E\sum B_{i,j}^2 + E\sum B_{i,j}B_{k,l} = EN_z + \sum EB_{i,j}B_{k,l}</tex> Рассмотрим сумму <tex>\sum EB_{i,j}B_{k,l}</tex>: Если <tex>i</tex>, <tex>j</tex>, <tex>k</tex> и <tex>k</tex> различны, то <tex>EB_{i,j}B_{k,l} \leqslant (1 - p^2)^{2(n - 4)} \leqslant n^{-2c^2}(1 + o(1))</tex>. <tex>\sum EB_{i,j}B_{k,l} \leqslant n^{4 - 2c^2}(1 + o(1))</tex> <tex>EB_{i,j}B_{i,l} = (1 - p + p(1 - p)^2)^{n - 3} \approx (1 - 2p^2)^{n - 3} = (1 - 2c^2\dfrac{\ln n}{n})^{n - 3} \approx e^{-2c^2 \ln n} = n^{-2c^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>.