Polynomials of graphs and matroids

Project Number
RI 2/12 DFM

Project Duration
April 2013 - April 2016

Status
Completed

Abstract
Graph Theory is a branch of Mathematics which studies configurations involving a set of nodes interconnected by edges (called graphs). The applications of graph theory can be found not only in other branches of mathematics, but also in scientific disciplines such as engineering, computer science, operational research, management sciences and the life sciences. The partition function of a graph is a polynomial defined on a graph in which each edge is assigned a weight. The complex zeros of partition functions play an important role in statistical mechanics, as the real limit points of these zeros determine the possible points of physical phase transitions. The Tutte polynomial is a special case of the partition function, when all weights are a constant. Note that Tutte polynomials of graphs can be extended Tutte polynomials for matroids. The chromatic polynomial and flow polynomial are two special cases of Tutte polynomials. A lot of work on these two polynomials focuses on finding the locations of their zeros. One of the reasons is that this problem is also associated with the 4-colour theorem, one of the most famous conjectures in mathematics. In the past few years, especially during the period of our previous AcRf project MI 5/06 DFM (Dec 2006- Aug 2010), we have finished some research on finding the locations of the zeros of these polynomials and are on the cutting edge of this area. Our previous project is very successful (around 12 papers were published in international journals). We are now applying for another AcRf project so that we can continue to have support collaborative opportunities with experts from other universities with a view to achieving significant breakthroughs in this area. In addition, we are extending our work into the area of matroids, with much preliminary work and study already done by the proposed Principal Investigator.

Funding Source
NIE

Related Projects