Is there an estimate for how much k-element subsets are needed to have any t-element subset in at least one of them?

100 Views Asked by At

Let's call $S(t, k, n)$ a minimal number of $k$-element subsets (blocks) of an $n$-element set $S$ with the property that each $t$-element subset of $S$ is contained in at least one block.

Are there any known estimates for $S(t, k, n)$?

P.S. I've found the similar notion of a "Steiner system" but it's a bit different thing ("in exactly one block" instead of "at least one block").

1

There are 1 best solutions below

1
On

Your $S$ would be what is called a $(n,k,t)$-covering design. There is literature about those, and a well-maintained online database of examples at https://www.ccrwest.org/cover.html.