A generalized matrix-tree theorem for Pfaffian pairs
Date
Friday, November 15, 2019 11:00 - 12:00
Speaker
Taihei Oki (University of Tokyo)
Location
Mondi Seminar Room 3, Central Building
Series
Seminar/Talk
Tags
Mathematics and CS Seminar
Host
Vladimir Kolmogorov
Contact
The celebrated matrix-tree theorem, which is to count the number of spanning trees in graphs, is a theorem essentially for counting bases of general regular matroids. Webb (2004) introduced the notion of Pfaffian pairs as a pair of regular matroids for which counting of their common bases is tractable through the matrix-tree theorem. This class can represent a bunch of important combinatorial structures, such as spanning trees, arborescences, Euler tours in 4-regular digraphs and perfect matchings in K_{3,3}-free bipartite graphs. In this talk, as an application of the matrix-tree theorem for Pfaffian pairs, we present deterministic polynomial-time algorithms for several counting problems: exact, group-labeled and weighted problem settings.