An Upper Bound on the Sizes of Multiset-Union-Free Families

Abstract

Let ${\mathcal{F}}_1$ and ${\mathcal{F}}_2$ be two families of subsets of an $n$-element set. We say that ${\mathcal{F}}_1$ and ${\mathcal{F}}_2$ are multiset-union-free if for any $A,B\in {\mathcal{F}}_1$ and $C,D\in {\mathcal{F}}_2$ the multisets $A\uplus C$ and $B\uplus D$ are different, unless both $A=B$ and $C=D$. We derive a new upper bound on the maximal sizes of multiset-union-free pairs, improving a result of Urbanke and Li.

arXiv commentA shorter ISIT conference version titled "VC-Dimension Based Outer Bound on the Zero-Error Capacity of the Binary Adder Channel" is available