covering designs of the form $(v,k,2)$

Question

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)

Answer 1

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

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

Answer 2

Fort and Hedlund determined the minimum size of a $(v,3,2)$-covering design: Minimal coverings of pairs by triples, Pacific J. Math. 8(4), 709-719, 1958.

The case $(v,4,2)$ was solved by Mills: On the covering of pairs by quadruples I, JCTA 13, 55–78, 1972 and II, JCTA 15, 138–166 (1973).

For the case $(v,5,2)$ with $v\equiv 0\pmod 4$, Abel, Assaf, Bennett, Bluskov and Greig established that the Schönheim bound $\left\lceil\frac{v}{5}\left\lceil \frac{v-1}{4}\right\rceil\right\rceil$ is tight for $v\geqslant 28$ with 17 possible exceptions in the range $40\leqslant v\leqslant 280$: Pair covering designs with block size 5, Discrete Mathematics 307(14), 1776-1791, 2007.

The same authors have results for $(v,6,2)$: Pair covering and other designs with block size 6, J Comb Des 15(6), 511-533, 2007

Caro and Yuster proved that for sufficiently large $v$ the minimum size of a $(v,k,2)$ covering design is $\left\lceil\frac{v}{k}\left\lceil \frac{v-1}{k-1}\right\rceil\right\rceil$: Covering Graphs: The Covering Problem Solved, JCTA 83 (2) 273–282, 1998.

The La Jolla Covering repository is a good source for covering designs. According to this table the smallest open case with $t=2$ is $(v,k,t)=(23,6,2)$ where the minimum size is either 20 or 21.