1
$\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$
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$

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.