标题:The guessing number
演讲人: Taoyang Wu Queen Mary, University of London
时间: 2007-06-11 10:00-2007-06-11 11:00
地点:FIT Building 4-603, Tsinghua University

内容:

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.