Числа Рамсея | Видеолекции Физтеха: Лекторий МФТИ - видеолекции по физике, математике, биологии, биоинформатике, информатике и другим дисциплинам

Видео не может быть загружено из-за проблем с интернет-соединением или проблем на сервере. Или формат файла не поддерживается вашим браузером.

Числа Рамсея

18-я лекция из курса: Дискретный анализ

Видео закончится через

NaN:NaN

00:00

00:00

Следующая секция начнется через 15:40

Теорема Франкла-Уилсона о нижней оценке R(s,s) (продолжение)

Формулировка результатов, полученных на прошлой лекции. Продолжение доказательства - выражение количества вершин через s.

15:40

Следующая секция начнется через 15:40

Теорема Франкла-Уилсона о нижней оценке R(s,s) (продолжение)

Обсуждение, почему теорема Франка-Уилсона справедлива для любого s.

24:07

Следующая секция начнется через 15:40

Теорема Брукса о верхней оценке хроматического числа графа. Теорема о верхней оценке хроматического числа n-однородного гиперграфа через его максимальную степень

Формулировка теоремы Брукса о верхней оценке хроматического числа графа через максимальную степень его вершин. Формулировка теоремы о верхней оценке хроматического числа n-однородного гиперграфа через максимальную степень его вершин. Доказательство с помощью локальной леммы Ловаса, получение явного выражения для верхней оценки. Следствие для n=2.

38:54

Следующая секция начнется через 15:40

Число Рамсея R_k(l_1, ..., l_r). Теорема о верхней оценке R_k(l_1, ..., l_r)

Определение числа Рамсея R_k(l_1, ..., l_r). Формулировка теоремы о верхней оценке R_k(l_1, ..., l_r), идея доказательства этой теоремы. Величина этой оценки для R_3(s,t).

52:38

Следующая секция начнется через 15:40

Теорема о нижней оценке R_3(s,s). Следствие из этой теоремы

Формулировка теоремы о нижней оценке R_3(s,s). Следствие из этой теоремы о нижней оценке R_3(s,s).

58:05

Следующая секция начнется через 15:40

Двудольные числа Рамсея b(s,t). Теорема о нижней оценке b(s,s). Теорема о верхней оценке b(s,s)

Определение двудольных чисел Рамсея. Формулировка теоремы о нижней оценке b(s,s). Доказательство этой теоремы. Формулировка теоремы о верхней оценке b(s,s).

00:00

00:00

00:00

Следующая секция начнется через 15:40

Теорема Франкла-Уилсона о нижней оценке R(s,s) (продолжение)

Формулировка результатов, полученных на прошлой лекции. Продолжение доказательства - выражение количества вершин через s.

15:40

Следующая секция начнется через 15:40

Теорема Франкла-Уилсона о нижней оценке R(s,s) (продолжение)

Обсуждение, почему теорема Франка-Уилсона справедлива для любого s.

24:07

Следующая секция начнется через 15:40

Теорема Брукса о верхней оценке хроматического числа графа. Теорема о верхней оценке хроматического числа n-однородного гиперграфа через его максимальную степень

Формулировка теоремы Брукса о верхней оценке хроматического числа графа через максимальную степень его вершин. Формулировка теоремы о верхней оценке хроматического числа n-однородного гиперграфа через максимальную степень его вершин. Доказательство с помощью локальной леммы Ловаса, получение явного выражения для верхней оценки. Следствие для n=2.

38:54

Следующая секция начнется через 15:40

Число Рамсея R_k(l_1, ..., l_r). Теорема о верхней оценке R_k(l_1, ..., l_r)

Определение числа Рамсея R_k(l_1, ..., l_r). Формулировка теоремы о верхней оценке R_k(l_1, ..., l_r), идея доказательства этой теоремы. Величина этой оценки для R_3(s,t).

52:38

Следующая секция начнется через 15:40

Теорема о нижней оценке R_3(s,s). Следствие из этой теоремы

Формулировка теоремы о нижней оценке R_3(s,s). Следствие из этой теоремы о нижней оценке R_3(s,s).

58:05

Следующая секция начнется через 15:40

Двудольные числа Рамсея b(s,t). Теорема о нижней оценке b(s,s). Теорема о верхней оценке b(s,s)

Определение двудольных чисел Рамсея. Формулировка теоремы о нижней оценке b(s,s). Доказательство этой теоремы. Формулировка теоремы о верхней оценке b(s,s).

Теорема Франка-Уилсона о нижней оценке R(s,s) (продолжение). Теорема Брукса о верхней оценке хроматического числа графа. Числа Рамсея. Двудольные числа Рамсея b(s,t), нижняя и верхняя оценка числа Рамсея b(s,s).

Лекторы

Райгородский Андрей Михайлович

доктор физико-математических наук, профессор МФТИ и МГУ

Доктор физико-математических наук, заведующий кафедрой дискретной математики ФИВТ, научный руководитель бакалавриата кафедры "Анализ данных", главный редактор журнала Moscow Journal of Combinatorics and Number Theory.

Конспекты

Следующая лекция

МАТЕМАТИКА01:09:55

Теорема о верхней оценке b(s,s)

19-я лекция из курса:

Дискретный анализ

Предыдущая лекция

МАТЕМАТИКА01:14:44

Теорема о нижней оценке R(3,t). Оценки R(s,s)

17-я лекция из курса:

Дискретный анализ

Московский физико-технический институт

Московский физико-технический институт (Физтех) – ведущий вуз России по подготовке высококвалифицированных специалистов по передовым направлениям науки и техники. Входит в топ 5 крупных рейтингов отечественных университетов. Отличительной чертой образовательного процесса МФТИ является система поиска и подготовки кадров – знаменитая «система Физтеха».

Скачайте наше мобильное приложение

iTunes

Google Play