Multichannel communication and graph vertex labeling problems

One way of dealing with the rising volume of communication over media with limited bandwidth is to break up the data into pieces. This approach is currently used in various settings such as packet switched networks, various multimedia protocols, and wireless and mobile computing. In the particular setting we investigate, the communication medium is considered unreliable, and in case of failure, the information sent over it can be corrupted, lost, or delayed to the point of being rendered useless. The goal is to design an encoding scheme to break the information in a way that, in case of communication failure, minimizes the error after reassembly. This question was posed in an information theoretical context as the Multiple Description problem in 1979. It is a generalization of Shannon's classical problem of source coding subject to fidelity criterion. Previously, there have been no optimal constructive results, moreover, there have been no constructive results for encoding into more than three pieces.; Depending on the type of data, error measure, and type of failure, the problem of designing these encoding schemes is equivalent to several classical problems in graph theory. For example, no-redundancy encodings that minimize maximum absolute error for complete loss of data correspond to the problem of bandwidth optimization of Hamming graphs (Cartesian products of cliques). The graph problem has been open since the 1960s. In this thesis, we demonstrate lower bounds and a nearly optimal solution to this problem. Using techniques developed for this solution, we give an algorithm for the wirelength optimization problem of grid graphs (products of paths) of arbitrary dimensions. This is the first constructive result for the product of more than two paths. In the communications setting, this problem is equivalent to designing no-redundancy encodings that minimize average error of a distance-1 type of medium failure. Similar techniques solved an unrelated graph edge isoperimetric problem. In addition, extending the algorithm to allow redundancy in the encoding improved the only previously known constructive result.