244
правки
Изменения
Нет описания правки
# Докажите, что для любого $\varepsilon > 0$ в $G(n, \frac 12)$ а.п.н. существует независимое множество размера $(2 - \varepsilon) \log_2 n$
# Найдите пороговую асимптотику, что граф $G(n, p)$ является эйлеровым или докажите, что её не существует
# Докажите, что если $k = \frac{\log n}{\log\log n}$, то $k! \le n$.
# Покажите, что в первой доле случайного двудольного графа $G(n, n, 1/n)$ с вероятностью, не стремящейся к нулю, существует вершина степени $\frac{\log n}{\log \log n}$.
# Зачем условие двудольности в предыдущей задаче? Покажите, что его можно убрать, в случайном графе $G(n, 1/n)$ с вероятностью, не стремящейся к нулю, существует вершина степени $\frac{\log n}{\log \log n}$.
# Докажите, что $G(n, 1/n)$ а.п.н. не содержит вершины степени больше $\frac{6\log n}{\log \log n}$. Указание, используйте приближение биномиального распределения Пуассоном и факт, что $k! \ge (k/e)^k$.
# Пусть $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$ изолированных вершин?
# Петя пытается спрятать в случайном графе клику размера $k$. Он берет граф с $n$ вершинами, $k$ из которых образуют клику, а остальных ребер нет, после чего проводит каждое из оставшихся ребер с вероятностью $1/2$. Вася хочет найти спрятанную Петей клику - выяснить, какие вершины ее образовывали. Для этого он выбирает $k$ вершин максимальной степени. Докажите, что если $k = \omega(\sqrt{n \ln n})$, то Вася а.п.н. найдет спрятанную Петей клику.
# Задача о наибольшем общем подграфе. Рассмотрим два графа, выбранных из распределения $G(n, 1/2)$. Найдем их общий индуцированный подграф размера $k$: выберем в каждом графе по $k$ вершин, оставим все ребра между ними, получившиеся графы должны быть изоморфны. Докажите, что наибольший общий подграф двух графов а.п.н. имеет размер не больше $4 \log_2 n$.
# Напишите генератор графов $G(n, p)$ на вашем любимом языке программирования и примените в этом и последующих заданиях. Проведите численные эксперименты с генератором для различных значений $n$ и $p$, соотнесите результаты с теорией, которую вы узнали на лекциях. В качестве ответа на задание продемонстрируйте графики зависимости вероятности от $p$, другие результаты численных экспериментов, можно также запускать программу с демонстрацией результатов запуска на проекторе. Проанализируйте появление треугольников для $p=\frac cn$ в зависимости от константы $c$.
# Продемонстрируйте появление свойства "диаметр 2" при $p=\sqrt{2 \ln n/n}$.
# Проанализируйте исчезновение изолированих вершин и появление связности на одном графике.
