Combinatorics of singly-repairable families

Eugene M. Luks ; Amitabha Roy

The electronic journal of combinatorics, Tome 12 (2005)

Résumé

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.

Détail

DOI : 10.37236/1956

Classification : 05D05, 68R05, 94B65
Mots-clés : Error correcting codes, Fault-tolerant solution of scheduling problems