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.