学术报告
您现在的位置: 首页 > 科学研究 > 学术报告 > 正文

20190112 马俊 Tutte polynomial of an Eulerian graph

发布时间:2019-01-11 10:58    浏览次数:    来源:

题目:Tutte polynomial of an Eulerian graph
报告人: 马俊博士,上海交通大学
时间地点:2019/1/12(周六)10:00-11:00,数学院425
Abstract:
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 [1] and Swee Hong Chan [2] 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多项式)的性质、计算、推广,及其与图上其他相关组合结构之间的关系,如与图的生成树、与图上泊车函数和与图上沙堆模型的关系上, 得到了一系列的成果。

湖南大学版权所有©2017年    通讯地址:湖南省长沙市岳麓区麓山南路麓山门     邮编:410082     Email:xiaoban@hnu.edu.cn
域名备案信息:[www.hnu.edu.cn,www.hnu.cn/湘ICP备05000239号]      [hnu.cn 湘教QS3-200503-000481 hnu.edu.cn  湘教QS4-201312-010059]