On the varshamov-tenengolts construction on binary strings

Ankur A. Kulkarni, Negar Kiyavash, R. Sreenivas

Research output: Contribution to journalArticle


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 n 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 n the smallest of these sets is within n2-n n2-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.

Original languageEnglish (US)
Pages (from-to)79-90
Number of pages12
JournalDiscrete Mathematics
Issue number1
StatePublished - Feb 28 2014


  • Coding theory
  • Deletion channel
  • Hypergraphs
  • Single-deletion-correcting codes
  • Varshamov-Tenengolts codes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'On the varshamov-tenengolts construction on binary strings'. Together they form a unique fingerprint.

  • Cite this