Skip to content

CSM

Seminar

The guessing number of a graph

Markstrom, K (Umea)
Friday 27 June 2008, 10:00-11:00

Meeting Room 3, CMS

Abstract

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.

Back to top ∧