15. Nov 2019

A generalized matrix-tree theorem for Pfaffian pairs

Datum: 15. November 2019 | 11:00 – 12:00
Sprecher: Taihei Oki, University of Tokyo
Veranstaltungsort: Mondi Seminar Room 3, Central Building

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.