Upper bounds for deletion correcting codes

Abstract

The world can’t keep up with its own data and therefore needs new ways to store it. Research is being done into new types of experimental data storage like DNA sampling or racetrack memory, which could completely revolutionize the way storage works. However, such storage media are prone to certain type of errors like deletion errors where information is lost. Consequently, there has been a surge in interest in developing deletion correcting codes to address this challenge. We are interested in the maximal size of a code correcting up to a certain number of deletions. Nevertheless, constructing these codes can be quite intricate and therefore we are often limited to working with bounds.
In this thesis, we will study and evaluate upper bounds for these codes. We will compare bounds that were derived analytically to bounds that have been computed with the use of linear programs. We will compute upper bounds for 1-, 2- and 3-deletion correcting codes. Moreover, we will show how to compute these bounds with a linear program, by posing the problem of finding a largest deletion correcting code as finding the transversal number on a hypergraph. It will become clear that the bounds computed through linear programming are much stronger than any bound derived analytically.