A covering design $(v,k,t)$ is a family of subsets of $[v]$ each having $k$ elements such that given any subset of $[v]$ of $t$ elements it is a subset of one of the sets of the family. A problem is to find the minimum number of subsets such a family can have.


I am interested in the case $(v,k,2)$. It seems to be equivalent to the problem of finding the minimum number of copies of $K\_k$ that are needed to cover the graph $K\_v$.


When $k=3$ this problem may be solved optimally with a Steiner triple system if it exists, which happens if and only if $v$ is $1$ or $3 \bmod 6$, in this case $\frac{v(v-1)}{6}$ subsets are required.


My questions are the following:


* Is the minimum of subsets for $(v,3,2)$ known when the congruence does not hold?
* If not what are good bounds?
* Does the problem with $t=2$ have another name (It seems like it may be more common than the general covering design)
* Is the minimum number of subsets for $(v,k,2)$ known?
* If not, which are some good bounds (specific values of $k$ are also welcome)



covering designs of the form $(v,k,2)$
**Edit:** ***The possible "gap" of sort in Caro and Yuster's proof of their upper bound has just been fixed!*** *See Ben Barber's comment below (and his joint paper with Daniela Kühn, Allan Lo and Deryk Osthus* [*on arXiv*](http://arxiv.org/pdf/1410.5750v1.pdf). *This shows Gustavsson's theorem (whose proof by Gustavsson himself might have been regarded as incomplete but was used by Caro and Yuster). So this result proves the general upper bound on the smallest coverings mentioned in Thomas Kalinowski's post is indeed correct.*


The most up to date account (except the above mentioned paper) on the minimum number of subsets for a $(v,k,2)$ covering is here:


[Y. M. Chee, C. J. Colbourn, A. C. H. Ling, R. M. Wilson, Covering and packing for pairs, *J. Combin. Theory Ser. A* **120** (2013) 1440–1449.](http://dx.doi.org/10.1016/j.jcta.2013.04.005)


One important remark about Thomas Kalinowski's answer is that the asymptotic solution by Caro and Yuster may be incomplete, although the claimed upper bound is likely the correct one. They rely on Gustavsson's theorem on graph decomposition (Lemma 2.1 in Caro and Yuster's paper), which is claimed to be proved in the following thesis:


T. Gustavsson, ``Decompositions of Large Graphs and Digraphs with High Minimum
Degree,'' Doctoral Dissertation, Dept. of Mathematics, Univ. of Stockholm, 1991.


However, here's an excerpt from the 2013 paper by Chee, Colbourn, Ling, and Wilson:



> 
> Their approach relies in an essential manner on a strong statement by Gustavsson:
> 
> 
> **Proposition 1.1**: . Let $H$ be a graph with $v$ vertices and $h$ edges, having degree sequence $(d\_1,\dots,d\_v)$. Then there exist a constant $N\_H$ and a constant $\epsilon\_H>0$, both depending only on $H$, such that for all $n>N\_H$, if $G$ is a graph on $n$ vertices, $m$ edges, and degree sequence $(\delta\_1,\dots,\delta\_n)$ so that $\min(\delta\_1,\dots,\delta\_n) \geq n(1−\epsilon\_H)$, $\gcd(d\_1,\dots,d\_v)\ \vert\ \gcd(\delta\_1,\dots,\delta\_n)$, and $h\ \vert\ m$, then $G$ has an edge partition (decomposition) into graphs isomorphic to $H$.
> 
> 
> We have not been able to verify the proof of Proposition 1.1. Indeed, while the result has been
>  used a number of times in the literature, no satisfactory proof of it appears there. While we expect
>  that the statement is true, we do not think that the proof in [12] is sufficient at this time to employ
>  the statement as a foundation for further results. Therefore we adopt a strategy that is completely
>  independent of Proposition 1.1, and independent of the results built on it.
> 
> 
> 


So, one might want to be careful about Caro and Yuster's claimed solution. Chee, Colbourn, Ling, and Wilson gave a slightly weaker upper bound on the minimum size of a $(v,k,2)$ covering, which essentially states that for sufficiently large $v$, Caro and Yuster's claimed upper bound is correct within a constant that depends on $k$. (And the proof of Gustavsson's theorem by Barber, Kühn, Lo and Osthus shows it *is* correct.) 


