報告題目：圖的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 TG(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, 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$. At last, we will discuss combinatorial interpretations of TG(1+p, -1)$ and TG(-1, 1).
報告人簡介：
葉永南，臺灣中研院數學研究所研究員，1985年在美國紐約州立大學水牛城分部獲得博士學位，1987年7月返臺擔任中央研究院數學所副研究員，1991年1月晉升為研究員迄今。曾任加拿大魁北克大學蒙特婁分部資訊與數學系研究學者，麻省理工學院數學系、柏克萊加州大學統計系和澳洲Monash大學經濟系訪問學者。學術研究除了數學之外，還涉及物理化學、統計、經濟等多個領域。曾任臺灣數學推動中心主任，中研院數學所副所長，多次獲得臺灣中研院傑出研究獎，國科會傑出研究獎，國科會傑出研究計劃獎。已發表的論文有百餘篇，組合論國際頂級雜誌JCTA曾出版專門文章介紹Yeh-species,這個由葉永南研究員名字命名的領域，現在這一方向的研究仍然在不斷深入。目前，葉永南研究員的研究主要在圖的Tutte多項式及其相關組合結構、計數組合學中uniform partitions等方面。