题目：Tutte polynomial of an Eulerian graph
William Tutte is one of the founders of the modern graph theory. For every undirected graph G, Tutte de_ned 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-_ring game on this digraph, K_evin 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 PD;v(y) and QD;v(y), which are de_ned on the set of v-sink subgaphs and the set of acyclic v-sink subgaphs of D, respectively. We _nd that these two polynomials have very good invariance properties. In particular, these two polynomials are independent of the choice of the vertex v. Moreover, we will introduce two polynomials ~ PD;v(y) and ~QD;v(y), which are de_ned on the set of v-source subgaphs and the set of acyclic v-source subgaphs of D, respectively. We prove that PD;v(y) = ~ PD;v(y) and QD;v(y) = ~QD;v(y). For these reason, we simply write PD;v(y) and ~ PD;v(y) as PD(y), and QD;v(y) and ~Q D;v(y) as QD(y). Thus, the polynomials PD(y) and QD(y) depends only on the Eulerian digraph D. Furthermore, PD(y) can be viewed as a generalization of the partial Tutte polynomial TG(1; y) on an undirected graph G.
报告人介绍： 马俊, 2006年从上海交通大学数学系博士毕业， 后2006年至2009年，在台北中央研究院数学所从事过为期三年的博士后研究工作，2010年到上海交通大学工作, 现为上海交通大学数学科学学院副教授, 主要研究组合设计与编码、代数组合、计数组合学及其应用等方面的问题。最近几年，研究主要围绕在图上的多项式(尤其是图的Tutte多项式)的性质、计算、推广，及其与图上其他相关组合结构之间的关系,如与图的生成树、与图上泊车函数和与图上沙堆模型的关系上, 得到了一系列的成果。