On Sets of Boolean n-Vectors with All k-Projections Surjective
Given a set, S, of Boolean n-vectors, one can choose k of the n coordinate positions and consider the set of k-vectors which results by keeping only the designated k positions of each vector, i.e., from k-projecting S. In this paper, we study the question of finding sets S as small as possible such that every k-projection of S yields all the 2k possible k-vectors. We solve this problem constructively and almost optimally for k=2 and all n. For k≧3, the constructive solutions we describe are much larger than an O(k2k log n) nonconstructive upper bound which we derive. The nonconstructive approach allows us to generate fairly small sets S which have a very high probability of having the surjective k-projection property.
A. K. Chandra et al., "On Sets of Boolean n-Vectors with All k-Projections Surjective," Acta Informatica, vol. 20, no. 1, pp. 103-111, Springer Verlag, Oct 1983.
The definitive version is available at http://dx.doi.org/10.1007/BF00264296
Keywords and Phrases
International Standard Serial Number (ISSN)
Article - Journal
© 1983 Springer Verlag, All rights reserved.