Изменения
setmunis -> setminus
# Подберите $p(n)$ и приведите последовательности случайных величин $X_n$ для $G(n, p)$, что $EX_n \to \infty$, но $\mathcal{P}(X_n = 0) \nrightarrow 0$.
# Докажите, что $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 {2\ln n}{n})$ стремится к бесконечности. Можно ли это считать доказательством а.п.н. связности графа $G(n, \frac {2\ln n}n)$?
# Покажите, что матожидание количества остовных деревьев у графа $G(n, \frac {\ln n}{2n})$ стремится к бесконечности.
# Найдите матожидание количества индуцированных подграфов $G(n, \frac dn)$, $d > 1$, которые являются путем длины $k = \sqrt{\log n}$.
# Для каких $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$.
# Найдите пороговую асимптотику, что граф $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}$.
# Проанализируйте исчезновение изолированных вершин и появление связности на одном графике.
# Постройте матроид с 4 элементами и 5 базами. Укажите множество циклов этого матроида.
# Постройте матроид с 5 элементами и 12 базами.
# Матроид с выброшенным элементом. Пусть $M$ - матроид. Обозначим как $M\setminus x$ матроид, где из носителя выкинут элемент $x$. Независимыми объявляются независимые множества исходного матроида, которые не содержали $x$. Формально, если $M = \langle X, I\rangle$, то $M\setminus x = \langle X \setminus x, \{A \setminus x | A \in I, x \not\in A\}\rangle$. Докажите, что для любых $M$ и $x$ получившаяся конструкция $M\setminus x$ является матроидом.
# Матроид, стянутый по элементу. Пусть $M$ - матроид. Обозначим как $M/x$ матроид, где из носителя выкинут элемент $x$. Независимыми объявляются независимые множества исходного матроида, которые ранее содержали $x$, после удаления из них этого элемента. Формально, если $M = \langle X, I\rangle$, то $M/x = \langle X \setminus x, \{A \setminus x | A \in I, x \in A\}\rangle$. Докажите, что для любых $M$ и $x$, таких что $\{x\}\in I$ получившаяся конструкция $M/x$ является матроидом.
# Докажите, что если $x \ne y$, то $M\setminus x/y=M/y\setminus x$
# Урезанный матроид. Пусть $M = \langle X, I \rangle$ - матроид. Обозначим как $M|_k$ следующую констркуцию: $M|_k = \langle X, \{A | A \in I, |A| \le k \}\rangle$. Докажите, что $M|_k$ является матроидом.
# Прямая сумма матроидов. Пусть $X$ и $Y$ - непересекающиеся множества, $M_1$ - матроид с носителем $X$ и $M_2$ - матроид с носителем $Y$. Построим новый матроид, назовем носителем объединение $X \cup Y$, независимыми объявим множества, которые являются объединением независимого из $M_1$ и независимого из $M_2$. Докажите, что прямая сумма матроидов является матридом.
# Представьте разноцветный матроид в виде прямой суммы универсальных матроидов.
# Является ли алгоритм Прима вариантом алгоритма Радо-Эдмондса?
# Являются ли паросочетания в полном графе семейством независимых множеств некоторого матроида?
# Рассмотрим кратчайшие пути из $s$ в $t$ в неориентированном невзвешенном графе. Назовем множество ребер независимым, если оно лежит на некотором кратчайшем пути. Образует ли эта конструкция семейство независимых множеств некоторого матроида?
# Будем называть предматроидом пару $\langle X, I \rangle$, для которой выполнены аксиомы нетривиальности ($\varnothing \in I$) и наследования независимости ($A \subset B$, $B \in I$, тогда $A \in I$). Пусть в предматроиде для любой весовой функции верно работает жадный алгоритм Радо-Эдмондса. Докажите, что такой предматроид является матроидом.
# Пусть $M$ - предматроид. Как и в матроиде будем называть базой множества максимальное по включению подмножество из $I$. Докажите, что если для каждого множества $A$ все его базы равномощны, то $M$ - матроид.
# Для каких универсальных матроидов существует изоморфный ему матричный матроид?
# Проекция матроида. Пусть $M = \langle X, I \rangle$ - матроид, $f : X \to Y$ - произвольная функция. Обратите внимание, что нет необходимости, чтобы $f$ была инъекцией или сюрьекцией. Построим конструкцию $f(M)$ как пару из носителя $Y$ и семейства множеств $f(I) = \{ f(A) \,|\, A \in I\}$. Докажите, что $f(M)$ является матроидом.
# Будем называть два элемента $x$ и $y$ матроида параллельными, если пара $\{x, y\}$ образует цикл. Докажите, что если $A$ независимо $x \in A$, а $x$ и $y$ параллельны, то $A\setminus x\cup y$ также независимо.
# Дайте альтернативное определение параллельных элементов на языке баз.
# Докажите, что отношение "быть параллельными" является транзитивным.
