Balanced Set Codes With Small Intersections

摘要

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 $2leq 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.