Back to Search
Start Over
Determination of a Subset from Certain Combinatorial Properties
- Source :
- Canadian Journal of Mathematics. 18:42-48
- Publication Year :
- 1966
- Publisher :
- Canadian Mathematical Society, 1966.
-
Abstract
- Let N be a finite set of n elements. A collection ﹛S1, S2, … , Sm﹜ of subsets of N is called a determining collection if an arbitrary subset T of N is uniquely determined by the cardinalities of the intersections Si ⋂ T, 1 ≤ i ≤ m. The purpose of this paper is to study the minimum value D(n) of m for which a determining collection of m subsets exists.This problem can be expressed as a coin-weighing problem (1; 7).In a recent paper Cantor (1) showed that D(n) = O(n/log log n), thus proving a conjecture of N. J. Fine (3) that D(n) = o(n). More recently Erdös and Rényi (2), Söderberg and Shapiro (7), Berlekamp, Mills, and Leo Moser have independently found proofs that D(n) = O(n/log n).
Details
- ISSN :
- 14964279 and 0008414X
- Volume :
- 18
- Database :
- OpenAIRE
- Journal :
- Canadian Journal of Mathematics
- Accession number :
- edsair.doi...........121802bd147526a7e8bc5d8f1267eae9