3
$\begingroup$

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$.

Improve this question
$\endgroup$
7
  • $\begingroup$ @GeoffRobinson Thanks! Could you explain why this bound holds? Also, it seems not to work at least for some parameters. For example, if $k=n$, then $|\mathcal{F}|=1$, but the bound you suggest is much larger. $\endgroup$
    – Or Meir
    Commented Feb 22, 2015 at 18:07
  • $\begingroup$ I did not write what I intended: the bound should have read $|\mathcal{F}| \geq \frac{n!(k-t)!}{k!(n-t)!}.$ I think the derivation should be clear. $\endgroup$
    – Geoff Robinson
    Commented Feb 22, 2015 at 18:09
  • $\begingroup$ @GeoffRobinson Thanks! Yes, this is clear. $\endgroup$
    – Or Meir
    Commented Feb 22, 2015 at 18:09
  • $\begingroup$ La Jolla Covering Repository is online. Check it out. (Sorry, don't have the URL to copy at present.) $\endgroup$
    – The Masked Avenger
    Commented Feb 22, 2015 at 18:14
  • $\begingroup$ The smallest size of such $\mathcal{F}$ is called the covering number $C_1(n,k,t)$. I think this is the website The Masked Avenger mentioned: ccrwest.org/cover.html $\endgroup$
    – Yuichiro Fujiwara
    Commented Feb 22, 2015 at 18:40

1 Answer 1

Reset to default
3
$\begingroup$

I think it is an optimal version of a covering with index $1$.

A $t$-$(n,k,\lambda)$ covering is an ordered pair $(U,\mathcal{B})$ of a finite set $U$ of cardinality $n$ and a finite set $\mathcal{B}$ of $k$-subsets of $U$ such that every $t$-subset appears as a subset in at least $\lambda$ elements of $\mathcal{B}$. So, your $\mathcal{F}$ is the $\mathcal{B}$ of a covering with $\lambda = 1$.

The size of a smallest $t$-$(n,k,\lambda)$ covering for given $t$, $n$, $k$, and $\lambda$ (or, more precisely, the smallest realizable $\mathcal{B}$ for given parameters) is called the covering number $C_\lambda(n,k,t)$. So, what you want to know is exactly the covering number.

It is not difficult to see that $C_\lambda(n,k,t) \geq \frac{nC_\lambda(n-1,k-1,t-1)}{k}$. So, repeating this process, we get a lower bound

$$C_\lambda(n,k,t) \geq \left\lceil\frac{n}{k}\left\lceil\frac{n-1}{k-1}\dots\left\lceil\frac{\lambda(n-t+1)}{k-t+1}\right\rceil\right\rceil\right\rceil.$$

This is known as the Schönheim bound.

There are results in design theory on $C_\lambda(n,k,t)$, and most of the major results should be listed or referenced in Section 11 of the 2nd edition of the Handbook of Combinatorial Designs. The above lower bound should be noted there as well. Determining the exact value of $C_\lambda(n,k,t)$ in general seems very difficult. So, I think it's still an open problem, though there are cases the exact covering number is known.

There is also an online database known as La Jolla Covering Repository. If you're only interested in specific cases, looking up the online tables may be more helpful than reading up on coverings in the literature.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .