minimum number of subsets? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T04:09:31Z http://mathoverflow.net/feeds/question/87442 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/87442/minimum-number-of-subsets minimum number of subsets? Alya Asarina 2012-02-03T15:41:03Z 2012-04-20T07:11:23Z <p>This question came up in a practical situation at work...</p> <p>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?</p> http://mathoverflow.net/questions/87442/minimum-number-of-subsets/87444#87444 Answer by Ben Green for minimum number of subsets? Ben Green 2012-02-03T16:03:17Z 2012-02-03T16:17:27Z <p>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$.</p> <p>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.</p> <p>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. </p> <p>In the spirit of current discussions on open access, a free version of the above:</p> <p><a href="http://front.math.ucdavis.edu/math/9502238" rel="nofollow">http://front.math.ucdavis.edu/math/9502238</a></p> http://mathoverflow.net/questions/87442/minimum-number-of-subsets/94607#94607 Answer by Greg Kuperberg for minimum number of subsets? Greg Kuperberg 2012-04-20T07:11:23Z 2012-04-20T07:11:23Z <p>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".</p> <p>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 [<a href="http://front.math.ucdavis.edu/math/9511224" rel="nofollow">arXiv:math/9511224</a>]) 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.</p> <p>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.</p>