Show simple item record

dc.contributor.authorDang, Anh Nhat
dc.identifier.citationDang.A.N. 2015, Guessing Games on Undirected Graphs, Queen Mary University of London.en_US
dc.description.abstractGuessing 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
dc.description.sponsorshipSchool of Electronic Engineering and Computer Science,en_US
dc.publisherQueen Mary University of Londonen_US
dc.titleGuessing Games on Undirected Graphsen_US
dc.rights.holderThe 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

Files in this item


This item appears in the following Collection(s)

  • Theses [3919]
    Theses Awarded by Queen Mary University of London

Show simple item record