東北大学 大学院情報科学研究科
純粋・応用数学研究センター

組合せ論セミナー

第74回(連続講演) 2016年2月2日 16:00〜17:30, 2月4日 15:00〜16:30

Yeong-Nan Yeh (Academia Sinica)「Tutte polynomials / Lattice paths and uniform partitions」

Lecture 1:「Tutte polynomials」(2/2)

William Tutte is one of the founders of modern graph theory. A brief introduction to William Tutte is presented by the following website:

https://uwaterloo.ca/combinatorics-and-optimization/about/professor-william-t-tutte

For every undirected graph, Tutte defined a polynomial T_G(x,y) in two variables which plays an important role in graph theory. This polynomial is called Tutte polynomial. It contains information about how the graph is connected. For example, T_G(1,1) is the number of spanning trees in G, T_G(2,1) is the number of spanning forests in G. As universality of graph language, Tutte polynomial contains several famous other specializations from other sciences such as the Jones polynomial from knot theory and the partition functions of the Potts model from statistical physics. In this talk, we will give an introduction of Tutte polynomials.

Lecture 2:「Lattice paths and uniform partitions」(2/4)

The classical Chung-Feller theorem gives a uniform partition of all n-Dyck paths in the plane. In this talk, we will introduce generalizations for the classical Chung-Feller theorem, discuss the functions of uniform-partition type and their combinatorial interpretations. Many uniform partitions of combinatorial structures are consequences of the cycle lemma. In this talk, we will introduce the generalizations of the cycle lemma.