Изменения
Нет описания правки
# Докажите, что $G(n, \frac dn), d > 1$ а.п.н. содержит индуцированный путь длины $\sqrt{\log n}$.
# Подберите $p(n)$ и приведите пример случайной величины $X$ в модели случайного графа $G(n, p)$, что $EX \to \infty$, но $\mathcal{P}(X = 0) \nrightarrow 0$.
# Для каких $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)$ а.п.н. не содержит циклов.
# Пусть $p = \omega(\frac 1n)$. Покажите, что $G(n, p)$ а.п.н. содержит цикл.
# Пусть $p = \frac dn$. Что можно сказать про наличие циклов в $G(n, p)$?
# Рассмотрим случайный двудольный $G(n, n, p)$, пусть $p = o(\frac{\log n}{n})$. Докажите, что $G$ а.п.н. не содержит полного паросочетание. Указание: используйте лемму Холла.
# Рассмотрим случайный двудольный $G(n, n, p)$, пусть $p = \omega(\frac{\log n}{n})$. Докажите, что $G$ а.п.н. содержит полное паросочетание. Указание: используйте лемму Холла.
# Указание: в этом и следующих заданиях используйте вероятностный метод. Если вероятность, что объект обладает некоторым свойством, больше 0, то существует объект с таким свойством. Если матожидание числа объектов с некоторым свойством больше 0, то существует объект с таким свойством. Число Рамсея $R(a, b)$ - величина, такая что граф, содержащий хотя бы $R(a, b)$ вершин обязательно содержит или клику размера $a$ или независимое множество размера $b$. Оцените сверху вероятность, что граф из $G(n, \frac 12)$ содержит клику размера $k$ или независимое множество размера $k$. Сделайте вывод о нижней границе на число Рамсея: $R(k, k) \ge 2^{k/2}-1$.
# Докажите, что существует турнир, в котором как минимум $\frac {n!}{2^{n-1}}$ гамильтоновых путей.
# Докажите, что любой граф с $n$ вершинами и $m$ ребрами содержит двудольный подграф с как минимум $\frac m2$ ребрами.
# Докажите, что для любого $\varepsilon > 0$ в $G(n, \frac 12)$ существует независимое множества размера $(2 - \varepsilon) \log_2 n$.
# Пусть граф $G$ с $n$ вершинами и $m \ge 4n$ ребрами изображен на плоскости, причем никакие три ребра не пересекаются в одной точке, и никакое ребро не содержит вершину как свою внутреннюю точку. Обозначим как $c$ число попарных пересечений ребер вне вершин. Докажите, что $c \ge \frac{m^3}{64n^2}$.
# Пусть на плоскости выбрано $n$ точек, обозначим как $l$ число прямых, каждая из которых содержит хотя бы $k+1$ из заданных точек ($1 \le k \le 2\sqrt{2n}$). Докажите, что $l \le 32n^2/k^3$.
