## A small collection of large subsets covering all small subsets.

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

Let $r,s,n$ be positive integers with $r < s < n$. Let $U = \{1,\ldots,n\}$.

Let $S$ contain $s$-element subsets of $U$ (of our choosing). What is that smallest we can make $S$ such that every $r$-element subset of $U$ is a subset of some element in $S$?

I'm curious what the best known upper and lower bounds are on the smallest we can make $S$, and I am especially interested in the case where $r << s << n$. I am more worried about asymptotic behavior than exact bounds.

This can also be viewed as a special case of a set-cover problem that has a lot of symmetry. I'm afraid/hoping there's something simple from graph theory that solves my problem.

EDIT: Thanks to @Gerhard, I see this is a well known problem called covering numbers / covering designs.

-

3
www.ccrwest.org/cover.html , the La Jolla covering repository, should be your first stop. Let us know what it does not answer. Gerhard "Ask Me About System Design" Paseman, 2010.10.13 – Gerhard Paseman Oct 14 2010 at 5:23

## 1 Answer

What you are looking for is an `$(r,s,n)$`-covering design. A good starting point might be the La Jolla Covering Repository or in fact, any book on design theory. In general, the smallest possible size for your covering design is given by `$\binom{n}{r}/\binom{s}{r}$` in which case every $r$ -element subset is contained in exactly one $s$-element subset and the design is then called a `$(r,s,n)$`-Steiner system. There are necessary conditions for Steiner systems to exist such as `$\binom{s-i}{r-i} | \binom{n-i}{r-i}$` for all $i$. Quite a lot is known about the existence of `$(2,3,n)$`-Steiner systems, and `$(3,4,n)$`-Steiner systems, but in general their existence is an open question.

-

Thank you -- this is perfect. It seems Erdos and Spencer give an upper bound of (1+\ln(C(s,r)))C(n,r)/C(s,r), which is perfect for my purposes! If I had enough reputation, I would upvote your answer : – Lev Reyzin Oct 14 2010 at 5:40
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 15, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.934317409992218, "perplexity_flag": "head"}