As you probably know, the web site:
[La Jolla Covering Repository]
http://www.ccrwest.org/cover.html
claims to have covering designs for "(v,k,t)-coverings with v<=32,
k<=16, t<=8, and fewer than 50,000 blocks."
I think you have generalized from the use of the word "Greedy" on the
one Web page to thinking it has an intrinsic meaning with respect to
the covering designs sought. It does not. It refers merely to the
method of construction, for which see the 1995 paper by Gordan et al,
also at that site and also pointed out to you previously.
It also has a PDF paper with lower bounds for much of this range of
parameters. Since the only cases you ask about are for t = 4, I'll
limit the rest of the discussion to that.
Let's walk through one of your cases, and I'm sure you will be able to
fill in the blanks for the remaining cases at your leisure. What is
the smallest number of blocks necessary for a (7,6,4) design?
Let's first look at what we learn from the Web site, then back up and
think it through for ourselves.
On page 4 of the Lower Bounds Table:
[Lower bounds table (PDF)]
http://www.ccrwest.org/cover/LOW.pdf
there is a table for t = 4 and various values of v up to 32 and k up
to 16. The entry for v = 7 and k = 6 is 5, meaning that 5 is a lower
bound on the number of blocks necessary.
Compare this with the information in the Upper Bounds Table:
[Upper bounds table (PDF)]
http://www.ccrwest.org/cover/HIGH.pdf
You will find (on page 4) that a (7,6,4)-covering design with 5 blocks
has been constructed. The annotation "l*" beside the entry means that
it was constructed as a "greedy covering", using lexicographic
ordering, and that the design is known to be optimal.
Finally an HTML page with links to respective listings of designs is here:
[La Jolla Covering Repository Tables]
http://www.ccrwest.org/cover/HIGH.html
from which you should be able to navigate to both the
(10,6,4)-covering design found previously as well as to the (7,6,4)
case now under discussion.
Absent the foregoing research, how might we discover an optimal
(7,6,4)-covering design for ourselves. Well, the block size 6 here is
pretty big in relationship to 7. I take it you've already noticed
that a (6,6,4)-covering design only needs one block! The (7,6,4) case
can then be considered as an extension adding one more element.
Consider the 4-subsets of {1,2,3,4,5,6,7} which are _not_ covered by (say):
{1,2,3,4,5,6}
i.e. the single block needed for (6,6,4). These are exactly the
4-subsets that contain the extra point 7, so what is needed is a
collection of 5-subsets that cover all the 3-subsets of {1,2,3,4,5,6}.
We then add extra point 7 to each of those, obtaining some 6-subsets
for the overall collection, and we're done!
It turns out that C(6,5,3) = 4. Although there are 30 subsets of size
3 in a set of size 6, and a subset of size 5 covers 10 of these at a
time, it is not possible to use just 3 = 30/10 to get the job done.
If that were possible, then each of the 6 elements would have to
appear in exactly 2 of the 3 blocks (since an element appearing in
only one block would fail to meet some other element ever, and since
not all 6 elements can be in the same 5-subset), but one cannot
arrange for three 5-subsets to have empty intersection here! So, at
least 4 blocks are needed, and these will do:
{1,2,3,4,5} -- 6 is missing
{1,2,3,4,6} -- 5 is missing
{1,2,3,5,6} -- 4 is missing
{1,2,4,5,6} -- 3 is missing
It is easy to verify that each 3-subset is contained in one of these
four 5-subsets, because one picks an element from {3,4,5,6} not
contained in that 3-subset and uses the corresponding 5-subset above
that "misses" it.
Putting this (6,5,3)-covering design together with the extra point 7,
as previously discussed, gives our final (7,6,4)-covering design using
the minimal five blocks:
{1,2,3,4,5,6} -- 7 is missing
{1,2,3,4,5,7} -- 6 is missing
{1,2,3,4,6,7} -- 5 is missing
{1,2,3,5,6,7} -- 4 is missing
{1,2,4,5,6,7} -- 3 is missing
Once again you can make a final verification that this is a
(7,6,4)-covering design. To see that any 4-subset is covered, pick an
element out of {3,4,5,6,7} not needed in that 4-subset, and use the
corresponding 6-subset above that "misses" it.
hope this helps, mathtalk-ga |
