8
$\begingroup$

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$?

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for your very great answer! I was truly surprised to know this is still an open problem, I wasn't expecting it. $\endgroup$ – Labba Apr 10 '16 at 23:57
  • $\begingroup$ Is it still open? I didn't search for anything more recent than that 1979 book which I happened to have on my shelves. $\endgroup$ – bof Apr 11 '16 at 0:21
  • $\begingroup$ I'll check some books at the library of my university: now that I know some infos about the specific kind of problem I was interested in, it will be easier to find more things related to it. I just have this sensation that it has not been solved yet, because my intuition tells me it's not that kind of problem that can be solved in just a few decades; but I will definitely let you know if I find something new on the topic! $\endgroup$ – Labba Apr 11 '16 at 0:33
  • 2
    $\begingroup$ For those interested in the general problem (as defined by Brouwer), it is called covering design. One can search for covering designs on the web site La Jolla Covering Repository. $\endgroup$ – vinc17 Jul 2 '17 at 21:51
4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I think you have misinterpreted the problem. I don't think the OP wants the minimum number $s$ such that every family of $s\ k$-element sets covers all the pairs; rather, I think he wants the minimum number $s$ such that some family of $s\ k$-element sets covers all the pairs. $\endgroup$ – bof Apr 9 '16 at 21:09
  • 1
    $\begingroup$ Yes, bof is right. $\endgroup$ – Labba Apr 9 '16 at 21:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.