Consider a length-n sequencexover aq-ary alphabet. The fixed-length Levenshtein ballLt(x) of radius t contains all length-nq-ary sequences that can be derived fromxby performingtdeletions followed bytinsertions. Recent studies have successfully characterized fixed-length Levenshtein balls in the context of radiust= 1. These works have derived explicit formulas for various quantities, including the exact size of the balls, extremal bounds (minimum and maximum sizes), as well as expected sizes and their concentration properties. However, the general case involving an arbitrary number oftdeletions andtinsertions (t> 1) remains largely uninvestigated. This work systematically examines fixed-length Levenshtein balls with multiple deletions and insertions, focusing specifically onfixed-length burst Levenshtein balls, where deletions occur consecutively, as do insertions. We provide solutions for explicit cardinality formulas, extremal bounds (minimum and maximum sizes), expected size, and concentration properties surrounding the expected value.

Motivated by applications in modern storage devices such as DNA storage and racetrack memories, we study the sequence reconstruction problem which involves two important issues. One is determining the maximum intersection size between two error balls. The other is designing reconstruction codes in which each transmitted sequence can be reconstructed from a given number of noisy reads with redundancy as small as possible. In this paper, we focus on channels that introduce single-burst-insertion/deletion error. We fully determine the maximum intersection size between two burst-insertion/deletion balls for both fixed-length and variable-length models. Then we characterize a pair of sequences when their burst-insertion/deletion balls have intersection of a certain size. Using these characterizations, we design reconstruction codes for all values$N$of the number of noisy reads and analyze their lower bounds. In addition, we extend our results to the burst-edit channel.

Motivated by emerging applications in coding for molecular data storage, much attention has been paid to the intersecting set discrepancy problem, which aims to design a large family of subsets of a common labeled ground set with bounded pairwise intersection and bounded set discrepancy. In this paper, we study the maximum size of such families of$k$-subsets with$v$elements ground set,$t$-bounded intersections, and zero or one discrepancy, called as balanced$(t,k,v)$set codes. By turning this problem into a graph edge-labeling problem, we are able to determine the maximum size of codes when$k=3,4$and$t=2,3$for a given ground set. The constructions are based on combinatorial designs, matching decompositions and edge coloring schemes. Furthermore, we improve the upper bound for balanced$(t,k,v)$set codes with all integers$2\leq t < k < v$. By the powerful probabilistic argument–Kahn’s Theorem, we show that the improved upper bound for any fixed integers$2 \leq t < k$is asymptotically tight when$v$goes to infinity.