Return to Question

Let $n \ge k \ge t \in \mathbb{N}$, and consider a universe $U$ of size $n$. Let $\mathcal{F}$ be a family of $k$-subsets of $U$, such that every $t$-subset of $U$ is contained in at least one member of $\mathcal{F}$. My question is: How small can $\mathcal{F}$ be? In other words, what is the smallest possible size of $\mathcal{F}$, in terms of $n,k,t$? Is it a known theorem?

Obviously, if $k=n$ then $|\mathcal{F}|=1$. It is also not hard to see that if $k=n-1$, then the smallest possible size of $|\mathcal{F}|$ is $t+1$.

Edit: Actually, this question can be rephrased as follows: What is the size of the smallest family $\mathcal{F}'$ of $(n-k)$-subsets such that $\mathcal{F}'$ does not have a hitting set of size $t$. Taking this view, it is not hard to see that $|\mathcal{F}'| \le (n-k) \cdot (t+1)$ (at least when $n-k > 0$).

Let $n \ge k \ge t \in \mathbb{N}$, and consider a universe $U$ of size $n$. Let $\mathcal{F}$ be a family of $k$-subsets of $U$, such that every $t$-subset of $U$ is contained in at least one member of $\mathcal{F}$. My question is: How small can $\mathcal{F}$ be? In other words, what is the smallest possible size of $\mathcal{F}$, in terms of $n,k,t$? Is it a known theorem?

Obviously, if $k=n$ then $|\mathcal{F}|=1$. It is also not hard to see that if $k=n-1$, then the smallest possible size of $|\mathcal{F}|$ is $t+1$.

Let $n \ge k \ge t \in \mathbb{N}$, and consider a universe $U$ of size $n$. Let $\mathcal{F}$ be a family of $k$-subsets of $U$, such that every $t$-subset of $U$ is contained in at least one member of $\mathcal{F}$. My question is: How small can $\mathcal{F}$ be? In other words, what is the smallest possible size of $\mathcal{F}$, in terms of $n,k,t$? Is it a known theorem?

Obviously, if $k=n$ then $|\mathcal{F}|=1$. It is also not hard to see that if $k=n-1$, then the smallest possible size of $|\mathcal{F}|$ is $t$.

Let $n \ge k \ge t \in \mathbb{N}$, and consider a universe $U$ of size $n$. Let $\mathcal{F}$ be a family of $k$-subsets of $U$, such that every $t$-subset of $U$ is contained in at least one member of $\mathcal{F}$. My question is: How small can $\mathcal{F}$ be? In other words, what is the smallest possible size of $\mathcal{F}$, in terms of $n,k,t$? Is it a known theorem?

Obviously, if $k=n$ then $|\mathcal{F}|=1$. It is also not hard to see that if $k=n-1$, then the smallest possible size of $|\mathcal{F}|$ is $t+1$.

Edit: Actually, this question can be rephrased as follows: What is the size of the smallest family $\mathcal{F}'$ of $(n-k)$-subsets such that $\mathcal{F}'$ does not have a hitting set of size $t$. Taking this view, it is not hard to see that $|\mathcal{F}'| \le (n-k) \cdot (t+1)$ (at least when $n-k > 0$).

Let $n \ge k \ge t \in \mathbb{N}$, and consider a universe $U$ of size $n$. Let $\mathcal{F}$ be a family of $k$-subsets of $U$, such that every $t$-subset of $U$ is contained in at least one member of $\mathcal{F}$. My question is: How small can $\mathcal{F}$ be? In other words, what is the smallest possible size of $\mathcal{F}$, in terms of $n,k,t$? Is it a known theorem?

Let $n \ge k \ge t \in \mathbb{N}$, and consider a universe $U$ of size $n$. Let $\mathcal{F}$ be a family of $k$-subsets of $U$, such that every $t$-subset of $U$ is contained in at least one member of $\mathcal{F}$. My question is: How small can $\mathcal{F}$ be? In other words, what is the smallest possible size of $\mathcal{F}$, in terms of $n,k,t$? Is it a known theorem?

Obviously, if $k=n$ then $|\mathcal{F}|=1$. It is also not hard to see that if $k=n-1$, then the smallest possible size of $|\mathcal{F}|$ is $t$.