Science Journal of Applied Mathematics and Statistics
Volume 5, Issue 1, February 2017, Pages: 49-53

Construction of Some Resolvable t-designs

Alilah David

Department of Mathematics, Masinde Muliro University of Science and Technology, Nairobi, Kenya

Email address:

To cite this article:

Alilah David. Construction of Some Resolvable t-designs. Science Journal of Applied Mathematics and Statistics. Vol. 5, No. 1, 2017, pp. 49-53. doi: 10.11648/j.sjams.20170501.17

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


Abstract: The 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 t 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. In this study t-design is constructed by relating known BIB designs, combinatorial designs and algebraic structures with t-designs. Additionally, an alternative approach for the construction of t-designs that provides a unified framework is also presented.

Keywords: Block Designs, Resolvable Designs, t-designs


1. Introduction

A  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 [2].

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 Ray-Chaudhuri [14] and Wilson [16]. 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 [14].

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 [7]. When, these designs are known as inversive planes. A Steiner quadruple system  is also known to exist for all . Some simpledesigns, 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 ,  by identifying BIB designs which are also designs [5].

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. In the case of , Kageyama [11] 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.

Mathon and Rosa [12] 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.

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 . 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.

A block design is a family of  subsets of a set  of  elements such that, for some fixed  and , with ,; each subset has  elements, and each pair of elements of  occurs together in exactly  subsets. The elements of  are called varieties, and the subsets of  are called the blocks. From Anderson [2], in a block design each element lies in exactly  blocks, where

and(1)

The five parameters  of a block design are therefore not independent, but have two restrictions as stated in the theorem. Whatever  are, they must satisfy (1), but conversely if five numbers  satisfy (1.1), there is no guarantee that a configuration exists as described by [15].

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 [16] on his part constructed designs with  and  from balanced incomplete block design.

Incidence Matrix

The incidence matrix  of a -BIBD satisfies the following properties: every column of  contains exactly "1"s; every row of  contains exactly "1"s; and two distinct rows of  contain "1" in exactly  columns

Theorem (Stinson (2004)). Let  be a 0-1 matrix and let . Then  is an incidence matrix of a-BIBD if and only if and  where  denotes a  unity matrix and  denotes a  matrix with every entry equal to 1.

Example of constructing BIB designs

Now consider , the conditions are fulfilled with;

Let the points be A, B, C, D, E, F, and G. Ordering the 3 blocks with A first and assume that B-C, D-E and F-G are together in these blocks. The following results are obtained:

Table 1. Results of Step one.

A A A
B D F
C E G

Second step

Next B and C must occur twice more and not together (order of blocks not important). The result is:

Table 2. Results of Step two.

A A A B B C C
B D F        
C E G        

Third step

D and F must occur together. We can assume this happens in a B block. The E and G must be together in the other B block. Then there is only one choice for the two C blocks (because order is unimportant). Results obtained are:

Table 3. -configuration.

A A A B B C C
B D F D E D E
C E G F G G F

When using this design for practical experiments randomization is a must. Treatments according to the labels will be randomized as per the order of the blocks, and the order of the three treatments within a block. The complementary design is constructed by replacing each block with a block consisting of the remaining points. For this case this results in:

Table 4. Complementary design.

D B B A A A A
E C C C C B B
F F D E D E D
G G E G F F G

Results obtained are  and . It is noted that the same BIB designs can be constructed by use of PG (2, 2).

3. Construction of Resolvable 3-(v, k, λt) Design

In this construction, technique introduced by Adhikari [1] of using the symmetric differences of pairs of blocks of incomplete blocks designs to construct other designs and the technique of arithmetic of integers modulo nis applied.

3.1. Resolvable 3-design with Parameters v=8,b=14,r=7,k=4,λ2=3,λ3=1

Consider resolvable 3-design with parameters

Let  be the set of equivalence classes mod 7 and  and  form a base for a (14, 8, 7, 4, 3)  cyclic design mod 7. When2 is added to each element of  and  and same process is continued, blocks of the design are obtained as follows;

Replacing residues with integers and  with 8, the following results are obtained;

Computing the differences modulo 7 and from pairs of distinct elements in , the following values of the block designs are obtained:

3-1 = 2 1-3 = 5 2-0 = 2 0-2 = 5
4-1 = 3 1-4 = 4 5-0 = 5 0-5 = 2
∞-1 = ∞ 1-∞ = -∞ 6-0 = 6 0-6 = 1
4-3 = 1 3-4 = 6 5-2 = 3 2-5 = 4
∞-3 = ∞ 3-∞ = -∞ 6-2 = 4 2-6 = 3
∞-4 = ∞ 4-∞ = -∞ 6-5 = 1 5-6 = 6

This results in ∞, -∞ and each non zero residue mod 7 exactly thrice as a difference of two elements in . This design is a (14,8,7,4,3)- BIBD which would result into a 3-(8,4,1) design.

3.2. Construction of t-design with Parameters v=12,b=22,r=11,k=6,λ2=5,λ3=2

Affine 3-design with parameters

Let  is the set of equivalence classes mod 11 and  and  then  is a base for the design.

Replacing residues with integers and  with 12, the following results are obtained;

Case of

Construction of  where

If  is the set of equivalence classes mod 7 and , and

Following the same procedure, design below with integers as elements is obtained;

Construction of  design where 

If  is the set of equivalence classes mod 7 and  and

Using the same procedure, the design below with integers as elements is obtained.

Case of

Construction of  where

Let  is the equivalence classes’ mod 11 and  and  then  is the base for the design below with integers as elements:

This construction is equivalent to "sum construction ", of BIBDs, but in this case a BIBD is added to a BIBD that is automorphic to it. Therefore new BIBDs can be formed by the collection of a BIBD with its automorphic BIBDs.

4. Conclusion

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 . The construction framework designed provides a platform at which new BIBDs can be formed by the collection of a BIBD with its automorphic BIBDs. In order to obtain combinatorial constructions of unique block designs, different kind of combinatorial designs are very effective.

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.


References

  1. Adhikari, B. (1967). On the symmetric differences of pairs of blocks of incomplete blockdesigns, Calcutta stat. Assoc. Bull 16, 45-48.
  2. Blanchard, J. (1995a). A construction for Steiner 3-designs, Journal of combinatorialTheory A, 71, 60-67.
  3. Blanchard, J. (1995c).A construction for orthogonal arrays with strength t ∶ 3, Discretemath 137, no. 1-3, 35-44.
  4. Cameron, P., Maimani, H. R., Omidi, G.R., and Tayfeh-Rezaie, B. (2006). 3-designs PGL(2, q), Discrete Mathematics, 306, vol.23, 3063-3073.
  5. Colbourn, C. (2002). Orthogonal arrays of strength three from regular 3-wise balanceddesigns.
  6. Hartman, A. (1994). The fundamental construction for 3-designs. Discrete math 124, no. 1-3, 107-131.
  7. Kageyama, S. (1991). A property of t-wise balanced designs, Ars. Combinatorial, 31, pp237-238.
  8. Mathon, R. and Rosa,A.(1985). Tables of paramenters of BIBds withr÷41includingexistence, enumeration and resolvability results. Annals of Discretemathematics 26, 275-308.
  9. Mcsorley, J., and Soicher, L. (2005). Construction of t-designs from a t-wise balanceddesign, Eur.J.Comb.to appear.
  10. Mohácsy, H., and Ray-Chaudhuri, D. (2001). A construction for infinite families ofSteiner 3-designs, Journal of Combinatorial Theory A, 94, 127-141.
  11. Mohácsy, H., and Ray-Chaudhuri, D. (2002). Candelabra Systems and designs, Journal ofStatistical planning and Inference, 106, 419-448.
  12. Mohácsy, H., and Ray-Chaudhuri, D. (2003). A construction for group divisible t-designswith strength t ∶ 2 and index unity, Journal of Statistical planning and Inference, 109, 167-177.
  13. Onyango, O. (2010).Construction of t-(v, k, ルt) designs, Journal of mathematicalscience, vol. 21 no. 4 pp 521-526.
  14. Ray-Chaudhuri, D. and Wilson, R. (1975). "On t-designs", Osaka, J.Math, 12, 737-744.
  15. Stinson, D. (2004). Combinatorial Designs: Construction and Analysis, Springer_Verlag,New York, Inc., New York.
  16. Wilson, R (1972a). An existence theory for pairwise balanced designs I. Compositiontheorems and Morphisms, Journal of Combinatorial Theory A, 13, 220-245.

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