Guessing numbers based on network routing capacity

Abstract

In this thesis, a new method of studying problems in network information flow is introduced. This is established by developing on the relatively new concept of guessing numbers, which is related to network coding, and combining it with another technique known as fractional routing. The resultant guessing game, called a fractional guessing game, is a modification of the existing guessing game that incorporates the notion of fractional routing for multiple-unicast networks. It is essentially an intersection of two major areas of mathematics which allows further study into network flow problems, and the relationship between guessing numbers and the solvability of network flow problems. To illustrate this relationship, we construct a graph (the pentagon or 5-cycle) that has a non- integer guessing number, by using a guessing strategy which ensures a guessing number in the half-open interval (2, 2.5]. This is an application of the link between guessing numbers on graphs and the solvability of their related networks. It is shown that the fractional guessing number of an example graph is higher than the guessing number computed using the existing linear approach. This guessing number is also dependent on the size of the alphabet from which the messages are constructed, answering an open question from the literature relating to the possibility of such a dependency. Finally, the extension of the method to include techniques of both routing capacity and network coding is discussed.