Комбинаторика покрытий домино

Задача о числе покрытий некоторой фигуры на квадратной сетке костяшками домино (или ромбами на треугольной сетке) – вариант задачи о подсчете совершенных паросочетаний в графе. Такая постановка имеет приложения и берет истоки в химии и статистической физике. Основная цель спецкурса – познакомить слушателей с методом гафнианов-пфаффианов подсчета паросочетаний. Метод был разработан голландским физиком П. Кастеляйном, который сосчитал число покрытий прямоугольной доски костяшками домино (1961) и затем обобщил метод решения на любые планарные графы (алгоритм FKT). Будет также рассмотрено другое приложение метода – концептуальный подсчет ограниченных плоских разбиений с различными типами симметрий, предпринятый Г. Купербергом (1994).

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