Combinatorics Seminar 2018


Speaker: Jun Ma (马俊), Shanghai Jiao Tong University

Date: Fri, Dec 07, 2018

Time: 13:30 - 14:30

Venue: Middle meeting room

Title: Tutte polynomial of an Eulerian graph

Abstract:

William Tutte is one of the founders of modern graph theory. For every undirected graph $G$, Tutte defined a two-variables polynomial $T_G(x,y)$ which plays an important role in graph theory. It 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$.

One has been looking for analogues of the Tutte polynomial for digraphs for a long time. Recently, considering the chip-firing game on an Eulerian digraph, Kévin Perrot, Trung Van Pham and Swee Hong Chan gave generalizations of the partial Tutte polynomial $T_G(1,y)$ from the point of view of recurrent configurations of the chip-firing game.

In this talk, we let $D$ be an weak-connected Eulerian digraph and $v$ be a vertex of $D$. We will introduce two polynomials $P_{D,v}(y)$ and $Q_{D,v}(y)$, which are defined on the set of $v$-sink subgaphs and the set of acyclic $v$-sink subgaphs of $D$, respectively. We find that these two polynomials have very good invariance properties. In particular, these two polynomials are independent of the choice of the vertex $v$. Moreover, we will introduce two polynomials $\tilde{P}_{D,v}(y)$ and $\tilde{Q}_{D,v}(y)$, which are defined on the set of $v$-source subgaphs and the set of acyclic $v$-source subgaphs of $D$, respectively. We prove that $P_{D,v}(y)=\tilde{P}_{D,v}(y)$ and $Q_{D,v}(y)=\tilde{Q}_{D,v}(y)$. For these reasons, we simply write $P_{D,v}(y)$ and $\tilde{P}_{D,v}(y)$ as $P_{D}(y)$, and $Q_{D,v}(y)$ and $\tilde{Q}_{D,v}(y)$ as $Q_{D}(y)$. Thus, the polynomials $P_{D}(y)$ and $Q_{D}(y)$ depend only on the Eulerian digraph $D$. Furthermore, $P_{D}(y)$ can be viewed as a generalization of the partial Tutte polynomial $T_G(1,y)$ on an undirected graph $G$.

References


Webmaster