Academic Report
Title: Some recent progresses in studies of the Tutte polynomial of a graph
Reporter: Researcher YE Yongnan (Institute of Mathematics, Taipei Academia Sinica)
Time: October 12, 2017 (Thursday) AM 10:00-11:00
Location: A#1101 room, Innovation Park Building
Contact: Prof. WANG Yi (tel: 84708351-8128)
Abstract: William Tutte is one of the founders of the modern graph. For every undirected graph, Tutte defineda 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 σ-cut tail and σ-cycle tail of T, which are generalizations of the conceptions of internally and externally activities, repectively, where σ 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. Ingeneral, 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(2,1) 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).
The brief introduction to the reporter: Prof. Ye was graduated from the Institute of Mathematics, Taiwan University in 1978, and got his master degree and Ph.D degree from Institute of Mathematics, New York State University Buffalo Division, respectively in 1983 and 1985. From 1985 to 1987, research at the Department of Information and Mathematics, the University of Quebec Montreal. He was a visiting scholar at Institute of Mathematics, MIT from 1991 to 1992, Department of Economics, Monash University at 1995 and Institute of Statistics, University of Berkeley at 1999. From1992 to 1994 he won the National Science Award for academic research; 2002 to 2005, the first prize of the National Science Council; 2009 to 2012 National Science Program Outstanding Program Research Award; 2011-2015 Central Research Institute of Academic Excellence Award.
