Domination Mappings into the Hamming Ball: Existence, Constructions, and Algorithms

Abstract

The Hamming ball of radius $w$ in $\{0,1{\}}^n$ is the set $\mathcal{B}(n,w)$ of all binary words of length $n$ and Hamming weight at most $w$. We consider injective mappings $\phi :\{0,1{\}}^m\to \mathcal{B}(n,w)$ with the following domination property: every position $j\in [n]$ is dominated by some position $i\in [m]$, in the sense that "switching off" position $i$ in $x\in \{0,1{\}}^m$ necessarily switches off position $j$ in its image $\phi (x)$. This property may be described more precisely in terms of a bipartite \emph{domination graph} $G=([m]\cup [n],E)$ with no isolated vertices, for all $(i,j)\in E$ and all $x\in \{0,1{\}}^m$, we require that $x_i=0$ implies $y_j=0$, where $y=\phi (x)$. Although such domination mappings recently found applications in the context of coding for high-performance interconnects, to the best of our knowledge, they were not previously studied. In this paper, we begin with simple necessary conditions for the existence of an $(m,n,w)$-domination mapping $\phi :\{0,1{\}}^m\to \mathcal{B}(n,w)$. We then provide several explicit constructions of such mappings, which show that the necessary conditions are also sufficient when $w=1$, when $w=2$ and $m$ is odd, or when $m\le 3w$. One of our main results herein is a proof that the trivial necessary condition $|\mathcal{B}(n,w)|\ge 2^m$ for the existence of an injection is, in fact, sufficient for the existence of an $(m,n,w)$-domination mapping whenever $m$ is sufficiently large. We also present a polynomial-time algorithm that, given any $m$, $n$, and $w$, determines whether an $(m,n,w)$-domination mapping exists for a domination graph with an equitable degree distribution.