Multiset Deletion Codes: Cyclic Constructions, Bounds, and Exact Results
We study deletion-correcting codes in the space of length-$n$ multisets over a $q$-ary alphabet. We present an explicit cyclic Sidon-type construction for arbitrary alphabet size $q$ and deletion radius $t$, defined by a single congruence modulo $t(t+1)^{q-2}+1$. The construction has redundancy at most $\log_q(t(t+1)^{q-2}+1)$ and...