Speaker : Ziqing Xiang (Institute of Mathematics, Academia Sinica)
Title : A matrix-tree theorem on mixed graphs
Time : 2020-09-11 (Fri) 15:00 -
Place : Seminar Room 617, Institute of Mathematics (NTU Campus)
Abstract: The matrix-tree theorem states that the number of spanning trees in a graph equals to the determinant of any cofactor of its Laplacian matrix. We will analyze the theorem carefully, and show that what the determinant really counts is the signed number of subgraphs with good orientations. With this interpretation, it is then straightforward to generalize the matrix-tree theorem to mixed graphs, that is graphs where directed edges, undirected edges, loops and parallel edges are allowed. At the end, we will show how to recover some of previously known generalizations of the matrix-tree theorem from this mixed graph version.