Guessing Games on Undirected Graphs
Publisher
Metadata
Show full item recordAbstract
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
number.
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
of G.
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.
5
Authors
Dang, Anh NhatCollections
- Theses [3822]