Combinatorics of Singly-Repairable Families

Eugene M. Luks, Amitabha Roy

Abstract


A non-empty set ${\cal F}$ of $n$-bit vectors over alphabet $\{0,1\}$ is called singly repairable, if every vector $u \in {\cal F}$ satisfies the following conditions:

(i) if any bit of $u$ is changed (from $0$ to $1$ or vice versa), the new vector does not belong to ${\cal F}$
(ii) there is a unique choice of a different bit that can then be changed to give another vector $\neq u$ in ${\cal F}$.

Such families ${\cal F}$ exist only for even $n$ and we show that $2^{n/2} \leq |{\cal F}| \leq {2^{n+1} \over (n+2)}$. The lower bound is tight for all even $n$ and we show that the families of this size are unique under a natural notion of isomorphism (namely, translations and permutation of coordinates). We also construct families that achieve the upper bound when $n$ is of the form $2^m-2$. For general even $n$, we construct families of size at least $2^n/n$. Of particular interest are minimal singly-repairable families. We show that such families have size at most $2^n/n$ and we construct families achieving this upper bound when $n$ is a power of $2$. For general even $n$, we construct minimal families of size $\Omega(2^{n}/n^2)$. The study of these families was inspired by a computational scheduling problem.


Full Text: PDF