Skip to main content
MathOverflow

Return to Question

replaced http://math.stackexchange.com/ with https://math.stackexchange.com/
Source Link
Community Bot
Community Bot
  • 1
  • 2
  • 3

Consider the set $S=\{1,2,\ldots, n\}$, and let $a<b<n$. What is the minimum number $f(a,b)$ such that there exist $f(a,b)$ subsets of $S$ of size $a$ for which any subset of $S$ of size $b$ contains at least one of the chosen subsets?

It is not hard to obtain a bound $f(a,b)\leq \dbinom{n}{a}-\dbinom{b}{a}+1$, as is shown herehere. But it doesn't seem easy to go beyond that. However, since this is such a simply-stated question, I would expect that it has been well-studied in combinatorial set theory. So, any references to better upper or lower bounds (or better yet, the exact answer) would be appreciated.

Consider the set $S=\{1,2,\ldots, n\}$, and let $a<b<n$. What is the minimum number $f(a,b)$ such that there exist $f(a,b)$ subsets of $S$ of size $a$ for which any subset of $S$ of size $b$ contains at least one of the chosen subsets?

It is not hard to obtain a bound $f(a,b)\leq \dbinom{n}{a}-\dbinom{b}{a}+1$, as is shown here. But it doesn't seem easy to go beyond that. However, since this is such a simply-stated question, I would expect that it has been well-studied in combinatorial set theory. So, any references to better upper or lower bounds (or better yet, the exact answer) would be appreciated.

Consider the set $S=\{1,2,\ldots, n\}$, and let $a<b<n$. What is the minimum number $f(a,b)$ such that there exist $f(a,b)$ subsets of $S$ of size $a$ for which any subset of $S$ of size $b$ contains at least one of the chosen subsets?

It is not hard to obtain a bound $f(a,b)\leq \dbinom{n}{a}-\dbinom{b}{a}+1$, as is shown here. But it doesn't seem easy to go beyond that. However, since this is such a simply-stated question, I would expect that it has been well-studied in combinatorial set theory. So, any references to better upper or lower bounds (or better yet, the exact answer) would be appreciated.

Source Link
boaten
boaten
  • 175
  • 5

Choosing subsets to cover larger sets

Consider the set $S=\{1,2,\ldots, n\}$, and let $a<b<n$. What is the minimum number $f(a,b)$ such that there exist $f(a,b)$ subsets of $S$ of size $a$ for which any subset of $S$ of size $b$ contains at least one of the chosen subsets?

It is not hard to obtain a bound $f(a,b)\leq \dbinom{n}{a}-\dbinom{b}{a}+1$, as is shown here. But it doesn't seem easy to go beyond that. However, since this is such a simply-stated question, I would expect that it has been well-studied in combinatorial set theory. So, any references to better upper or lower bounds (or better yet, the exact answer) would be appreciated.