City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

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

What: Lecture
When: Sunday, 18 March 2018, 13:00–14:30
Where: ПОМИ РАН

Description

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

Video