Изменения
Нет описания правки
# Для каких $p$ граф $G(n, p)$ а.п.н. не содержит $K_k$ (надо привести пороговую асимптотику)?
# Докажите, что если $k = \frac{\log n}{\log\log n}$, то $k! \le n$.
# Покажите, что в первой доле случайного двудольного графа $G(n, n, 1/n)$ с вероятностью отличной от 0 , не стремящейся к нулю, существует вершина степени $\frac{\log n}{\log \log n}$.# Зачем условие двудольности в предыдущей задаче? Покажите, что его можно убрать, в случайном графе $G(n, 1/n)$ с вероятностью отличной от 0 , не стремящейся к нулю, существует вершина степени $\frac{\log n}{\log \log n}$.
# Докажите, что $G(n, 1/n)$ а.п.н. не содержит вершины степени больше $\frac{6\log n}{\log \log n}$. Указание, используйте приближение биномиального распределения Пуассоном и факт, что $k! \ge (k/e)^k$.
# Пусть $p = o(\frac 1n)$. Покажите, что $G(n, p)$ а.п.н. не содержит циклов.
