Изменения
Нет описания правки
# Докажите, что если $p = \omega(\frac{1}{n^2})$, то случайный граф $G(n, p)$ а.п.н. имеет хотя бы одно ребро.
# Пусть $p = \frac{c}{n^2}$ для некоторого $c$. Найдите вероятность того, $G(n, p)$ имеет хотя бы одно ребро.
# Оцените центральный биномиальный коэффициент ${2n \choose n}$ снизу величиной порядка $\frac {c4^n}{\sqrt{n}}$. Указание: используйте формулу Стирлинга.
# Рассмотрим число ребер $m$, такое что $m(n) \to \infty$ и ${n \choose 2} - m(n) \to \infty$, а также $p(n) = \frac {m(n)}{n \choose 2}$. Докажите, что вероятность того, что $G(n, p)$ имеет ровно $m$ ребер есть $\Omega(m^{-0.5})$.
# Рассмотрим свойство $A$, а и такие же $m(n)$ и $p(n)$, как в предыдущей задаче. Докажите, что $P(G(n, m) \in A) \le C \sqrt{m} P(G(n, p) \in A)$.
