On the Varshamov–Tenengolts construction on binary strings

This paper is motivated by the problem of finding the largest single-deletion-correcting code for binary strings. The Varshamov–Tenengolts construction classifies binary strings into non-overlapping sets, the largest set of these is asymptotically the largest single-deletion-correcting code. However despite the asymptotic optimality little is known about the quality of the construction as a function of the string length. We show that these sets are also responsible for the (near) solution of several combinatorial problems on a certain hypergraph. Furthermore our results are valid for any string length. We show that the sets collectively solve strong vertex coloring and edge coloring on the hypergraph exactly. For any string length nn we show that the largest of these sets is within n+1n−1 of optimal matching on the hypergraph, which also corresponds to the largest single-deletion-correcting code. Moreover, we show for any nn the smallest of these sets is within n2−nn2−3n+4−42n of the smallest cover of this hypergraph and that each of these sets is a perfect matching. We then obtain similar results on the dual of this hypergraph.