About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Acta Informatica
Paper
On sets of Boolean n-vectors with all k-projections surjective
Abstract
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(k 2k 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. © 1983 Springer-Verlag.