Редактирование: Список заданий по ДМ 2к 2020 осень

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 158: Строка 158:
 
# Докажите, что для любого $\varepsilon > 0$ в $G(n, \frac 12)$ матожидание количества независимых множеств размера $(2 - \varepsilon) \log_2 n$ стремится к $\infty$.
 
# Докажите, что для любого $\varepsilon > 0$ в $G(n, \frac 12)$ матожидание количества независимых множеств размера $(2 - \varepsilon) \log_2 n$ стремится к $\infty$.
 
# Докажите, что для любого $\varepsilon > 0$ в $G(n, \frac 12)$ а.п.н. существует независимое множество размера $(2 - \varepsilon) \log_2 n$.
 
# Докажите, что для любого $\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 базами. Укажите множество циклов этого матроида.
 
# Постройте матроид с 4 элементами и 5 базами. Укажите множество циклов этого матроида.
 
# Постройте матроид с 5 элементами и 12 базами.
 
# Постройте матроид с 5 элементами и 12 базами.

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)