American Journal of Theoretical and Applied Statistics
Volume 6, Issue 1, January 2017, Pages: 52-60

Construction Procedure for Non-trivial T-designs

John Chibayi1, David Alila2, Fredrick Onyango1

1Department of Statistics and Actuarial Science, MasenoUniverisity, Nairobi, Kenya

2Department of Mathematics, MasindeMuliro University of Science and Technology, Nairobi, Kenya

Email address:

(J. Chibayi)
(D. Alila)
(F. Onyango)

To cite this article:

John Chibayi, David Alila, Fredrick Onyango. Construction Procedure for Non-trivial T-designs. American Journal of Theoretical and Applied Statistics. Vol. 6, No. 1, 2016, pp. 52-60. doi: 10.11648/j.ajtas.20170601.17

Received: July 20, 2016; Accepted: August 8, 2016; Published: January 22 , 2017


Abstract: A t-design is a generation of balanced incomplete block design (BIBD) where λ is not restricted to the blocks in which a pair of treatments occurs but to the number of blocks in which any treatments (t = 2,3...) occurs. The problem of finding all parameters (t, v, k, λt) for which t-(v, k, λt) design exists is a long standing unsolved problem especially with λ=1 (Steiner System) as no Steiner t-designs are known for t 6 when v > k. The objective of this study therefore to develop new methods of constructing t-designs with t ≥ 3 and λ ≥ 1. In this study t-design is constructed by relating known BIB designs, combinatorial designs and algebraic structures with t-designs.

Keywords: Block Designs, Steiner Systems, T-designs


1. Introduction

design is an incidence structure of points and blocks with the following properties; there are points, each block is incident with points, any point is incident with blocks, and any points are incident to common blocks. Where and are all positive integers and . The four numbers and determine (blocks) and and four numbers themselves cannot be chosen arbitrarily. For a design and is any -element subset of , with , then the number of blocks containing is given by:

(1)

particular, . Since in equation above needs to be an integer, only the values of and that make an integer for all are admissible parameters for a design. A tuple is said to be admissible if the arithmetic conditions aforementioned hold and is said to be feasible if a design exists, hence a feasible tuple is necessarily admissible [2]. The converse is not true. That is, admissibility conditions are necessary but they are not sufficient, there exist several cases of parameters that satisfy the admissibility conditions and yet no design with these parameters exists. However, it is conjectured that admissibility conditions would be sufficient, if the point set is large. This is known as large existence conjecture or ''asymptotic existence''conjecture.

The incidence structure associated with a design can be represented by a matrix. The point-block incidence matrix , associated with a design with blocks is a matrix of rows and columns. The elements of are where is the point, is the block and

There is a generalization of Fisher's inequality to designs which is due to [1]. If a design exists, where is even, then the number of blocks . A design in which is called Steiner system. For example a is a Steiner triple system (STS) and a design is a Steiner quadruple system (SQS). A design is called a balanced incomplete block design (BIBD). A t-design is said to have repeated blocks if there are two blocks incident with the same set of k points. A t-design with no repeated blocks is said to be simple [6].

A design with are known for only a few values of and . For there are several infinite families known. For instance, for any prime power and for any , there exists a design known as inversive geometry. When , these designs are known as inversive planes. A Steiner quadruple system is also known to exist for all . Some simple designs, have been constructed for . Construction of a design remains one of the outstanding open problems in the study of t-designs. Even for and , only a few examples of designs are known. In this study we construct some designs, with much emphasis on t , by identifying BIB designs which are also designs.

2. Literature Review

The main problem in designs is the question of existence and the construction of those solutions, given admissible parameters. That is, finding all parameters for which design exists. There are many known Steiner designs but constructing Steiner it has proved to be much harder. Wilson (1972a,1972b) building upon the work of many including ([3], [7], [10], and [11]) proved for , fixed k and sufficiently large v satisfying arithmetic conditions designs exist. There is no similar existence result yet for . In the case of , [4] has shown thatthere is design if andonly if the necessary arithmetic conditions are satisfied. But for larger k, even , the result is far from complete. For the problem is wide open. All these constructions bear a distinct algebraic flavor in the sense that the underlying set upon which the design is constructed has a nice algebraic structure. Algebraic construction requires that a certain fixed (big) group to act as a group of automorphisms for the desired design. This technique was first formulated on paper by [11].

However this method culminates in a computer or computer-like brute-force search which cannot take us very far in quest for new designs (especially Steiner designs). Cameron et al. [5] simplified this method, by coming up with a technique that employs transitive actions of groups. They showed that, if a group acts transitively on subsets of size tthe orbits for that group yield designs.

Stinson [15] came up with block spreading method for and for prime power index. Let be a positive integer and let be a prime power. Suppose that there exists a design satisfying . Then there exists a group divisible design (GDD) of group type with block size and index one, whenever . This method has application in the construction of Steiner designs. Blanchard ([3], [7], [14]) generalizes Hartman's [14] results for as follows: (The ''block spreading'' method for and for prime power index). Let and be positive integers, , and let be a prime power. Then there exists a number such that for any design satisfying , there is a GDD of group type with block size and index one whenever . More so, ([5], [8]) generalizes Blanchard's construction for general index (the ''block spreading'' method for and general index). Let and be a positive integers . Then there exists a number such that for any design with prime power decomposition satisfying ; ; there is a GDD of group type with block size and index one whenever . This generalized ''block spreading'' construction has several application such as constructing new Steiner designs and new group divisible designs with index one. Limitation of this method is that the bounds on are too large.

Magliveras et al. [9] constructed some new large sets of t-designs, using recursive construction described by Qiu-rong Wu [14]. Wu [14] showed that if there exists large sets , , ,), then there exists a large set . He went on to show that also, if there exist a large sets and then there exist large sets for all .

Mohácsy and Ray-Chaudhuri [12] constructed designs from known wise balanced designs. In his works he showed that, given a positive integer and a design , with all blocks-sizes occurring in and , the construction produces a design , with . Onyango [13] on his part constructed designs with and from balanced incomplete block design.

3. Construction of Some Designs with

The properties of designs include:

(2)

(3)

Replacing in equation (2) we have:

(4)

Now when we have:

(5)

This implies

(6)

Given that are all integers and is a rational number which we will represent by where are positive integers. Thus the equations (5) become:

and (7)

Case 1: When

Then (6) becomes: ,

,

Theorem 1: If , where is an integer then there are only three non- trivial designs which are:

Proof: From (2), (3), and (7)

(8)

This implies: and . For this design to be design and from (1) it implies

That is:

(9)

which is a positive integer. Expanding and simplifying equation (9), we obtain

(10)

The last term of equation (10), that is

(11)

will be an integer if . The only values for in which this is possible are 1 and 2. In this case Equation (11) is not an integer. Thus both Equations (10) and (11) will be integers if takes the values 2, 3, 5 and 11. The table below gives corresponding values of .

Table 1. Case1; for the possible cases of designs.

λ2 k λ1 v b
2 3 3 4 4
3 4 7 8 14
5 6 21 22 77
11 12 111 112 1036

The required designs are; . A is trivial given , but it is required that , hence is not included and our proof is completed.

Case 2: When

In this case Equation (6) becomes

and

Where is a positive integer and both are divisible by .

From Equation (1) we get as follows;

,

and

(12)

Using for this design to be design then:

(13)

That is

(14)

which is a positive integer. Expanding and simplifying equation (14), we obtain

(15)

Equation (15) will be and integer ifthe last term is an integer. Thus can take any of the following values 3,4,6,8,10,18,28,32,38,58, and 118. But must be divisible by 2. So 3 is not a possibility. We give corresponding values of in the Table 2 below.

Table 2. Case 2; for the possible cases of designs.

λ2 k λ1 v b
4 3 10 6 20
6 4 26 14 91
8 5 50 26 260
10 6 82 42 574
18 10 290 146 4234
22 12 442 222 8177
28 15 730 366 17812
38 20 1370 686 46991
58 30 3250 1626 176150
118 60 13690 6846 1562029

Thefollowing designs can then be obtain from BIB designs given below

For , the possible values are: 6,9,15,18,21,33,39,60,69,81,123,165,249, and 501. The corresponding values of in the Table 3 below.

Table 3. Case2; for the possible cases of designs.

λ2 k λ1 v b
6 3 21 8 56
9 4 57 20 285
15 6 183 62 1891
18 7 273 92 3588
21 8 381 128 6096
33 12 993 332 27473
39 14 1407 470 47235
60 21 3423 1142 186146
69 24 4557 1520 288610
81 28 6321 2108 475881
165 56 26733 8912 4254366
249 84 61257 20420 14891285
501 168 249501 83168 123514876

Again we obtain designs from BIB designs below:

For , and using similar arguments as before we obtain possible values of as follows:8,12,16,20,28,32,36,....which give the values of as follows:

Table 4. Case2; for the possible cases of designs.

λ2 k λ1 v b
8 3 36 10 120
12 4 100 26 650
16 5 196 50 1960
20 6 324 82 4428
28 8 676 170 14365
32 9 900 226 22600
36 10 1156 290 33524

The desired designs are obtained from the following BIB designs:

Remark: this construction can go on and on by simply varying the values of for each case, but as values of increases the designs obtained have large parameters making them not practical.

4. Construction of Designs with t=3 and λ t ≥1

We extend the work in [10] by constructing designs with , that is for general indexand Steiner designs. When and from Equation (2) we have:

and

(16)

Where is a rational number since are all positive integers hence, we will represent it by where are positive integers.

Case I,

Then Equation (15) becomes:

and (17)

For this design to be design and from ; it implies

(18)

That is,

(19)

Expanding and simplification of Equation (19)we obtain

(20)

Which will be an integer if divides . For , that is , the only possible values for in which this is possible are 1 and 2. Thus Equation (20) will be an integer if takes only of the following values; 2 and 5. The table below gives corresponding values of

Table 5. Case 1; for the possible cases of designs.

λ2 k λ1 v b
2 3 2 3 2
5 6 11 12 22

The first does not exist hence we have only one design in this case.

This is identified with this BIB design .

CASE II,

In this case Equation (17) becomes:

and (21)

Using similar argument as before:

Will be integer if Equation (22) is and integer

(22)

We give the corresponding values of in Table 6 below;

Table 6. Case 2; for the possible cases of designs.

λ2 k λ1 v b
4 3 6 4 8
6 4 14 8 28
10 6 42 22 154
14 8 86 44 473
22 12 222 112 2072
46 24 1014 508 21463

The following designs; can be obtained from designs given below:

For and using similar arguments as before we give the values of as in Table 7 below:

Table 7. Case 2; for the possible cases of designs.

λ2 k λ1 V B
6 3 12 5 20
12 5 57 20 228
15 6 93 32 496
27 10 327 110 3597

We get the desired designs from BIB designs below:

For and using the same methods we give the table of values of; as follows:

Table 8. Case 2; for the possible cases of designs.

λ2 k λ1 v b
8 3 20 6 40
12 4 52 14 182
16 5 100 26 520
20 6 168 42 1126
36 10 580 146 8468
44 12 884 222 16354
56 15 1460 366 35624

Similarly, for the values of we give them as in the Table 9 below:

Table 9. Case 2; for the possible cases of designs.

λ2 k λ1 v b
10 3 30 7 70
20 5 155 32 992
25 6 255 52 2210
30 7 380 77 4180
65 14 1955 392 54740

Now, for and applying the same methods, we give values of in table 10 below respectively.

Table 10. Case 2; for the possible cases of designs.

λ2 k λ1 v b
6 3 9 4 12
9 4 21 8 42
15 6 63 22 231
24 9 171 58 1102
51 18 819 274 12467

Table 11. Case 2; for the possible cases of designs.

λ2 k λ1 v b
12 3 30 6 60
18 4 78 14 273
24 5 150 26 780
30 6 246 42 1722

Also for and using similar arguments, we give values of in the Tables below respectively.

Table 12. Case 2; for the possible cases of designs.

λ2 k λ1 v b
4 3 4 3 4
6 4 8 5 10
10 6 22 12 44
22 12 112 57 532

The first design is trivial.

Table 13. Case 2; for the possible cases of designs.

λ2 k λ1 v b
12 4 28 8 56
20 6 84 22 308
28 8 172 44 946

Table 14. Case 2; for the possible cases of designs.

λ2 k λ1 v b
18 4 60 11 165
24 5 114 20 456
30 6 186 32 992

When and using similar methods the values of we give them in the tables below respectively.

Table 15. Case 2; for the possible cases of designs.

λ2 k λ1 v b
15 4 35 8 70
20 5 65 14 182
25 6 105 22 385
45 10 365 74 2701

Table 16. Case 2; for the possible cases of designs.

λ2 k λ1 v b
30 4 130 14 455
40 5 250 26 1300
50 6 410 42 2870

or we get the following tables respectively.

Table 17. Case 2; for the possible cases of designs.

λ2 k λ1 v b
15 6 33 12 66
24 9 87 30 290
51 18 411 138 3151

Table 18. Case 2; for the possible cases of designs

λ2 k λ1 v b
18 4 42 8 84
30 6 126 22 462
42 8 258 44 1419

Also for we get the following table:

Table 19. Case 2; for the possible cases of designs.

λ2 k λ1 v b
21 4 49 8 98
35 6 147 22 539
42 7 217 32 992

Lastly, for we also get the following tables respectively.

Table 20. Case 2; for the possible cases of designs.

λ2 k λ1 v b
12 4 16 5 20
20 6 44 12 88
28 8 88 23 253
44 12 224 57 1064

Table 21. Case 2; for the possible cases of designs.

λ2 k λ1 v b
24 4 56 8 112
40 6 168 22 616
56 8 344 44 1892
88 12 888 112 8288

Case III,

Letting

and (23)

Where are positive integers and are divisible by and substituting these values of in:

We obtain as follows:

, and (24)

Using for this to be design then

That is Equation (24) is a positive integer

(25)

Expanding and simplifying Equation (24) we obtain

(26)

Under this case and using similar method we find exists if Equation (26) is an integer:

(27)

Taking in this case there is only one non-trivial and would take the values 5 or 35 with corresponding values of in the table below.

Table 22. Case 3; for the possible cases of designs.

λ2 k λ1 v b
5 3 5 3 5
35 15 230 93 1426

For , we get the following table:

Table 23. Case 3; for the possible cases of designs.

λ2 k λ1 v b
7 3 7 3 7
21 7 56 17 136

5. Construction of 4-(v,k,1) Designs

The same technique that has been used to construct is applied. When and , we have;

and (28)

Given are all integers, and is a rational number which we will represent by where are positive integers.

Case 1

Equation (28) becomes;

and (29)

Using Equation (29) and (30) we obtain

Which implies;

and (30)

For this design to be and from it means

Hence Equation (31) is a positive integer

(31)

Expanding Equation (31) we obtain

(32)

Equation (32) will be integer whenever Equation (33) is an integer

(33)

Using Equation (33), corresponding values of will be generated as shown in Table 12:

Table 24. Case 1; for the possible cases of 4 designs.

λ3 λ2 λ1 k v b
2 3 4 4 5 5
5 21 77 7 23 253

The first design is trivial. The is the only non trivial. This is then identified with the following BIB designs; and

Case 2,

In this case Equation (29) becomes

and (34)

For this design to be and from it means

Hence, equation (34) is a positive integer

(35)

Thus takes any of the following values 2 and 4. But must be greater than 2, hence 2 is not a possibility. We give corresponding values of in the table below.

Table 25. Case 2; for the possible case of 4 design.

λ3 λ2 λ1 k v b
4 10 20 4 7 35

This design is trivial. Hence, for there is no nontrivial design.

For , takes only 6 as its value. The corresponding values of are given in the table 26 below.

Table 26. Case 2; for the possible case of 4 design.

λ3 λ2 λ1 k v b
6 21 56 4 9 126

This design is trivial. Hence, also for there is no nontrivial design.

For , takes the values 8 and 28. The corresponding values of are given in the table below.

Table 27. Case 2; for the possible cases of 4 designs.

λ3 λ2 λ1 k v b
8 36 120 4 11 330
28 676 14365 9 171 272935

We obtain the desired designs from BIB designs below:

For and using similar arguments as before, the possible values of are as follows: which gives the values of as in the table below.

Table 28. Case 2; for the possible cases of 4 designs.

λ3 λ2 λ1 k v b
10 55 220 4 13 715
15 155 1240 5 33 8184
20 305 3782 6 63 39711

Case 3,

In this case Equation (28) can be rewritten as

, and ,(36)

Using Equation (28) we have

Which implies

(37)

For this design to be and from it means

That is Equation (38) is a positive integer

(38)

Using similar argument as before Equation (38) will be integer if Equation (39) is an integer

(39)

The corresponding values of is given in the table below.

Table 29. Case 3; for the possible case of 4 design.

λ3 λ2 λ1 k v b
3 6 10 4 6 15

This design is trivial. Hence, for there is no nontrivial design

Also for there is no non-trivial , the following table gives the corresponding values of .

Table 30. Case 3; for the possible case of 4 design.

λ3 λ2 λ1 k v b
5 6 35 4 8 70

In this case there is only one non- trivial . The following table gives the corresponding values of .

Table 31. Case 3; for the possible case of 4 design.

λ3 λ2 λ1 k v b
4 12 30 5 11 66

For equation (28) becomes

And the corresponding values of are as shown below.

Table 32. Case 3; for the possible cases of 4 designs.

λ3 λ2 λ1 k v b
4 10 20 4 7 35
6 26 91 5 15 273
8 50 260 6 27 1170
10 82 574 7 43 3526
22 442 8177 13 223 140267

For equation (3.4.3.2) becomes

In this case there is only one non- trivial . The following table gives the corresponding values of .

Table 33. Case 3; for the possible case of 4 design.

λ3 λ2 λ1 k v b
7 35 140 5 17 476

For equation (3.4.3.2) becomes

Also in this case, there is only one non- trivial . The following table gives the corresponding values of

Table 34. Case 3; for the possible case of 4 design.

λ3 λ2 λ1 k v b
40 1496 52547 17 563 1740233

For equation (3.4.3.2) becomes

And the corresponding values of are as shown below.

Table 35. Case 3; for the possible cases of 4 designs.

λ3 λ2 λ1 k v b
6 21 56 4 9 126
9 57 285 5 21 1197
15 183 1891 7 63 17019

6. Conclusion

In this study a new recursive technique has been developed for the construction of designs. Thus, the study has presented an alternative method that is simpler and unified for the construction of BIBDs that are very important in the experimental designs. As it provides designs for different values of , unlike many methods that provide designs for a single value of . More so, it provides both Steiner and non-Steiner designs.

Recommendations

Although this study has provided a technique for the construction of designs, it is still clear that construction method of designs is not known in general. In fact, it is not clear how one might construct designs with arbitrary block size. We therefore invite researchers to come up with ''additive theorems'' or this construction to make it general for any value of as this may bring in new techniques and ideas. There is also need for obtaining a theorem which would give all values of x and y for the case three in this construction in order to see new Steiner designs. Lastly, if there is a computer package that could be incorporated in the method to aid in calculations.


References

  1. Blanchard, J. L (1995a). A construction for Steiner 3-designs, Journal of combinatorial Theory A, 71, 60-67.
  2. Blanchard, J. L. (1995b). An extension theorem for Steiner systems, Discrete Mathematics 141, no. 1-3, 23-35.
  3. Blanchard, J. L (1995c). A construction for orthogonal arrays with strength t ≥ 3, Discrete math 137, no. 1-3, 35-44.
  4. Bogart, K. P. (1990). Introductory Combinatorics second edition, Harcourt Brace Bose, Jovanovich, Inc. Orlando, Florida.
  5. Cameron, P. J., Maimani, H. R., Omidi, G.R., and Tayfeh-Rezaie, B. (2006). 3-designs PGL (2, q), Discrete Mathematics, 306, vol. 23, 3063-3073.
  6. Colbourn, C.J.et al. (2002).Orthogonal arrays of strength three from regular 3-wise balanced designs.
  7. Dinitz, J. H., & Stinson, D. R. (1992).Contemporary Design Theory: A collection ofsurveys, Wiley-Interscience.
  8. Hartman, A. (1994). The fundamental construction for 3-designs. Discrete math 124, no.1-3, 107-131.
  9. Magliveras, S. S., Kramer, E. S., & Stinson, D. R. (1993). Some new Large sets of t-designs. Australasian journal of Combinatorics 7, pp 189-193.
  10. Mohácsy, H., and Ray-Chaudhuri, D. K. (2001). A construction for infinite families of Steiner 3-designs, Journal of Combinatorial Theory A, 94, 127-141.
  11. Mohácsy, H., and Ray-Chaudhuri, D. K. (2002). Candelabra Systems and designs, Journalof Statistical planning and Inference, 106, 419-448.
  12. Mohácsy, H., and Ray-Chaudhuri, D. K. (2003). A construction for group divisible t-designs with strength t ≥2 and index unity, Journal of Statistical planning and Inference, 109, 167-177.
  13. Onyango, O.F. (2010).Construction of t-(v, k, λt) designs, Journal of mathematical science, vol. 21 no. 4 pp 521-526.
  14. Qiu-rong Wu. (1991). A note on extending t-designs, Australasia. Journal of Combinatorics, 4 pp 229-235.
  15. Stinson, D. R. (2004). Combinatorial Designs: Construction and Analysis, Springer_Verlag, New York, Inc., New York.

Article Tools
  Abstract
  PDF(266K)
Follow on us
ADDRESS
Science Publishing Group
548 FASHION AVENUE
NEW YORK, NY 10018
U.S.A.
Tel: (001)347-688-8931