4
$\begingroup$

This question came up in a practical situation at work...

Given a set S of size n, what is the minimum number of subsets of S of size k s.t. each pair of elements of S occurs in the same subset at least once?

$\endgroup$
3
  • $\begingroup$ Tell me if I am wrong, but it seems to be related to $(\nu,k,\lambda)$-designs, isn't it? $\endgroup$
    – Bernikov
    Feb 3, 2012 at 15:58
  • $\begingroup$ Just curious - what line of work? $\endgroup$ Apr 20, 2012 at 8:19
  • $\begingroup$ Crowdsourcing. :) We wanted to have people rank ~10 or 20 items from best to worst, but thought this would be too much to handle. So the idea was to break the task up into ranking ~5 items at a time, while making sure each pair of items is compared at least once. $\endgroup$ Apr 23, 2012 at 14:47

2 Answers 2

7
$\begingroup$

If you want each $l$-tuple of elements to occur at least once then you can do this with $(1 + o(1))\binom{n}{l}/\binom{k}{l}$ sets, which is within $1 + o(1)$ of optimal by a simple counting argument. This is proven using something called the Rödl Nibble. Most likely when $l = 2$, which is the situation you're interested in, there is a direct construction. The problem is perhaps more naturally formulated in terms of graphs: you're looking for a covering of all the edges of the complete graph $K_n$ by copies of $K_k$.

In terms of explicit constructions, this paper seems relevant. I'm led to understand that one of the authors takes a passing interest in Math Overflow; perhaps he will comment further.

  • MR1333298 Daniel M. Gordon, Oren Patashnik, Greg Kuperberg, New constructions for covering designs. J. Combin. Des. 3 (1995), no. 4, 269–284, doi:10.1002/jcd.3180030404.

In the spirit of current discussions on open access, a free version of the above is at https://arxiv.org/abs/math/9502238

$\endgroup$
1
  • 1
    $\begingroup$ ccrwest.org/cover.html is the site of the La Jolla Covering Repository, which contains optimal or known near optimal coverings for many small values. Gerhard "Ask Me About System Design" Paseman, 2012.02.03 $\endgroup$ Feb 3, 2012 at 19:21
4
$\begingroup$

The more general problem, as Ben Green says, is to cover every $t$-tuple by subsets of size $k$ in a set of size $v$. (These are more standard variables.) This is called a covering design. (It's not the same as a $(v,k,t)-\lambda$-design, because in those each tuple is covered the same number of times, rather than at least once.) Although there is no theorem to this effect, finding covering designs looks like an open-ended problem that will never be completely solved, even though there are many good ideas and it can be solved in some cases. In this respect it is like the problem of finding sphere packings, error-correcting codes, graphs with various properties, etc. Non-rigorously the La Jolla covering repository shows you that it looks that way, because many of the competitive covering designs, even for $t=2$, were found by methods such as simulated annealing and even "private tools".

As Ben also mentions, if $k$ and $t$ are fixed, then Rodl showed that the covering density converges to 1 as $v \to \infty$. In this limit covering designs are equivalent to packing designs up to an $o(1)$ fraction of slop. Rodl's technique is the "Rodl nibble", in which small clusters of blocks are added incrementally. However, it was discovered (see Asymptotically optimal covering designs, J. Combin. Theory Ser. A 75 (1996), no. 2, 270–280) that you might as well let a Rodl nibble be just a single block. This simplifies Rodl's construction to the random greedy algorithm. There is also a non-rigorous model that correctly predicts the rate at which the random greedy algorithm converges to density 1. There has been a lot of interesting work to close the gap between rigorous bounds on the random greedy algorithm, and the non-rigorous model of the algorithm.

If $k$ grows along with $v$, then there is no known asymptotic $1+o(1)$ bound even for $t=2$. (Unless $k$ grows so slowly that the arguments for $k$ fixed still work.) The volume lower bound, just the fact that the covering density is at least 1, can be improved to the Schonheim bound. (If $k$ is fixed then the Schonheim bound is the same as the volume bound up to $1+o(1)$.) It's easy to believe that the Schonheim bound is close to the truth for a wide range of parameters, but no such thing is proven except for the smallest values of $k$. For instance, when $k=3$, the Schonheim bound is always sharp.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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