报告题目：图的Tutte多项式近期研究进展

报告人：叶永南教授

讲座时间：2017年10月21日10:15-11:00

讲座地点：友谊校区国际会议中心第一会议室

邀请人：张胜贵

承办学院：理学院

联系人：陆由

联系电话：18202966680

报告简介：

William Tutte is one of the founders of the modern graph. For every undirected graph, Tutte defined a polynomial T_G(x,y) in two variables which plays an important role in graph theory. In this talk, we will introduce some recent progresses in studies of the Tutte polynomial of a graph.

In Tutte's original definitions, non-negative integers, called internal and external activities with respect to the arbitrary enumeration, are defined for each spanning tree, they serve as the indices of x and y in the product that is the corresponding term of Tutte polynomial. First, We will introduce the conceptions of \sigma-cut tail and \sigma-cycle tail of T, which are generalizations of the conceptions of internally and externally activities, repectively, where \sigma is a sequence on the edge set of G and T is a spanning tree of G. We will also discuss the conceptions of proper Tutte mapping and deletion-contraction mapping.

In 2004, Postnikov and Shapiro introduced the concept of G-parking functions in the study of certain quotients of the polynomial ring. The Tutte polynomial of the graph G can be expressed in terms of statistics of G-parking functions. Let ∆ be a nonsingular M-matrix. We will introduce ∆-parking functions which is a generalization of G-parking functions. We will introduce the abelian sandpile model and ∆-recurrent configurations. There is a simple bijection between ∆-parking functions and ∆-recurrent configurations. We will discuss the geometry of sandpile model.

In general, the Tutte polynomial encodes information about subgraphs of G. For example, for a connected graph G, T_G(1, 1) is the number of spanning trees of G, T_G(2, 1) is the number of spanning forests of G, T_G(1, 2) is the number of connected spanning subgraphs of G, T_G(2, 2) is the number of spanning subgraphs of $G$. At last, we will discuss combinatorial interpretations of T_G(1+p, -1)$ and T_G(-1, 1).

报告人简介：

叶永南，台湾中研院数学研究所研究员，1985年在美国纽约州立大学水牛城分部获得博士学位，1987年7月返台担任中央研究院数学所副研究员，1991年1月晋升为研究员迄今。曾任加拿大魁北克大学蒙特娄分部资讯与数学系研究学者，麻省理工学院数学系、柏克莱加州大学统计系和澳洲Monash大学经济系访问学者。学术研究除了数学之外，还涉及物理化学、统计、经济等多个领域。曾任台湾数学推动中心主任，中研院数学所副所长，多次获得台湾中研院杰出研究奖，国科会杰出研究奖，国科会杰出研究计划奖。已发表的论文有百余篇，组合论国际顶级杂志JCTA曾出版专门文章介绍Yeh-species,这个由叶永南研究员名字命名的领域，现在这一方向的研究仍然在不断深入。目前，叶永南研究员的研究主要在图的Tutte多项式及其相关组合结构、计数组合学中uniform partitions等方面。