Tutte polynomial, G-parking function and sandpile
| 报告题目：Tutte polynomial, G-parking function and sandpile 报告人：马俊 博士 上海交通大学数学系 报告时间：2013年7月7日（星期日）下午16:00 报告地点： 数学搂二楼学术报告厅 欢迎师生踊跃参加！ Abstract: Generalizing the chromatic polynomial, Tutte proposed in 1954 a two-variable polynomial 12TG(x,y)' type="#_x0000_t75"> for any graph G that came to be named after him and turns out to be a very important concept in mathematics and in science. The polynomial contains information about how the graph is connected. For example, 12TG(1,1)' type="#_x0000_t75"> is the number of spanning trees in G and 12TG(2,1)' type="#_x0000_t75"> is the number of spanning forests in G. The polynomial appears in many places. For example, Jones polynomial from knot theory and the partition functions of the Potts model from statistical physics are both closely related to Tutte polynomial. Many combinatorial interpretations for Tutte polynomial were made from various viewpoints. Parking function is a famous combinatorial model and has close relations with Tutte polynomial. Konheim and Weiss introduced the concept of parking functions in the study of the linear probes of random hashing function. Postnikov and Shapiro introduced G-parking functions in the study of certain quotients of the polynomial ring. In this talk, we will discuss Tutte polynomial and relate it to some combinatorial models, such as G-parking functions, sand-piles.
|