Изменения
Нет описания правки
# Пусть для некоторого свойства $A$ существует две функции $p_1(n)$ и $p_2(n)$, что для графа $G(n, p_1(n))$ свойство $A$ а.п.н. не выполняется, а для $G(n, p_2(n))$ свойство $A$ а.п.н. выполняется. Докажите, что существует функция $\tilde p(n)$, что для случайного графа $G(n, \tilde p(n))$ свойство $A$ выполняется с вероятностью, стремящейся к $\frac 12$.
# Докажите, что $G(n, \frac {2\ln n}{n})$ а.п.н. не содержит вершин степени 0.
# Рассмотрим модель случайного двудольного графа $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.
# Пусть $p = o(n^{-\frac 23})$. Докажите, что а.п.н. $G(n, p)$ не содержит $K_4$.
# Пусть $p = \o(\frac 1n)$ и $k$ -- константа. Покажите, что $G(n, p)$ а.п.н. не содержит цикл длины $k$.
# Пусть $p = \omega(\frac 1n)$ и $k$ -- константа. Покажите, что $G(n, p)$ а.п.н. содержит цикл длины $k$.
# Пусть $p = o(\frac 1n)$. Покажите, что $G(n, p)$ а.п.н. не содержит циклов.
# Покажите, что матожидание количества остовных деревьев у графа $G(n, \frac {\ln n}{2n})$ стремится к бесконечности.
# Покажите, что матожидание количества остовных деревьев у графа $G(n, \frac {2\ln n}{n})$ стремится к бесконечности. Можно ли это считать доказательством а.п.н. связности графа $G(n, \frac {2\ln n}n)$?
# Найдите матожидание количества индуцированных подграфов $G(n, \frac dn), d > 1$, которые являются путем длины $k = \sqrt{\log n}$.
# Подберите $p(n)$ и приведите последовательности случайных величин $X_n$ для $G(n, p)$, что $EX_n \to \infty$, но $\mathcal{P}(X_n = 0) \nrightarrow 0$.
# Для каких $p$ граф $G(n, p)$ а.п.н. не содержит $K_k$ (надо привести пороговую асимптотику)?
# Пусть $p = \frac dn$. Докажите, что в $G(n, p)$ каждая вершина а.п.н. принадлежит не более, чем одному треугольнику.
# Докажите, что в $G(n, \frac 12)$ а.п.н. не существует независимого множества размера $2 \log_2 n$
# Докажите, что для любого $\varepsilon > 0$ в $G(n, \frac 12)$ матожидание количества независимых множеств размера $(2 - \varepsilon) \log_2 n$ стремится к $\infty$.
# Докажите, что для любого $\varepsilon > 0$ в $G(n, \frac 12)$ а.п.н. существует независимое множество размера $(2 - \varepsilon) \log_2 n$.
