skip to content

The guessing number of a graph

Friday 27th June 2008 - 10:00 to 11:00
Center for Mathematical Sciences

The following game was introduced by Soren Riis, as an euqivalent form of a problem in information transfer. A group of people are given dices and each person throws the dice so that everyone else, can see the outcome, but nobody can see their own result. Next everybody has to guess their own results without communicating with the others, and the group wins the game if everybody guesses correctly.. The surprising fact is that the probability of a win in this game is independent of N.

In this talk I will discuss the extension of this game to general graphs, the graph describes whose results an individual can see, and how the fractional chromatic number and entropy inequalities can be used to find the exact win probability for a large class of graphs.

University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons