Noah Kravitz, Princeton University

Abstract

The deletion distance between two binary words of length n is the smallest k such that the words have a common subsequence of length n-k.  A set of binary words of length n is called a k-deletion code if every pair of distinct words has deletion distance greater than k, and it is natural to ask for the maximum size of such a code.  A classical result of Levenshtein shows that (for fixed k) this quantity is at least Omega_k(2^n/n^{2k}) and at most O_k(2^n/n^k).  We improve the lower bound to Omega_k(2^n logn/n^{2k}) by studying triangles in the associated "deletion graph".  Joint work with Noga Alon, Gabriela Bourla, Ben Graham, and Xiaoyu He.