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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 167: Строка 167:
 
# Рассмотрим случайный двудольный $G(n, n, p)$, пусть $p = o(\frac{\log n}{n})$. Докажите, что $G$ а.п.н. не содержит полного паросочетание. Указание: используйте лемму Холла.
 
# Рассмотрим случайный двудольный $G(n, n, p)$, пусть $p = o(\frac{\log n}{n})$. Докажите, что $G$ а.п.н. не содержит полного паросочетание. Указание: используйте лемму Холла.
 
# Рассмотрим случайный двудольный $G(n, n, p)$, пусть $p = \omega(\frac{\log n}{n})$. Докажите, что $G$ а.п.н. содержит полное паросочетание. Указание: используйте лемму Холла.
 
# Рассмотрим случайный двудольный $G(n, n, p)$, пусть $p = \omega(\frac{\log n}{n})$. Докажите, что $G$ а.п.н. содержит полное паросочетание. Указание: используйте лемму Холла.
# Указание: в этом и следующих заданиях используйте вероятностный метод. Если вероятность, что объект обладает некоторым свойством, больше 0, то существует объект с таким свойством. Если матожидание числа объектов с некоторым свойством больше 0, то существует объект с таким свойством. Число Рамсея $R(a, b)$ - величина, такая что граф, содержащий хотя бы $R(a, b)$ вершин обязательно содержит или клику размера $a$ или независимое множество размера $b$. Оцените сверху вероятность, что граф из $G(n, \frac 12)$ содержит клику размера $k$ или независимое множество размера $k$. Сделайте вывод о нижней границе на число Рамсея: $R(k, k) \ge 2^{k/2-1}$.
+
# Указание: в этом и следующих заданиях используйте вероятностный метод. Если вероятность, что объект обладает некоторым свойством, больше 0, то существует объект с таким свойством. Если матожидание числа объектов с некоторым свойством больше 0, то существует объект с таким свойством. Число Рамсея $R(a, b)$ - величина, такая что граф, содержащий хотя бы $R(a, b)$ вершин обязательно содержит или клику размера $a$ или независимое множество размера $b$. Оцените сверху вероятность, что граф из $G(n, \frac 12)$ содержит клику размера $k$ или независимое множество размера $k$. Сделайте вывод о нижней границе на число Рамсея: $R(k, k) \ge 2^{k/2}-1$.
 
# Докажите, что существует турнир, в котором как минимум $\frac {n!}{2^{n-1}}$ гамильтоновых путей.
 
# Докажите, что существует турнир, в котором как минимум $\frac {n!}{2^{n-1}}$ гамильтоновых путей.
 
# Докажите, что любой граф с $n$ вершинами и $m$ ребрами содержит двудольный подграф с как минимум $\frac m2$ ребрами.
 
# Докажите, что любой граф с $n$ вершинами и $m$ ребрами содержит двудольный подграф с как минимум $\frac m2$ ребрами.

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

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

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