THE COVERING DESIGNS C(49,6,3,6,1,=168) AND C(27,6,3,4,1,=91)
Uenal Mutlu
Herbststr. 34
D-82178 Puchheim, Germany
ABSTRACT:
Here is the ingenious record breaking covering design C(49,6,3,6,1,=168)
everyone talks of, with the least number of blocks ever created!
Included are also the underlying subdesigns and the generic formulae.
The enumerated designs are attached in the appendix.
1.INTRODUCTION / DEFINITIONS:
C(v,k,t,m,L,=b) S(v,k,t,=b) t-(v,k,L,=b)
Coverings, Packings, Steiner-Systems, t-Designs are combinatorial
optimization problems found mainly in the field of discrete
mathematics. t-design is the abbrev. for "Tactical Configuration".
A covering design is a carefully selected combinatorial subset of
b blocks of the complete design with blocksize k. It assures as a
minimum at least L blocks with t matches if m of the drawn k numbers
out of the v varieties are hit. The order of the points inside the
blocks and the order of the blocks of the design itself are usually
irrelevant for such designs.
Steiner-Systems are also t-Designs with usually L=1. A t-design is
also called an exact covering and packing. t-Designs do not exist
for every v,k,t,m,l-Combo, but coverings do. The difference is:
whereas t-designs have a Covering Density of exact 1.0, coverings
do have a Covering Density > 1.0 (if it were exactly 1.0, then it
would be a t-design). So coverings have some unavoidable duplicate
t-subsets in their k-subsets. For t-Designs and Steiner Systems the
parameter m is implicit and equals to t. Nevertheless in this paper
the term "covering" shall also include the t-design if it exist, for
example S(22,6,3,=77) or 3-(22,6,1,=77).
The aim for covering designs is to find the least possible number
of blocks (b; lower bound) which still guarantees the parameters
of the design. Since t-designs are exact, it's impossible to improve
them. So the aim is directed to real covering designs only.
This kind of problems fall into the category combinatorial
optimization and is called Set Covering Problem (SCP),
comparable to the famous Travelling Salesman Problem (TSP) or
cost minimizing / profit maximazing like optimization problems.
Covering designs and t-designs are the most important structures
in Design Theory, and most of the designs are even with super-
computers hard to create, because there is still no generic formula
for all admissable parameters, and a brute-force search is too
time-consuming.
Best general approach I've seen implemented in a program is
the work of NURMELA/OeSTERGARD [18] in their program 'cover'.
They used the simulated annealing algorithm for the SCP.
It will not always find the best bounds due to time/memory
constraints, but it's generally usable, whereas most of the
other approaches are for some specific parameters or 'families',
'classes' only.
For further definitions and details the reader is referred to
for example [1,4,8,27].
2.HISTORICAL ISSUES:
Research on this subject started in the last century with
J.PLUeCKER (~1835), W.S.B.WOOLHOUSE (1844), T.P.KIRKMAN (1847+),
J.STEINER (1853).
Since 1969 it was also found to be very important in military
tactics and in the design of computer chips. Further, mainly in
statistics: medicine and agricultural experiments, nuclear research,
demoscopy, quality control, and so on, and even in lottery.
Till today nobody on earth could prove the existence or the
non-existence of the outstanding Steiner System S(17,5,4,=476)
or the S(18,6,5,=1428), though their parameters aren't really
so big. There are some more examples of such still unsolved
cases.
3.MAIN THEOREM:
Theorem 3.1: C(v1,k,t,m1,L,=b1)
+ C(v2,k,t,m2,L,=b2)
= C(v1+v2,k,t,m1+m2-1,L,=b1+b2)
The proof of this formula is trivial and can easily be verified
with any valid input sets satisfying the initial conditions,
namely both having the same parameters k,t,L.
Theorem 3.1 includes also the well known two cases of which the
second one is explicitly used here:
C(v1,6,3,3,1,=b1) + C(v2,6,3,3,1,=b2) = C(v1+v2,6,3,5,1,=b1+b2)
C(v2,6,3,3,1,=b1) + C(v2,6,3,4,1,=b2) = C(v1+v2,6,3,6,1,=b1+b2)
3.1 Construction:
C(49,6,3,6,1,=168) = C(22,6,3,3,1,=77) + C(27,6,3,4,1,=91) :
This new covering is built up from the well known Steiner-System
S(22,6,3,=77) which goes back at least to CARMICHAEL (1931) [6]
or WITT (1938) [28] plus a new C(27,6,3,4,1) in only 91 blocks,
which was found by the author in November 3, 1995 [16]. The bound
before this was 97, which gave 174 blocks for the final covering
(cf. [9], [17]). Now the new bound is improved to be 168 blocks.
These two coverings can be found in the appendix. The Steiner
System can be found for example in [6] and is also included in
in the final C(49) as being one of the subsystems.
BTW: any other combo of C1 and C2 for C(49) produces more than
168 blocks, though they are valid constructions too, they are
not the requested optimal minimum.
4.CONCLUSION:
4.1 We have shown and proven the following new lower bounds:
C(27,6,3,4,1) <= 91
C(49,6,3,6,1) <= 168
In both cases this is an improvement of at least 6
blocks against the best known bounds before (cf. [9]).
4.2 In Theorem 3.1 we have presented a generic formula for
combining two (not necessarily distinct) coverings with
same k, t and L, and the resulting parameters of the
final design.
Such coverings with small v,k,t,m are also used in the lottery;
see also the newsgroup rec.gambling.lottery; there, coverings
are usually called "wheels" and/or "systems".
5.OPEN PROBLEMS:
1. Further improve the bounds for the two designs shown here.
Also for other design parameters. A list of known bounds
can be found in scientific papers and lists; see reference.
2. Find a formula for Lower Bound Calculation for m<>t.
The "Schoenheim Lower Bound" [24,25] formula works well for
m=t only. The formulae mentioned in [9,18] IMHO vary very
much from the reality.
3. Find similar Formula like in Theorem 3.1.
4. Prove the existence/nonexistence of the Steiner Systems
with the admissable parameters S(17,5,4,=476) and/or
S(18,6,5,=1428).
6. ACKNOWLEDGEMENTS:
I would like to thank Mahmut Kursun for letting me use his
Internet account for the past several months.
7. REFERENCES / BIBLIOGRAPHY:
[1] I.ANDERSON "Combinatorial Designs - Construction Methods"
Ellis Horwood / Halsted/Wiley (1990)
[2] J.A.BATE, R.G.STANTON "A survey of (2,2,L,V) designs"
Congr.Numer. 31 (1981) 3-15
[3] J.A.BATE, R.G.STANTON "Some algorithmic results on (2,3,3,v)
designs and (2,4,4,v) designs", Util.Math. 20 (1981) 195-220
[4] Th.BETH, D.JUNGNICKEL, H.LENZ "Design Theory"
1985, BI; Update pages in Ars Combin. 28 (1990) 129-199
[5] Iliya BLUSKOV, Canada: private communication
[6] R.D.CARMICHAEL "Tactical configurations of rank two",
Amer.J.Math. 53 (1931) 217-240
[7] Y.M.CHEE, C.J.COLBOURN, D.L.KREHER "Simple t-designs with v <= 30",
Ars Combin. 29 (1990) 193-258
[8] J.H.DINITZ and D.R.STINSON (eds) "Contemporary Design Theory"
(1992), John Wiley & Sons Inc.
- W.H.MILLS, R.C.MULLIN "Coverings and Packings" 371-400
[9] Z.FUeREDI, G.J.SZEKELY, Z.ZUBOR "On the lottery problem",
J.Combin.Designs 4.1 (1996) 5-10
[10] GAP package of the RWTH-Aachen (Group-Theory package)
[11] D.M.GORDON, O.PATASHNIK, G.KUPERBERG "New constructions for
covering designs", J.Combin.Designs 3.4 (1995) 269-284
[12] D.M.GORDON, O.PATASHNIK "Asymptotically Optimal Covering Designs"
15Jun1995, preprint PS-file
[13] D.M.GORDON: private communications, lists
[14] Adolf MUeHL, Vienna: private communications, lists
[15] Uenal MUTLU, Munich: "Lists of enumerated covering designs
v<=54, k<=7, t>=1, m<=7, L=1" periodically posted in sci.math
and rec.gambling.lottery and at the following locations:
ftp.tuco.com/pub/math
http://www.tuco.com/math1.htm
[16] Uenal MUTLU "Two new covering designs: C(27,6,3,4,1,=91) and
C(49,6,3,6,1,=168)" in preperation
[17] Normand VEILLEUX, Canada: private communications, lists
[18] K.J.NURMELA, P.R.J. OeSTERGARD "Upper Bounds for Covering
Designs by Simulated Annealing", Congr.Numer. 96 (1993) 93-111
[19] K.J.NURMELA, Helsinki: private communications
[20] W.OBERSCHELP "Lotto-Garantiesysteme und Blockplaene",
Math.Phys.Semesterber. 19 (1972) 55-67
[21] O.PATASHNIK: private communications
[22] R.W.ROBINSON, G.W.SOUTHERN, W.D.WALLIS (eds) "Combinatorial
Mathematics VII", (1979/81) Springer LNCS 829
- R.G.STANTON, J.A.BATE "A computer search for B-coverings" 37-50
[23] G.SCHLEGL, Vienna: private communications, lists
[24] J.SCHOeNHEIM "On Coverings"
Pacific J.Combin. 14 (1964) 1405-1411
[25] J.SCHOeNHEIM "On maximal systems of k-tuples",
Studia Sci.Math.Hungar. 1 (1966) 363-368
[26] A.SCHRIJVER (ed) "Packing and covering in combinatorics"
Amsterdam, Math.Centre Tracts 106 (1979)
- A.E.BROUWER "Packing and Covering of (k,t)-sets" 89-97
- A.E.BROUWER, M.VOORHOEVE "Turan theory and the lotto
problem" 99-105
- J.K.LENSTRA et al. "Complexity of packing, covering and
partitioning problems" 275-291
[27] W.D.WALLIS "Combinatorial Designs"
Monographs and textbooks in pure and applied mathematics Vol. 118,
Marcel Dekker Inc., (1988)
[28] E.WITT "Ueber Steinersche Systeme",
Abh.math.Sem.hansischen Univ. 12 (1938) 265-275
APPENDIX:
C(27,6,3,4,1,=91):
------------------
#Id v b k v1 0/0 t/m l x ...
Id 27 91 6 27 0/0 3/4 1 2
Base 1
Date November 3, 1995
Author U.Mutlu, Munich/Germany
Comments
Data
1 2 3 4 5 6
1 2 4 5 7 8
1 2 4 5 9 10
1 3 4 5 7 10
1 3 4 5 8 9
1 4 5 6 7 9
1 4 5 6 8 10
1 4 5 6 18 19
1 4 5 6 20 22
1 4 5 6 26 27
1 11 12 13 14 15
1 11 16 17 18 19
1 11 20 21 22 23
1 11 24 25 26 27
1 12 13 16 23 24
1 12 13 17 21 25
1 14 16 21 26 27
1 14 17 20 22 24
1 14 18 19 23 25
1 15 16 20 22 25
1 15 17 23 26 27
1 15 18 19 21 24
2 3 6 7 8 9
2 3 6 7 9 10
2 3 12 13 20 27
2 3 12 18 20 22
2 3 12 19 20 26
2 3 13 18 22 27
2 3 13 19 26 27
2 3 18 19 22 26
2 7 10 11 14 17
2 7 10 15 21 23
2 7 10 16 24 25
2 8 9 11 23 25
2 8 9 14 15 16
2 8 9 17 21 24
3 7 8 11 15 24
3 7 8 14 21 25
3 7 8 16 17 23
3 9 10 11 16 21
3 9 10 14 23 24
3 9 10 15 17 25
4 11 12 13 16 17
4 11 14 15 18 19
4 11 20 22 24 25
4 11 21 23 26 27
4 12 13 14 23 25
4 12 13 15 21 24
4 14 16 20 21 22
4 14 17 24 26 27
4 15 16 25 26 27
4 15 17 20 22 23
4 16 18 19 23 24
4 17 18 19 21 25
5 11 12 13 24 25
5 11 14 15 26 27
5 11 16 17 20 22
5 11 18 19 21 23
5 12 13 14 16 21
5 12 13 15 17 23
5 14 17 18 19 24
5 14 20 22 23 25
5 15 16 18 19 25
5 15 20 21 22 24
5 16 23 24 26 27
5 17 21 25 26 27
6 11 12 13 21 23
6 11 14 15 20 22
6 11 16 17 26 27
6 11 18 19 24 25
6 12 13 14 17 24
6 12 13 15 16 25
6 14 16 18 19 21
6 14 23 25 26 27
6 15 17 18 19 23
6 15 21 24 26 27
6 16 20 22 23 24
6 17 20 21 22 25
7 9 12 13 20 22
7 9 12 18 22 27
7 9 12 19 22 26
7 9 13 18 20 26
7 9 13 19 20 27
8 10 12 13 19 20
8 10 12 18 19 26
8 10 12 19 22 27
8 10 13 18 22 27
8 10 13 19 22 26
8 10 18 20 26 27
11 14 15 16 17 21
11 14 16 23 24 25
C(49,6,3,6,1,=168):
-------------------
#Id v b k v1 0/0 t/m l x ...
Id 49 168 6 49 0/0 3/6 1 2
Base 1
Date November 3, 1995
Author U.Mutlu, Munich/Germany
Comments
Data
1 3 8 10 19 36
1 3 10 12 19 24
1 3 10 16 19 46
1 4 7 13 15 30
1 4 18 27 29 41
1 4 22 23 34 43
1 4 35 37 44 47
1 7 13 18 35 43
1 7 13 23 27 37
1 8 10 12 19 46
1 8 10 16 19 24
1 10 12 16 19 36
1 10 19 22 34 36
1 10 19 24 36 46
1 10 19 29 36 41
1 10 19 36 44 47
1 15 18 23 44 47
1 15 22 27 34 35
1 15 29 37 41 43
1 18 22 30 34 37
1 23 29 30 35 41
1 27 30 43 44 47
2 5 6 9 11 14
2 5 17 20 21 25
2 5 26 28 31 32
2 5 33 38 39 40
2 5 42 45 48 49
2 6 17 26 33 42
2 6 20 28 38 45
2 6 21 31 39 49
2 6 25 32 40 48
2 9 17 32 39 45
2 9 20 31 40 42
2 9 21 28 33 48
2 9 25 26 38 49
2 11 17 28 40 49
2 11 20 26 39 48
2 11 21 32 38 42
2 11 25 31 33 45
2 14 17 31 38 48
2 14 20 32 33 49
2 14 21 26 40 45
2 14 25 28 39 42
3 4 12 15 27 46
3 4 16 24 37 43
3 7 8 13 22 47
3 7 8 22 29 34
3 7 8 22 41 44
3 8 12 16 24 36
3 8 12 16 36 46
3 8 13 29 34 47
3 8 13 41 44 47
3 8 29 34 41 44
3 12 18 35 37 46
3 12 23 30 43 46
3 15 16 18 24 30
3 16 23 24 27 35
4 7 10 13 18 27
4 7 13 19 35 37
4 7 13 23 36 43
4 8 12 24 30 35
4 8 16 18 23 46
4 10 15 29 30 41
4 10 22 34 35 37
4 10 23 43 44 47
4 15 18 23 27 30
4 15 18 35 37 43
4 15 19 30 44 47
4 15 22 30 34 36
4 18 19 22 27 34
4 18 27 36 44 47
4 19 23 29 41 43
4 29 35 36 37 41
5 6 17 28 39 48
5 6 20 26 40 49
5 6 21 32 33 45
5 6 25 31 38 42
5 9 17 31 33 49
5 9 20 32 38 48
5 9 21 26 39 42
5 9 25 28 40 45
5 11 17 26 38 45
5 11 20 28 33 42
5 11 21 31 40 48
5 11 25 32 39 49
5 14 17 32 40 42
5 14 20 31 39 45
5 14 21 28 38 49
5 14 25 26 33 48
6 9 17 21 38 40
6 9 20 25 33 39
6 9 26 31 45 48
6 9 28 32 42 49
6 11 17 20 31 32
6 11 21 25 26 28
6 11 33 38 48 49
6 11 39 40 42 45
6 14 17 25 45 49
6 14 20 21 42 48
6 14 26 32 38 39
6 14 28 31 33 40
7 10 13 15 37 43
7 10 13 23 30 35
7 12 13 16 22 34
7 12 16 29 34 47
7 12 16 34 41 44
7 13 15 18 19 23
7 13 15 27 35 36
7 13 18 30 36 37
7 13 19 27 30 43
7 13 22 24 41 46
7 24 29 41 44 46
7 24 34 41 46 47
8 12 15 23 24 37
8 12 18 24 27 43
8 15 16 35 43 46
8 16 27 30 37 46
9 11 17 25 42 48
9 11 20 21 45 49
9 11 26 32 33 40
9 11 28 31 38 39
9 14 17 20 26 28
9 14 21 25 31 32
9 14 33 38 42 45
9 14 39 40 48 49
10 15 18 22 23 34
10 15 27 35 44 47
10 18 29 35 41 43
10 18 30 37 44 47
10 22 27 30 34 43
10 23 27 29 37 41
11 14 17 21 33 39
11 14 20 25 38 40
11 14 26 31 42 49
11 14 28 32 45 48
12 13 16 22 29 44
12 13 16 22 41 47
13 24 29 34 46 47
13 24 34 41 44 46
15 18 23 29 36 41
15 19 22 34 37 43
15 19 27 29 35 41
15 36 37 43 44 47
17 20 33 40 45 48
17 20 38 39 42 49
17 21 26 32 48 49
17 21 28 31 42 45
17 25 26 31 39 40
17 25 28 32 33 38
18 19 29 30 37 41
18 19 35 43 44 47
18 22 34 35 36 43
19 22 23 30 34 35
19 23 27 37 44 47
20 21 26 31 33 38
20 21 28 32 39 40
20 25 26 32 42 45
20 25 28 31 48 49
21 25 33 40 42 49
21 25 38 39 45 48
22 23 27 34 36 37
22 24 29 44 46 47
23 30 35 36 44 47
26 28 33 39 45 49
26 28 38 40 42 48
27 29 30 36 41 43
31 32 33 39 42 48
31 32 38 40 45 49
Uenal Mutlu
Herbststr. 34
D-82178 Puchheim
Germany