4
$\begingroup$

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)
$\endgroup$
  • $\begingroup$ I would call the covering designs $\ (v\ k\ 2)\ $-- sloppy planes. $\endgroup$ – Włodzimierz Holsztyński Jan 3 '15 at 22:28
  • $\begingroup$ Your $\ \frac{n(n-1)}2\ $ must be a typo(?). A simple calculation shows that the number of 3-subset of a $\ (\nu\ 3\ 2)\ $ perfect system must be $\ \frac{\nu\cdot(\nu-1)}3\ $ (it's $\ 3,\ $ not $\ 2,\ $ in the denominator). Also then $\ \nu\equiv 1\ or\ 3\mod 6\ $ (rather than $\ 0\ or\ 3).\ $ Thus I feel that it would be nice and useful for non-specialists like me to have a short list of basic results in a separate Answer. $\endgroup$ – Włodzimierz Holsztyński Jan 4 '15 at 1:43
  • 1
    $\begingroup$ @WłodzimierzHolsztyński You can find basic facts in the paper I linked to in my post (or those given by Thomas Kalinowski as well, I think). Handbook of Combinatorial Designs is a good reference book for this sort of basic knowledge; coverings are treated in Section 11 of Chapter IV in the 2nd edition. As for the typos, yes, they are not correct, although the number of $3$-subsets in this case is not $\frac{v(v-1)}{3}$ but $\frac{\binom{v}{2}}{\binom{3}{2}} = \frac{v(v-1)}{6}$. I'll edit OP's post. $\endgroup$ – Yuichiro Fujiwara Jan 4 '15 at 6:31
  • $\begingroup$ @YuichiroFujiwara -- thank you for the links. And I let $\ \frac{\binom{\nu}2}{\binom 32}=\frac{\nu\cdot (\nu-1)}{3\cdot 2}\ $ to have somehow just $\ 3\ $ in the denominator--ooops! Sorry. $\endgroup$ – Włodzimierz Holsztyński Jan 4 '15 at 6:46
8
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ Together with Daniela Kühn, Allan Lo and Deryk Osthus I have a submitted a paper that proves that statement of Gustavsson and gives quantitative bounds on the value of $\epsilon_H$. The most recent version can be found on the arXiv. arxiv.org/abs/1410.5750 $\endgroup$ – Ben Barber Jan 5 '15 at 13:35
  • $\begingroup$ @BenBarber That's awesome! Thank you for the comment and link, and thank you for your work! $\endgroup$ – Yuichiro Fujiwara Jan 5 '15 at 13:40
  • $\begingroup$ And please feel free to make this post more informative and/or correct errors, or post another answer. $\endgroup$ – Yuichiro Fujiwara Jan 5 '15 at 14:55
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, that's usefull, I allready knew about la Jolla, the second source is great! Do you know if there has been any work on the bounds for arbitrary $(v,k,2)$? $\endgroup$ – Jorge Fernández Jan 3 '15 at 21:24
  • $\begingroup$ I know there are resuts for $(v,k,t)$ in general, but I though maybe with $(v,k,2)$ they could be sharper $\endgroup$ – Jorge Fernández Jan 3 '15 at 21:25
  • 2
    $\begingroup$ Caro and Yuster's proof might be incomplete (although the statement itself is probably correct). See my answer (and the paper I linked to) for more detail. $\endgroup$ – Yuichiro Fujiwara Jan 3 '15 at 23:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.