Изменения
Нет описания правки
# Пусть для некоторого свойства $A$ существует две функции $p_1(n)$ и $p_2(n)$, что для графа $G(n, p_1(n))$ свойство $A$ а.п.н. не выполняется, а для $G(n, p_2(n))$ свойство $A$ а.п.н. выполняется. Докажите, что существует функция $p'(n)$, что для случайного графа $G(n, p'(n))$ свойство $A$ выполняется с вероятностью, стремящейся к $\frac 12$.
# Докажите, что $G(n, \frac {2\ln n}{n})$ а.п.н. не содержит изолированных вершин.
# Рассмотрим модель случайного двудольного графа $G(n, n, p)$: из полного двудольного графа $K_{n,n}$ каждое ребро удаляется с вероятностью $1 - p$. Пусть $X$ -- количество изолированных вершин первой доли. Найдите $EX$ и $DX$.
# Докажите, что если $p = o(n^{-1.5})$, то $G(n, p)$ а.п.н. является объединением компонент связности размера 1 и 2.
# Докажите, что если $p = \omega(n^{-1.5})$, то $G(n, p)$ а.п.н. содержит путь длины 2.
# Выведите формулу вероятности того, что расстояние между фиксированными вершинами $u$ и $v$ не меньше двух.
# Пусть $p = c \sqrt{ \frac {\ln n}{n}}$, $c > \sqrt{2}$. Покажите, что $G(n, p)$ а.п.н. имеет диаметр не больше 2.
# Докажите, что $G(n, p)$ а.п.н имеет диаметр 2, если $p$ -- константа.
# Докажите, что $G(n, p)$ а.п.н имеет диаметр 2, если $p = c \sqrt{ \frac {\ln n}{n}}$, $c > \sqrt{2}$.
# Пусть $p = o(n^{-\frac 23})$. Докажите, что а.п.н. $G(n, p)$ не содержит $K_4$.
# Пусть $p = \frac dn$. Докажите, что в $G(n, p)$ каждая вершина а.п.н. принадлежит не более, чем одному треугольнику.
# Пусть $p = \omega(n)$ и $k$ -- константа. Покажите, что $G(n, p)$ а.п.н. содержит цикл длины $k$.
# Покажите, что матожидание количества остовных деревьев у графа $G(n, \frac {2\ln n}{n})$ стремится к бесконечности. Можно ли это считать доказательством а.п.н. связности графа $G(n, \frac {2\ln n}n)$?
# Докажите, что $G(n, \frac dn), d > 1$ а.п.н. содержит индуцированный путь длины $\sqrt{\log n}$.
# Подберите $p(n)$ и приведите пример случайной величины $X$ в модели случайного графа $G(n, p)$, что $EX \to \infty$, но $\mathcal{P}(X = 0) \nrightarrow 0$.
