Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
Tell me if I am wrong, but it seems to be related to $(\nu,k,\lambda)$-designs, isn't it? –  Bernikov Feb 3 '12 at 15:58
    
Just curious - what line of work? –  Felix Goldberg Apr 20 '12 at 8:19
    
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. –  Alya Asarina Apr 23 '12 at 14:47

2 Answers 2

up vote 6 down vote accepted

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\"odl 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 (96e:05043) Gordon, Daniel M.(1-CCR); Patashnik, Oren(1-CCR); Kuperberg, Greg(1-CHI) New constructions for covering designs. (English summary) J. Combin. Des. 3 (1995), no. 4, 269–284.

In the spirit of current discussions on open access, a free version of the above:

http://front.math.ucdavis.edu/math/9502238

share|improve this answer
1  
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 –  Gerhard Paseman Feb 3 '12 at 19:21

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 [arXiv:math/9511224]) 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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