2
$\begingroup$

A $(v,k,t)$ covering design is a collection of $k$-subsets of $V=\{1,\ldots,v\}$ chosen so that any $t$-subset of $V$ is contained in (or "covered by") at least one $k$-set in the collection. Existence is trivial, so instead one focuses on obtaining "small" coverings.

The best lower bound on the size of a covering design is the Schönheim bound, $L(v,k,t) = \left\lceil \frac{v}{k} \left\lceil \frac{v-1}{k-1} \left\lceil \cdots \left\lceil \frac{v-t+1}{k-t+1} \right\rceil \cdots \right\rceil \right\rceil \right\rceil$.

Arising out of an application to something else, I am in need of covering designs (especially for small $t$, say $t=2$ or $t=3$) where $v$ is given by a linear function in $k$. In such a situation, it is not difficult to show that when $k$ exceeds some threshold value $k_0$, the Schönheim bound works out to be a constant. (For example, if $v=4k+4$ and $t=2$, we have $L(4k+4,k,2)=21$ for all $k\geq 20$.)

It seems that little is known about the existence of coverings meeting the Schönheim bound in this situation: for $t=2$, $\frac{v}{k}\leq \frac{13}{4}$, the number of blocks is (with a few exceptions) at most $13$, designs meeting the bound are known. (See Theorem VI.11.31 in the Handbook of Combinatorial Designs.) This research works on the principle of "What can we cover with a fixed number of blocks?".

However, in applications, it is usually sufficient to have "good" rather than "optimal" examples.

A 2013 paper by Chee, Colbourn, Ling and Wilson shows that, asymptotically, one can construct coverings with $t=2$ which are within a constant of the Schönheim bound; however, if my understanding of the paper is correct, that constant is dependent on $k$ (so isn't helpful if $k$ is not fixed).

So the general question is: given a fixed $t$, and $v=ak+b$ for $k\geq k_0$ (or $k$ "large enough"), does there exist a $(ak+b,k,t)$ covering of constant size?

Most specifically, I am interested in the cases where $v=4k+2$ and $v=4k+4$.

$\endgroup$

1 Answer 1

0
$\begingroup$

Partition all $v$ elements onto groups of size $[k/t]$ and for any $t$ groups choose a $k$-set containing them all. This is of constant (but large) size.

$\endgroup$

You must log in to answer this question.

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