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
Discrete Mathematics
Paper
Golden ratios in a pairs covering problem
Abstract
Let An = {1,...,n} and let B = {B1,...,Br} where B1,...,Br are subsets of A n, each of size m. We say that B covers all the pairs (i, j), 1≤i<j≤n, if for each pair set {i, j} there exists k, 1≤k≤r, such that {i, j}⊆Bk. Let N(m, n) denote the minimum possible cardinality of such a system B. In this paper, the values of N(m, n) are determined exactly for all m, n such that m≥ 1 2n. It is further shown that in this range N(m, n) is a function of the fraction m/n only. Significant results for m< 1 2n are also given. © 1982.