Tutte Polynomial and Parking Function

Konheim and Weiss [2] introduced the concept of parking func-tions of length n in the study of the linear probes of random hashing function. Riordan [5] studied a relation of parking problems to ballot problems. The most notable result about parking functions is bijec-tions from the set of classical parking functions to the set of labeled trees on n+ 1 vertices. For every undirected graph, Tutte [6] defined a polynomial TG(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, TG(1, 1) is the number of spanning trees in G, TG(2, 1) is the number of spanning forests in G. As universality of graph language, Tutte polynomial contains several famous other specialisations from other sciences such as the Jones polynomial from knot theory and the partition functions of the Potts model from statistical physics. Recently, Postnikov and Shapiro [4] defined the G-parking functions of a graph. By considering a statistic wG(f) on G-parking func-tions, Plautz and Calderer [3] related G-parking functions and the Tutte polynomial TG(1, y) of G. In the bivariate expression of Tutte polynomial TG(x, y) defined by Tutte [6], the exponents of x and y are the number of internally active edges and the number of externally ac-tive edges in a spanning tree of G, respectively. Thus, the statistic wG(f) is equally distributed as the number of externally active edges in a spanning tree of G. Chebikin and Pylyavskyy [1] established a family of bijections from the set of G-parking functions to the set of spanning trees of G. Hence, one expects to get a new expression for the Tutte polynomial of a general connected graph G in terms of statistics of G-parking functions. In this talk, we introduce a bivariate expression for the Tutte polynomial in terms of statistics of G-parking functions