Экстремальная комбинаторика 2.Графы Келли и спектральные методы в комбинаторике

Лектор: Андрей Борисович Купавсикй

00:00:00 - Введение и обзор тем
00:01:31 - Формулировка теоремы Крускала
00:03:22 - Применение теоремы к регулярным графам
00:04:11 - Методы доказательства
00:06:15 - Преобразование семейств множеств
00:10:45 - Преобразование в симплициальный комплекс
00:11:48 - Монотонность и экстремальные задачи
00:12:49 - Введение в частичные порядки
00:13:29 - Операция, сохраняющая размер
00:14:21 - Свойства монотонных семейств
00:15:57 - Операция сдвига
00:17:57 - Коммутативность операций
00:20:06 - Индукционное доказательство
00:22:18 - Анализ тени и сдвигов
00:24:22 - Сценарии мощности
00:24:54 - Введение в доказательство
00:26:16 - Анализ множеств
00:27:29 - Противоречие
00:29:01 - Личные воспоминания
00:30:29 - Завершение доказательства
00:31:13 - Гиперкубы и неравенства
00:31:28 - Минимизация тени
00:33:36 - Сложность функции
00:34:31 - Результаты о стабильности
00:35:24 - Рёберная граница
00:38:26 - Неравенство для средней степени
00:41:07 - Доказательство по индукции
00:46:52 - Перенормировка и применение неравенства
00:49:12 - Неравенство Йенсена
00:53:13 - Введение в теорию графов
00:55:01 - Матрицы смежности и лапласиан
00:57:43 - Спектр лапласиана
01:00:07 - Связь между спектром и экспансией
01:03:21 - Дисперсия и разложение вектора
01:07:31 - Введение в коэффициенты и дисперсию
01:07:59 - Интерпретации через базис и лапласиан
01:08:56 - Характеристический вектор и его свойства
01:10:07 - Оценка суммы через собственные значения
01:10:59 - Неравенство Пуанкаре
01:12:46 - Глобальная дисперсия характеристической функции
01:14:10 - Нормировка и оценка дисперсии
01:16:02 - Сравнение произвольного и полного графа
01:19:06 - Применение к гиперкубу
01:22:38 - Матрица смежности и собственные вектора
01:24:42 - Введение в обозначения
01:25:55 - Применение матрицы смежности
01:27:10 - Мультипликативная функция
01:29:11 - Векторы и вершины графа
01:35:11 - Собственные векторы и значения
01:37:14 - Спектральная история
01:38:04 - Заключение

Оператор: Тучков Артём
Монтажер: Тучков Артём

Видео Экстремальная комбинаторика 2.Графы Келли и спектральные методы в комбинаторике канала Лекторий ФПМИ