Михаил Николаевич Вялый

Пфаффианы и перечисление паросочетаний

М.Н.Вялый планирует провести 4 занятия.

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

Речь пойдет в основном про многочлены, известные как детерминант, пфаффиан и перманент. В качестве побочной темы планируется обсудить сложность вычисления этих многочленов. Будет сделана попытка объяснить, почему вычисление детерминанта — простая задача, а вычисление перманента — сложная. Будет также объяснено, почему подсчет числа паросочетаний в графе значительно упрощается, если граф можно нарисовать на плоскости без самопересечений.

Знание линейной алгебры сильно упрощает понимание этого курса, но не является обязательным для понимания почти всех затрагиваемых в нем вопросов.

Записки курса см. здесь

Organization Committee e-mail:
dubna@mccme.ru