2015/08/10 by Yurii Burman, Burman, Yurii
Computer Science · Mathematics · #05C20 #05C50 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Matrix Theory and Algorithms #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1508.02245
openalex publication_date 2015/08/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The classical matrix-tree theorem was discovered by G.~Kirchhoff in 1847. It relates the principal minor of the Laplace (nxn)-matrix to a particular sum of monomials indexed by the set of trees with n vertices. The aim of this paper is to present a generalization of the (nonsymmetric) matrix-tree theorem containing no trees and essentially no matrices. Instead of trees we consider acyclic directed graphs with a prescribed set of sinks, and instead of determinant, a polynomial invariant of the matrix determined by directed graph such that any two vertices of the same connected component are mutually reacheable.