Combinatorics of singly-repairable families (Q2583659): Difference between revisions

The set \({\mathcal F}\) of binary \(n\)-vectors is called a single-repairable family, if no two vectors are closer then Hamming distance two and for every vector \(f\in {\mathcal F}\) and any coordinate \(i\in \{1,\dots ,n\}\) there is another vector \(g\in {\mathcal F}\) such that \(d(f,g)=2\) and their \(i\)th coordinates are different. The paper constructs such families and proves tight lower and upper bounds for maximum families. The problem is arising in the context of fault-tolerant solutions of scheduling problems.