Gilbert-Varshamov-like lower bounds for deletion-correcting codes

The development of good codes which are capable of correcting more than a single deletion remains an elusive task. Recent papers, such as that by Kulkarni and Kiyavash [3], instead focus on the more tractable problem of deriving upper bounds on the cardinalities of such codes. In the present work, we develop Gilbert-Varshamov-type lower bounds on the cardinalities of deletion-correcting codes. Our approach is based on the application of results from extremal graph theory. We give several bounds for the cases of binary and non-binary single- and multiple-error correcting codes. We introduce a bound that is, to the best of our knowledge, the strongest existing lower bound on the sizes of deletion-correcting codes. Our work also reveals some structural properties of the underlying Levenshtein graph.