\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Eugene M. Luks and Amitabha Roy }
%
%
\medskip
\noindent
%
%
{\bf Combinatorics of Singly-Repairable Families}
%
%
\vskip 5mm
\noindent
%
%
%
%
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: 

\item{(i)} if any bit of $u$ is
changed (from $0$ to $1$ or vice versa), the new vector does not
belong to ${\cal F}$ 

\item{(ii)} there is a unique choice of a different
bit that can then be changed to give another vector $\not= 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 \emph{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.

\bye

.
