Изменения
Нет описания правки
# Докажите, что пересечение всех максимальных по включению барьеров $G$ равно $A(G)$.
# Лапой называется индуцированный подграф $K_{1, 3}$ - вершина (центр лапы) и три её соседа, не связанные между собой. Докажите, что если $B$ - минимальный по включению барьер $G$, то каждая вершина $B$ - центр лапы в $G$.
# Докажите, что если связный граф $G$ содержит четное число вершин и не содержит лапы, то он содержит совершенное паросочетание (Теорема Сумнера-Лас Вергнаса).# Найдите математическое ожидание степени вершины в биномиальной модели $G(n, p)$.# Найдите вероятность, что граф в равномерной модели $G(n, m)$ является деревом ($m = n - 1$).# Найдите вероятность, что граф в биномиальной модели $G(n, p)$ является деревом.# Найдите вероятность, что граф в равномерной модели $G(n, m)$ является гамильтоновым циклом ($m = n$).# Найдите вероятность, что граф в биномиальной модели $G(n, p)$ является гамильтоновым циклом.# Докажите, что если $p = o(\frac{1}{n^2})$, то случайный граф $G(n, p)$ а.п.н. не имеет ребер (а.п.н. = асимптотически почти наверное = с вероятностью, стремящейся к 1).# Докажите, что если $p = \omega(\frac{1}{n^2})$, то случайный граф $G(n, p)$ а.п.н. имеет хотя бы одно ребро.# Пусть $p = \frac{c}{n^2}$ для некоторого $c$. Найдите вероятность того, $G(n, p)$ имеет хотя бы одно ребро.# Оцените центральный биномиальный коэффициент ${2n \choose n}$ снизу величиной порядка $\frac {4^n}{\sqrt{n}}$. Указание: используйте формулу Стирлинга.# Рассмотрим число ребер $m$, такое что $m(n) \to \infty$ и ${n \choose 2} - m(n) \to \infty$, а также $p(n) = \frac {m(n)}{n \choose 2}$. Докажите, что вероятность того, что $G(n, p)$ имеет ровно $m$ ребер есть $\Omega(m^{-0.5})$.# Рассмотрим свойство $A$, а и такие же $m(n)$ и $p(n)$, как в предыдущей задаче. Докажите, что $P(G(n, m) \in A) \le C \sqrt{m} P(G(n, p) \in A)$.# Рассмотрим следующую модель генерации случайного графа. Сначала проведем каждое ребро с вероятностью $\frac 12$. Затем, для каждой пары вершин, между которыми не было проведено ребро на первом шаге, проведем ребро с вероятностью $\frac 13$. Как эта модель соотносится со стандартными моделями Эрдёша-Реньи?# Назовём свойство случайного графа монотонным, если оно сохраняется при добавлении ребра. Рассмотрим монотонное свойство $A$ при фиксированном размере графа $n$. Докажите, что $P(G(n, p) \in A)$ возрастает при возрастании $p$.# Придумайте такое свойство, что вероятность, что $G(n, \frac 12)$ обладает этим свойством, стремится к $\frac 13$.# Пусть для некоторого свойства $A$ существует две функции $p_1(n)$ и $p_2(n)$, что для графа $G(n, p_1(n))$ свойство $A$ а.п.н. не выполняется, а для $G(n, p_2(n))$ свойство $A$ а.п.н. выполняется. Докажите, что существует функция $p'(n)$, что для случайного графа $G(n, p'(n))$ свойство $A$ выполняется с вероятностью, стремящейся к $\frac 12$.# Докажите, что $G(n, \frac {2\ln n}{n})$ а.п.н. не содержит изолированных вершин.# Рассмотрим модель случайного двудольного графа $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.# Выведите формулу вероятности того, что расстояние между фиксированными вершинами $u$ и $v$ больше двух.# Пусть $p = c \sqrt{ \frac {\ln n}{n}}$, $c > \sqrt{2}$. Покажите, что $G(n, p)$ а.п.н. имеет диаметр не больше 2.# Докажите, что $G(n, p)$ а.п.н имеет диаметр 2, если $p$ -- константа.# Докажите, что $G(n, p)$ а.п.н имеет диаметр 2, если $p = c \sqrt{ \frac {\ln n}{n}}$, $c > \sqrt{2}$.# Пусть $p = o(n^{-\frac 23})$. Докажите, что а.п.н. $G(n, p)$ не содержит $K_4$.# Пусть $p = \frac dn$. Докажите, что в $G(n, p)$ каждая вершина а.п.н. принадлежит не более, чем одному треугольнику.# Пусть $p = \omega(n)$ и $k$ -- константа. Покажите, что $G(n, p)$ а.п.н. содержит цикл длины $k$.# Покажите, что матожидание количества остовных деревьев у графа $G(n, \frac {2\ln n}{n})$ стремится к бесконечности. Можно ли это считать доказательством а.п.н. связности графа $G(n, \frac {2\ln n}n)$?# Докажите, что $G(n, \frac dn), d > 1$ а.п.н. содержит индуцированный путь длины $\sqrt{\log n}$. # Подберите $p(n)$ и приведите пример случайной величины $X$ в модели случайного графа $G(n, p)$, что $EX \to \infty$, но $\mathcal{P}(X = 0) \nrightarrow 0$.
