Explicit Edit Codes via Multicoloring

For any fixed integers q≥2 and t≥1, we construct explicit q-ary codes of length n that correct any combination of at most t insertions, deletions, and substitutions, with redundancy at most 2tlogq n+Oq,t(loglog n) q-ary symbols. This matches the leading redundancy term of Levenshtein's classical existential bound. Building on the standard graph-coloring approach, we use a prime-based multicoloring of the edit-confusion graph to assign multiple colors to each q-ary word of length $m