题目：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多项式)的性质、计算、推广，及其与图上其他相关组合结构之间的关系,如与图的生成树、与图上泊车函数和与图上沙堆模型的关系上, 得到了一系列的成果。