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