Upcoming Talks

Ist logo

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: Mathematics and CS Seminar
Host: Vladimir Kolmogorov

Abstract:

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.
Qr image
Download ICS Download invitation
Back to eventlist