Изменения
Нет описания правки
# Докажите, что для любого $\varepsilon > 0$ в $G(n, \frac 12)$ матожидание количества независимых множеств размера $(2 - \varepsilon) \log_2 n$ стремится к $\infty$.
# Докажите, что для любого $\varepsilon > 0$ в $G(n, \frac 12)$ а.п.н. существует независимое множество размера $(2 - \varepsilon) \log_2 n$.
# Пусть $p = \omega(\frac 1n)$. Покажите, что $G(n, p)$ а.п.н. содержит цикл.
# Пусть $p = \frac dn$. Что можно сказать про наличие циклов в $G(n, p)$ в зависимости от $d$?
# Рассмотрим случайный двудольный $G(n, n, p)$, пусть $p = \omega(\frac{\log n}{n})$. Докажите, что $G$ а.п.н. содержит полное паросочетание. Указание: используйте лемму Холла.
# Рассмотрим случайный двудольный $G(n, n, p)$, пусть $p = o(\frac{\log n}{n})$. Докажите, что $G$ а.п.н. не содержит полное паросочетание. Указание: используйте лемму Холла.
# Пусть $p = \frac{\ln n + c}{n}$. Какой предел вероятности, что у $G(n,p)$ ровно $k$ изолированных вершин?
# Докажите, что если $p = \frac{d}{n}$, $d > 1$, то все компоненты связности, кроме гигантской, а.п.н. являются деревьями.
# Докажите, что если $p = \frac{d}{n}$, $d > 1$, то в графе а.п.н. нет компоненты связности ровно с одним циклом.
# Пусть $C$ компонента связности графа $G(n, m)$ в равномерной модели, причем размер $C$ это $k = O(1) $, а $m = o(n)$. Найдите предел вероятности, что $C$ останется компонентой связности после добавления в граф $\alpha n$ случайных ребер, которых там еще нет (то есть при переходе к графу $G(n, m+\alpha n)$).
# Докажите, что любой граф с $n$ вершинами и $m$ ребрами содержит двудольный подграф с как минимум $\frac m2$ ребрами.
# Пусть граф $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$.
# Докажите, что $\alpha(G) \ge \sum (1 + \deg u)^{-1}$ с помощью вероятностного метода.
# Постройте матроид с 4 элементами и 5 базами. Укажите множество циклов этого матроида.
# Постройте матроид с 5 элементами и 12 базами.
