主讲人:马俊 上海交通大学
时间:2019年7月3日15:00
地点:3号楼332
举办单位:数理学院
内容介绍:William Tutte is one of the founders of the modern graph theory. For every undirected graph G, Tutte defined a polynomial TG(x,y) in two variables which plays an important role in graph theory. It encodes information about subgraphs of $G$. For example, for a connected graph G, TG(1, 1) is the number of spanning trees of G, TG(2, 1) is the number of spanning forests of G, TG(1, 2) is the number of connected spanning subgraphs of G, TG(2, 2) is the number of spanning subgraphs of G. One has been looking for analogues of the Tutte polynomial for digraphs for a long time. Recently, considering an Eulerian digraph and a Chip-firing game on this digraph, Kevin Perrot and Swee Hong Chan gave generalizations of the partial Tutte polynomial TG(1,y) from the point of view of recurrent congurations of the Chip-ring game. In this talk, let D be an weak-connected Eulerian digraph and v be a vertex of D. We will introduce two polynomials and , which are defined on the set of v-sink subgaphs and the set of acyclic v-sink subgaphs of D, respectively. We find that these two polynomials have very good invariance properties. In particular, these two polynomials are independent of the choice of the vertex v.