# Pairwise Balanced Design of Order6n+4 and 2-Fold System of Order 3n+2

Authors: Manjusri Basu; Debabrata Kumar Ghosh; Satya Bagchi
Journal: ISRN Discrete Mathematics
 (2012)

---

## Abstract

In the Steiner triple system, Bose (1939) constructed the2−(v,3,1) design for v=6n+3 and later on Skolem (1958) constructed the same for v=6n+1. In the literature we found a pairwise balanced design (PBD) for v=6n+5. We also found the 2-fold triple system of the orders 3n and 3n+1. In this paper, we construct a PBD for v=6n+4 and a 2-fold system of the order 3n+2. The second construction completes the 2-fold system for all n∈N.


---

## Body

## 1. Introduction

A Latin square of ordern is an n×n array, each cell of which contains exactly one of the symbols in {1,2,…,n}, such that each row and each column of the array contain each of the symbols in {1,2,…,n} exactly once. A latin square is said to be idempotent if  cell (i,i) contains symbol i for 1≤i≤n. A latin square of order 2n is said to be half-idempotent if for 1≤i≤n cells (i,i) and (n+i,n+i) contain the symbol i. A latin square is said to be commutative if cells (i,j) and (j,i) contain the same symbol, for all 1≤i,j≤n.A quasi-group of ordern is a pair (Q,∘), where Q is a set of size n and “∘” is a binary operation on Q such that for every pair of elements a,b∈Q the equations a∘x=b and y∘a=b have unique solutions. As far as we are concerned a quasi-group is just a latin square with a headline and a sideline.At-(v,k,λ) design is an ordered pair (X,B) where X is a v set of points and B, called a block set, is of k subsets of X with the property that every t subset of X is contained in exactly λ blocks [1]. A t-(v,k,1) design is defined as a Steiner system and denoted by S(t,k,v). A Steiner triple system (STS) 2-(v,3,1) is an ordered pair (S,B), where S is a finite set of points or symbols, and B is a set of 3-element subsets of S called triples, such that each pair of distinct elements of S occurs together in exactly one triple of B. The order of a Steiner triple system (S,B) is the size of the set S, denoted by |S|=v.Theorem 1.1 (see [2, Theorem 1.1.3]).
A Steiner triple system of orderv exists if and only if v≡1 or 3(mod6).The Bose Construction (v≡3(mod6), see [2, 3])
Letv=6n+3 and let (Q,∘) be an idempotent commutative quasi-group of order 2n+1, where Q={1,2,…,2n+1}. Let S=Q×{1,2,3}), and define B to contain the following two types of triples.Type 1.
For1≤i≤2n+1, {(i,1),(i,2),(i,3)}∈B (see Figure 2).Type 2.
For1≤i≤2n+1, {(i,1),(j,1),(i∘j,2)},{(i,2),(j,2),(i∘j,3)},{(i,3),(j,3),(i∘j,1)}∈B (see Figure 2).Then(S,B) is a Steiner triple system of order 6n+3.The Skolem Construction (v≡1(mod6), see [2, 4])
Letv=6n+1 and let (Q,∘) be a half idempotent commutative quasi-group of order 2n, where Q={1,2,…,2n}. Let S={∞}∪(Q×{1,2,3}), and define B as follows.Type 1.
For1≤i≤n,{(i,1),(i,2),(i,3)}∈B.Type 2.
For1≤i≤n,{∞,(n+i,1),(i,2)},{∞,(n+i,2),(i,3)},{∞,(n+i,3),(i,1)}∈B.Type 3.
For1≤i≤2n,{(i,1),(j,1),(i∘j,2)},{(i,2),(j,2),(i∘j,3)},{(i,3),(j,3),(i∘j,1)}∈B (see Figure 3).Then(S,B) is a Steiner triple system of order 6n+1.Fort a positive integer, a t-wise balanced design D is an ordered pair (S,B), where S is a finite nonempty set (of points) and B is a finite nonempty multiset of subsets of S (called blocks), such that every t subset of S is contained in a constant number λ>0 of blocks. If v=|S| and K is the set of sizes of the blocks, then we call D a t-(v,K,λ) design. If all blocks of D have the same size k (i.e., K={k}), then D is called a t design or a t-(v,k,λ) design. A pairwise balanced design of order v with block sizes from K is a pair (S,B), B is a family of subsets (blocks) of S that satisfy (1) if Bi∈B, then |Bi|∈K and (2) every pair of distinct elements of S occurs in exactly λ blocks of B.The6n+5 Construction (see [2])
Let(Q,∘) be an idempotent commutative quasi-group of order 2n+1, where Q={1,2,…,2n+1} and let α be the permutation (1)(2,3,…,2n+1). Let S={∞1,∞2}∪(Q×{1,2,3} and let B contain the following blocks.Type 1.
{
∞
1
,
∞
2
,
(
1,1
)
,
(
1,2
)
,
(
1,3
)
}.Type 2.
{
∞
1
,
(
2
i
,
1
)
,
(
2
i
,
2
)
}
,
{
∞
1
,
(
2
i
,
3
)
,
(
(
2
i
)
α
,
1
)
}
,
{
∞
1
,
(
(
2
i
)
α
,
2
)
,
(
(
2
i
)
α
,
3
)
},{∞2,(2i,1),((2i)α-1,3)}, for 1≤i≤n.Type 3.
{
(
i
,
1
)
,
(
j
,
1
)
,
(
i
∘
j
,
2
)
}
,
{
(
i
,
2
)
,
(
j
,
2
)
,
(
i
∘
j
,
3
)
}
,
{
(
i
,
3
)
,
(
j
,
3
)
,
(
(
i
∘
j
)
α
,
1
)
} for 1≤i≤2n+1.Then(S,B) is a PBD(6n+5) with exactly one block of size 5 and the rest of size 3.Aλ-fold triple system is a pair of (S,B), where S is a finite set and B is a collection of 3-element subsets of S called triples such that each pair of distinct elements of S belongs to exactly λ triples of B.Theorem 1.2 (see [2, Theorem 2.3.7]).
The spectrum of2-fold triple systems is precisely the set of all v≡0 or 1(mod3).3
n Construction (see [2])
Let(Q,∘) be an idempotent (not necessarily commutative) quasi-group, where Q={1,2,…,n}. Let S=Q×{1,2,3}. We denote B which contains the following two types of triples.Type 1.
{
(
x
,
1
)
,
(
x
,
2
)
,
(
x
,
3
)
} occurs exactly twice in B for all x∈Q.Type 2.
Forx≠y, the six triples, {(x,1),(y,1),(x∘y,2)},{(y,1),(x,1),(y∘x,2)},{(x,2),(y,2),(x∘y,3)},{(y,2),(x,2),(y∘x,3)},{(x,3),(y,3),(x∘y,1)},{(y,3),(x,3),(y∘x,1)}∈B.Then(S,B) is a 2-fold triple system of order 3n.3
n
+
1 Construction (see [2, 4])
Let(Q,∘) be an idempotent (not necessarily commutative) quasi-group, where Q={1,2,…,n}. Let S={∞}∪(Q×{1,2,3}). We denote B which contains the following two types of triples.Type 1.
The four triples{∞,(x,1),(x,2)},{∞,(x,2),(x,3)},{∞,(x,1),(x,3)},{(x,1),(x,2),(x,3)}∈B for all x∈QType 2.
Ifx≠y, the six triples {(x,1),(y,1),(x∘y,2)},{(y,1),(x,1),(y∘x,2)},{(x,2),(y,2),(x∘y,3)},{(y,2),(x,2),(y∘x,3)},{(x,3),(y,3),(x∘y,1)},{(y,3),(x,3),(y∘x,1)}∈B.Then(S,B) is a 2-fold triple system of order 3n+1.


## 2. Main Results

6
n
+
4 Construction
Let(Q,∘) be an idempotent commutative quasi-group of order 2n+1, where Q={1,2,…,2n+1}. Now we construct (S,B) where S={∞}∪{Q×{1,2,3}} and B contains the following blocks.Type 1.
{
∞
,
(
i
,
1
)
,
(
i
,
2
)
,
(
i
,
3
)
}
∈
B, for 1≤i≤2n+1.Type 2.
{
(
i
,
1
)
,
(
j
,
1
)
,
(
i
∘
j
,
2
)
}
,
{
(
i
,
2
)
,
(
j
,
2
)
,
(
i
∘
j
,
3
)
}
,
{
(
i
,
3
)
,
(
j
,
3
)
,
(
i
∘
j
,
1
)
}
∈
B for 1≤i<j≤2n+1.Theorem 2.1.
The ordered pair(S,B) is a pairwise balanced design 2-(6n+4,{4,3},1).Proof.
The number of pointsv is 6n+4 (see Figure 1). The blocks of Type 1 are of length 4, whereas the blocks of Type 2 are of length 3. It is clear from the construction that any pair of points of S occurs in exactly one block. Hence (S,B) is a PBD 2-(6n+4,{4,3},1).
The number of blocks of the PBD2-(6n+4,{4,3},1) are (2n+1)+(3.2n+1C2)=(2n+1)(3n+1).Graphical representation of(6n+4) construction.
(a)
(b)Graphical representation of(3n+2) construction (Type 1 and Type 2).
(a)
(b)Figure 3
Graphical representation of(3n+2) construction (Type 3).For example,n=2,thatis,v=6.2+4=16, the quasi-group of order 5 is
(2.1)o12345115234252413324351431542543125
Let S={∞,1,2,…,15} and B contains the following blocks.Type 1.
{
∞
,
1,6
,
11
}
,
{
∞
,
2,7
,
12
}
,
{
∞
,
3,8
,
13
}
,
{
∞
,
4,9
,
14
}
,
{
∞
,
5,10,15
}
∈
B.Type 2.
{
1,2
,
10
}
,
{
1,3
,
7
}
,
{
1,4
,
8
}
,
{
1,5
,
9
}
,
{
2,3
,
9
}
,
{
2,4
,
6
}
,
{
2,5
,
8
}
,
{
3,4
,
10
}
,
{
3,5
,
6
}, {4,5,7},{6,7,15},{6,8,12},{6,9,13},{6,10,14},{7,8,14},{7,9,11},{7,10,13},{8,9,15},{8,10,11},{9,10,12},{11,12,5},{11,13,2},{11,14,4},{11,15,4},{12,13,4},{12,14,1},{12,15,3},{13,14,5},{13,15,1},{14,15,2}∈B.So (S,B) is a PBD2-(16,{4,3},1) with a total of 35 blocks in which 2.2+1(=5) blocks of size 4 and 3.5C2(=30) blocks of size 3.3
n
+
2 Construction
Let(Q,∘) be an idempotent (not necessarily commutative) quasi-group, where Q={1,2,…,n}. Let S={∞1,∞2}∪(Q×{1,2,3}). We define B as follows.Type 1.
{
∞
1
,
∞
2
,
(
1,1
)
,
(
1,2
)
,
(
1,3
)
} occurs exactly twice in B.Type 2.
For1≤x≤n, {∞1,(x,1),(x,2)},{∞1,(x,2),(x,3)},{∞1,(x,1),(x,3)},{∞2,(x,1),(x,2)},{∞2,(x,2),(x,3)},{∞2,(x,1),(x,3)}∈B for all x∈Q.Type 3.
Ifx≠y, the six triples {(x,1),(y,1),(x∘y,2)},{(y,1),(x,1),(y∘x,2)},{(x,2),(y,2),(x∘y,3)},{(y,2),(x,2),(y∘x,3)},{(x,3),(y,3),(x∘y,1)},{(y,3),(x,3),(y∘x,1)}∈B.Theorem 2.2.
The ordered pair(S,B) is a 2-fold system of order 3n+2.Proof.
The number of points isv=3n+2. The Type 1 of new (S,B) construction consists of block length 5. The Type 2 and Type 3 of the above construction consist of length 3. Any pair of points of S occurs in exactly two blocks. Hence the construction (S,B) is a 2-fold system. Also the ordered pair (S,B) holds 2-(3n+2,{3,5},2) design.For example,n=4, the quasi-group of order 4 is
(2.2)o123411342242133243143124
Let S={∞1,∞2,1,2,…,12} and B contains the following blocks.Type 1.
{
∞
1
,
∞
2
,
1,5
,
9
}, {∞1,∞2,1,5,9}∈B.Type 2.
{
∞
1
,
2,6
}
,
{
∞
1
,
2,10
}
,
{
∞
1
,
6,10
}
,
{
∞
1
,
3,7
}
,
{
∞
1
,
7,11
}
,
{
∞
1
,
3,11
}
,
{
∞
1
,
4,8
},{∞1,8,12},{∞1,4,12},{∞2,2,6},{∞2,2,10},{∞2,6,10},{∞2,3,7},{∞2,7,11},{∞2,3,11}, {∞2,4,8},{∞2,8,12},{∞2,4,12}∈B.Type 3.
{
1,2
,
7
}
,
{
2,1
,
8
}
,
{
1,3
,
8
}
,
{
3,1
,
6
}
,
{
1,4
,
6
}
,
{
4,1
,
7
}
,
{
2,3
,
5
}
,
{
3,2
,
8
}
,
{
2,4
,
7
}
,
{
4,2
,
5
},{3,4,5},{4,3,6},{5,6,11},{6,5,12},{5,7,12},{7,5,10},{5,8,10},{8,5,11},{6,7,9},{7,6,12},{6,8,11},{8,6,9},{7,8,9},{8,7,10},{9,10,3},{10,9,4},{9,11,4},{11,9,2},{9,12,2}, {12,9,3},{10,11,1},{11,10,4},{10,12,3},{12,10,1},{11,12,1},{12,11,2}∈B.So(S,B) is a PBD 2-(14,{5,3},1) with 2 blocks of size 5 and the rest of the blocks of size 3.


## 3. Conclusion

There already exist STS forv=6n+1 and v=6n+3 and PBD for v=6n+5. In this paper, we construct PBD for v=6n+4. The PBD for v=6n and, v=6n+2 is still now open. The 2-fold triple system exists for v≡0 or  1(mod3) and, in this paper, we construct 2-fold system exits for 3n+2. These complete that the 2-fold system holds for all natural numbers n.



---

*Source: 251457-2012-12-27.xml*