|dc.contributor.author||Dang, Anh Nhat||
|dc.identifier.citation||Dang.A.N. 2015, Guessing Games on Undirected Graphs, Queen Mary University of London.||en_US
|dc.description.abstract||Guessing games for directed graphs were introduced by Riis for studying multiple unicast
network coding problems. In a guessing game, the players toss generalised die
and can see some of the other outcomes depending on the structure of an underlying
digraph. They later simultaneously guess the outcome of their own die. Their objective
is to find a strategy that maximises the probability that they all guess correctly.
The performance of the optimal strategy for a digraph is measured by the guessing
In general, the existence of an algorithm for computing guessing numbers of a graph
is unknown. In the case of undirected graphs, Christofides and Markstr om defined
a strategy that they conjectured to be optimal. One of the main results of this
thesis is a disproof of this conjecture. In particular, we illustrate an undirected
graph on 10 vertices having guessing number which is strictly larger than the lowerbound
provided by Christofides and Markstr om's method. Moreover, even in case
the undirected graph is triangle-free, we establish counter examples to this conjecture
based on combinatorial objects known as Steiner systems.
The main tool thus far for computing guessing numbers of graphs has been information
theoretic inequalities. Using this method, we are able to derive the guessing
numbers of new families of undirected graphs, which in general cannot be computed
directly using a computer. A new result of the thesis is that Shannon's information
inequalities, which work particularly well for a wide range of graph classes, are not
sufficient for computing the guessing number.
Another contribution of this thesis is a firm answer to the question concerning irreversible
guessing games. In particular, we construct a directed graph G with Shannon
upper-bound that is larger than the same bound obtained when we reverse all edges
Finally, we initialize a study on noisy guessing game, which is a generalization of
noiseless guessing game defined by Riis.
We pose a few more interesting questions, some of which we can answer and some
which we leave as open problems.
|dc.description.sponsorship||School of Electronic Engineering and Computer
|dc.publisher||Queen Mary University of London||en_US
|dc.title||Guessing Games on Undirected Graphs||en_US
|dc.rights.holder||The copyright of this thesis rests with the author and no quotation from it or information derived from it may be published without the prior written consent of the author||