Minimum number of subsets of $A$ of a given order that contain all possible pairs of elements of $A$

Let us consider a set $A$ containing $n$ elements. What is the minimum number of subsets of $A$ of order $k\geq 2$ such that, for every $(x, y)\in A^2$, at least one those subsets contains both $x$ and $y$ as its elements?

We know that the number of unordered pairs of elements of $A$ is $$\binom{n}{2},$$ but the minimum number of such subsets is definitely smaller. For $k = 5$, the subset $\{a,b,c,d,e\}$ already yields $10$ of these pairs. And if $n = k$, then the answer is trivially $1$.

Is there a way to compute the minimum number of subsets that satisfy this condition, given $n$ and $k$?

Solution 1:

This is a set covering problem, a well-considered subject which I know nothing about. However, I have in my library the book Packing and Covering in Combinatorics, A. Schrijver (ed.), Mathematical Centre Tracts 106, Mathematisch Centrum, Amsterdam, 1979, which contains on pp. 89-97 a survey article "Packing and covering of $\binom kt$-sets" by A. E. Brouwer with a bibliography of 28 items. Of course you want something more up to date, but at least this 1979 survey is a starting point.

Brouwer defines: $$C(t,k,v)=\min\{|\mathcal B|:\mathcal B\subseteq\mathcal P_k(v)\text{ and each }T\in\mathcal P_t(v)\text{ is contained in some }B\in\mathcal B\}$$ where $\mathcal P_t(v)$ is the collection of all $t$-element subsets of the set $\{0,1,\dots,v-1\}.$

Thus, in Brouwer's notation, you are asking for the value of $C(2,k,n).$ The obvious lower bound is $$C(2,k,n)\ge\frac{\binom n2}{\binom k2}=\frac{n(n-1)}{k(k-1)}.$$ Complete answers are known (or rather, were known in 1979) only for $k=3$ and $k=4.$ The covering result

$$C(2,3,n)=\left\lceil\frac n3\left\lceil\frac{n-1}2\right\rceil\right\rceil$$

is attributed to M. K. Fort, Jr., and G. A. Hedlund, Minimal coverings of pairs by triples, Pacific J. Math. 8. (1958) 709–719.

For $n\notin\{7,9,10,19\}$ the result $$C(2,4,n)=\left\lceil\frac n4\left\lceil\frac{n-1}3\right\rceil\right\rceil$$ is attributed to W. H. Mills, On the covering of pairs by quadruples, I: J. Combin. Theory (A) 13 (1972) 55-78, II: J. Combin. Theory (A) 15 (1973) 138-166; the exceptional values are $C(2,4,7)=5,\ C(2,4,9)=8,\ C(2,4,10)=9,\ C(2,4,19)=31.$

P.S. Brian Scott points out that "There is a second edition of MCT 106 from 1982, freely available here as a (non-searchable) PDF. Any changes from the first edition appear to be very minor."

Solution 2:

Let A be a set of containing n element. There are $\frac{n!}{k! (n-k)!}$ subsets of A with k elements, and the elements $a,b\in A$ are included in $\frac{(n-2)!}{(k-2)! (n-k)!}$ of those subsets with k elements. Which means that in $ M= \frac{n!}{k! (n-k)!} - \frac{(n-2)!}{(k-2)! (n-k)!}$ of them either $a$ or $b$ or both $a, b$ are not included.

Therefore you need to have at least M+1 subsets of A with k elements to guarantee that both $a$ and $b$ are included in at least one of them.