Guessing number is a relatively new concept on graphs defined in studying network coding and circuit complexity. In this talk, we will introduce it from two different approaches: one is based on a game and the other is related with statistical models on graphs. Due to the difficulty in exact computing, we are interested in its up bounds and lower bounds. To this end, we link it with the maximal number of vertex disjoint cycles and the minimal feedback edges set, two well known parameters on graphs. As an application, we obtain the bounds for shift graphs, a subclass of directed circulant graphs. (This is joint work with Peter Cameron and Soren Riis.)
I am a third year Ph.D student in Queen Mary, University of London, under the supervison of Dr. Soren Riis and Prof. Peter.J.Cameron. Before coming to London, I got my master degree in mathematics from Peking University (2004) and the first degree in Mechanics from Harbin Institute of Technology (2001). My main interest lies in computational complexity and combinatorics, as well as their connections with statistical mechanics, topology and group theory.