minimum number of subsets?

Question

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?

Answer 1

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

Answer 2

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.