• Login
    JavaScript is disabled for your browser. Some features of this site may not work without it.
    Guessing Games on Undirected Graphs 
    •   QMRO Home
    • Queen Mary University of London Theses
    • Theses
    • Guessing Games on Undirected Graphs
    •   QMRO Home
    • Queen Mary University of London Theses
    • Theses
    • Guessing Games on Undirected Graphs
    ‌
    ‌

    Browse

    All of QMROCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects
    ‌
    ‌

    Administrators only

    Login
    ‌
    ‌

    Statistics

    Most Popular ItemsStatistics by CountryMost Popular Authors

    Guessing Games on Undirected Graphs

    View/Open
    Dang_Nhat_Anh_Final_PhD_221215.pdf (1.283Mb)
    Publisher
    Queen Mary University of London
    Metadata
    Show full item record
    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
    Authors
    Dang, Anh Nhat
    URI
    http://qmro.qmul.ac.uk/xmlui/handle/123456789/12790
    Collections
    • Theses [3371]
    Copyright statements
    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
    Twitter iconFollow QMUL on Twitter
    Twitter iconFollow QM Research
    Online on twitter
    Facebook iconLike us on Facebook
    • Site Map
    • Privacy and cookies
    • Disclaimer
    • Accessibility
    • Contacts
    • Intranet
    • Current students

    Modern Slavery Statement

    Queen Mary University of London
    Mile End Road
    London E1 4NS
    Tel: +44 (0)20 7882 5555

    © Queen Mary University of London.