Спектральная теория графов

Санкт-Петербург, весна 2018

Описание

UPD! ЧТОБЫ ПОЛУЧИТЬ ОЦЕНКУ ЗА КУРС НАДО ДОГОВОРИТЬСЯ СО МНОЙ И С А. КУЛИКОВЫМ. если Вы решите все (два) домашних задания целиком, это гарантирует Вам 5, если каждое наполовину --- то три.

Спектральная теория графов позволяет судить о свойствах графа по свойствам связанных с ним матриц (смежности, лапласиана, инцидентности). Дело в том, что у неориентированного графа матрица смежности и лапласиан симметричны, то есть для них существуют полные наборы вещественных собственных чисел.

Мы обсудим наиболее известные математические (сильно регулярные графы, количество остовных деревьев, экспандеры, связь с паросочетаниями) и компьютерные (рисование планарных графов, Google page rank, экспандеры) сюжеты.

Преподаватели

Список лекций

Лекция 1. Введение

Матрицы, ассоциированные с графом.

Лекция 2. Теорема Куранта -- Фишера, раскраски графов

Появляется основной используемый для оценки через собственные значения инструмент --- теорема Куранта -- Фишера. Далее мы доказываем усиление теоремы Брукса (теорема Вилфа) и оценку Хоффмана на число независимости графа.

Лекция 3. Вокруг формулы Хоффмана

Мы рассматриваем различные обобщения формулы Хоффмана --- нижнюю оценку на число ребер в множестве фиксированного размера, изопериметрическое неравенство.

Лекция 4. Кнезеровский граф.

Мы рассматриваем граф Кнезера, приводим доказательство Ловаса теоремы Эрдёша -- Ко -- Радо и готовимся к великим свершениям