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(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.

Department(s)

Computer Science

Keywords and Phrases

Computer Metatheory

International Standard Serial Number (ISSN)

0001-5903

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 1983 Springer Verlag, All rights reserved.

Publication Date

01 Oct 1983

Link to Full Text

Share

 
COinS