dc.contributor.author Dang, Anh Nhat dc.date.accessioned 2016-06-10T11:02:19Z dc.date.available 2016-06-10T11:02:19Z dc.date.issued 2015-12-15 dc.date.submitted 2016-06-10T11:35:25.515Z dc.identifier.citation Dang.A.N. 2015, Guessing Games on Undirected Graphs, Queen Mary University of London. en_US dc.identifier.uri http://qmro.qmul.ac.uk/xmlui/handle/123456789/12790 dc.description PhD 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 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.sponsorship School of Electronic Engineering and Computer en_US Science, dc.language.iso en en_US dc.publisher Queen Mary University of London en_US dc.subject Mathematics en_US dc.title Guessing Games on Undirected Graphs en_US dc.type Thesis 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
﻿

### This item appears in the following Collection(s)

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