Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-17T18:02:26.292Z Has data issue: false hasContentIssue false

Determination of a Subset from Certain Combinatorial Properties

Published online by Cambridge University Press:  20 November 2018

David G. Cantor
Affiliation:
Institute for Defense Analyses, Princeton, New Jersey and University of Washington
W. H. Mills
Affiliation:
Institute for Defense Analyses, Princeton, New Jersey and University of Washington
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1966