# A New Relationship between Block Designs

Authors: Alexander Shramchenko; Vasilisa Shramchenko
Journal: International Journal of Combinatorics
 (2016)

---

## Abstract

We propose a procedure of constructing new block designs starting from a given one by looking at the intersections of its blocks with various sets and grouping those sets according to the structure of the intersections. We introduce a symmetric relationship of friendship between block designs built on a setV and consider families of block designs where all designs are friends of each other, the so-called friendly families. We show that a friendly family admits a partial ordering. Furthermore, we exhibit a map from the power set of V, partially ordered by inclusion, to a friendly family of a particular type which preserves the partial order.


---

## Body

## 1. Introduction

We consider balanced incomplete block designs (BIBDs) (see [1–3]). With every block design one can associate some other block designs obtained using the original one. For example, given a block design D with blocks’ length k, one can form another block design by taking all subsets of length k
′
<
k of all the blocks of D. We suggest a new way of looking at relationships between block designs.We introduce a notion offriendship between block designs based on the structure of intersections between their blocks. More precisely, suppose that we choose a block of one of the two BIBDs and look at the intersections of this block with all the blocks of the other BIBD. Suppose also that the number of blocks of the second BIBD that give intersections of length n only depends on n and does not depend on our choice of a block of the first BIBD. Now, if the same is true after we interchange the roles of the two BIBDs, then they are calledfriends. This is quite a strong condition and we expect families of block designs that are friends of each other to possess interesting properties. We give examples of friends and study the question of when a block design is friends with itself.We call a family of block designs built on a setV which are pairwise friends afriendly family. On such a family we introduce a partial order. Furthermore, given that the power set of V is also partially ordered by inclusion, we show that there exists a map from the power set of V to a friendly family of a particular type which preserves the ordering.We also suggest studying families of block designs constructed using a common “parent” block design. In Section5, making use of a given block design built on a set V, we define an equivalence relation on the power set of the set V. We conjecture that if the given block design is a Desargues projective plane, then the constructed equivalence classes in the power set are block designs, which are pairwise friends; that is, they form a friendly family. Furthermore, we suggest using the procedure of intersecting the blocks of a BIBD by various sets as a way to generate new block designs. We describe a few cases when such a construction yields friends of the original block design.


## 2. Definitions and Notation

A balanced incomplete block design is defined as follows (see [1–3]).Definition 1.
LetV be a finite set of cardinality v
=
V and b, k, r, λ four positive integers. A block design with parameters v
,
b
,
r
,
k
,
λ built on V is a list of b blocks, each of which is a k-element subset of V, such that every element of V is contained in exactly r blocks and every pair of elements of V is contained in exactly λ blocks.We assume that all block designs are simple; that is, they have no repeated blocks. The notation we use is in accordance with [3].(i)
P
V is the power set of V, that is, the set of all subsets of V including the empty set and V itself, ordered by inclusion: for X
,
Y
⊂
V we say X
<
Y if and only if X
⊂
Y.
(ii)
D
i, i
∈
I, is a set of block designs, each of which is built on the set V and has parameters v
,
b
i
,
r
i
,
k
i
,
λ
i.
(iii)
D
i
s, s
=
1
,
…
,
b
i, stand for the blocks of the block design D
i.
(iv)
D
k is a full design of block size k built on the set V, that is, a block design with parameters v
,
v
k
,
r
,
k
,
λ whose set of blocks is the full set of combinations of k out of v elements. We assume that D
0 is the empty set and D
v
=
V
.Remark 2.
The parameters of a block design are not independent: one hasb
k
=
v
r and r
k
-
1
=
λ
v
-
1.


## 3. Friends of Block Designs

We are going to consider intersections of the blocks of a design by a given set and focus on the number of elements in these intersections. Let us consider a block designD built on a set V and some subset M of V. For j
≥
0, let z
j
∈
N stand for a number of blocks of D whose intersections with M contain exactly j elements. More precisely, we define(1)
z
j
=
∑
1
≤
s
≤
b
δ
M
∩
B
s
,
j
,where for two sets M and L
(2)
δ
M
∩
L
,
j
=
1
i
f
M
∩
L
=
j
,
0
otherwise
.Lemma 3.
LetD be a block design with parameters v
,
b
,
r
,
k
,
λ built on the set V. Let M be a subset of V with M
=
m. Then the following formulas hold: (3)
∑
j
=
0
k
z
j
=
b
,
(4)
∑
j
=
0
k
z
j
j
=
r
m
,
(5)
∑
j
=
0
k
z
j
j
2
=
m
λ
m
-
λ
+
r
.Proof.
The first two equations follow directly from the definition of a block design. In the same way one obtains(6)
∑
j
=
0
k
z
j
j
2
=
m
2
λ
. Here and below we assume that m
n
=
0 if n
>
m
. This and the first two equations of the lemma imply (5).Due to the first equation of Lemma3, the sequence φ
=
z
0
,
z
1
,
…
,
z
k is a partition of the number of blocks b. Let us denote this partition by φ
D
,
M
=
z
0
,
z
1
,
…
,
z
k
. Note that we allow z
i
=
0, for some i
≤
k, and do not require z
i
≥
z
j, for i
≥
j.Definition 4.
Two block designsD
1 and D
2 built on the same set V are called friends if the partitions φ
D
1
,
D
2
i and φ
D
2
,
D
1
j do not depend on i and j, respectively.Note that this relationship between designs is symmetric by definition.For designs which are friends, we simplify the notation for partition: we writeφ
D
1
,
D
2 instead of φ
D
1
,
D
2
i and φ
D
2
,
D
1 instead of φ
D
2
,
D
1
i.Example 5.
LetP
3 be the finite projective plane with parameters (v
=
b
=
7, r
=
3, k
=
3, λ
=
1) built on the set V
=
1,2
,
…
,
7, the Fano plane. Denote its blocks by B
i; that is, P
3
=
B
1
,
…
,
B
7. More precisely, we have B
1
=
2
,
3
,
5, B
2
=
3
,
4
,
6, B
3
=
4
,
5
,
7, B
4
=
1
,
5
,
6, B
5
=
2
,
6
,
7, B
6
=
1
,
3
,
7, B
7
=
1
,
2
,
4
. Let D
5 be the full design of block size five built on the same set V. Then P
3 and D
5 are friends. The corresponding partitions are φ
D
5
,
P
3
=
0
,
3
,
12
,
6 and φ
P
3
,
D
5
=
0
,
1
,
4
,
2
.For more examples of friends see Section4.Proposition 6.
Let block designsD
1 and D
2 be friends; then(7)
φ
D
1
,
D
2
b
2
=
φ
D
2
,
D
1
b
1
.Proof.
Consider a matrixM with entries given by M
i
j
=
D
1
i
∩
D
2
j for i
=
1
,
…
,
b
1 and j
=
1
,
…
,
b
2. Because D
1 and D
2 are friends, the rows (columns) of M are equal up to permutations. Any integer n appears equal number of times in every row (column). Multiplying this number of times by b
1 (resp., b
2), we get the total number of times the integer n appears in the matrix M. On the other hand, by doing so we get the corresponding component of the partition in the left (resp., right) hand side of (7).Proposition 7.
Let block designsD and D
1 be friends with the corresponding partition φ
D
,
D
1
=
z
0
,
z
1
,
…
,
z
k
D; here k
D is the block size of D. Let design D
2 be the complement of D
1; that is, D
2
s
=
V
∖
D
1
s for all s
=
1
,
…
,
b
1. Then D and D
2 are also friends and the partition φ
D
,
D
2
=
ω
0
,
…
,
ω
k
D satisfies (8)
ω
i
=
z
k
D
-
i
,
i
=
0
,
…
,
k
D
.Proof.
Let us assume thatk
D is smaller than block sizes of designs D
1 and D
2; the other situations are considered similarly. Suppose that a block D
1
s has i elements in common with a block D
t of design D. Then the remaining k
D
-
i elements of D
t belong to the complement of D
1
s, that is, to D
2
s. Thus ω
i
=
z
k
D
-
i.A natural question is when a block design is friends with itself.Example 8.
A full block designD
k is friends with itself. Indeed, in this case, φ
D
k
,
D
k
j
=
z
0
,
z
1
,
…
,
z
k is independent of the choice of a block of D
k since for all such partitions we have(9)
z
i
=
k
i
v
-
k
k
-
i
.Here are some classes of block designs that are naturally friends of themselves.Theorem 9.
LetD be a block design with parameters v
,
b
,
r
,
k
,
λ. (1)
Ifλ
=
1, then D is friends with itself.
(2)
Ifk
=
3, then D is friends with itself.
(3)
IfD is symmetric, that is, b
=
v, then D is friends with itself.Proof.
(
1
) Let B be an arbitrary block of D. As before, we denote φ
D
,
B
=
z
0
,
z
1
,
…
,
z
k, a partition of the number b of blocks obtained by intersecting all blocks of D with the chosen block B. Given that every pair of elements appears in only one block of D  λ
=
1, we know that no pair of elements from the block B will appear in some other block of D. Thus there will be no blocks whose intersection with B would give a set of two or more elements with the only exception of the set of k elements produced by the intersection of B with itself. Thus z
i
=
0 for 2
≤
i
≤
k
-
1 and z
k
=
1.
The remaining elementsz
0 and z
1 can be found from equations of Lemma 3. Thus the partition φ
D
,
B is independent of the choice of a block B.
(
2
) Let us first consider a block design D with an arbitrary k. For some arbitrary block B of D denote φ
D
,
B
=
z
0
,
z
1
,
…
,
z
k. Lemma 3 with m
=
k gives three relations for z
j
j
=
0
k. Our condition that no blocks are repeated implies that z
k
=
1. Thus we have four linear equations for k
+
1 partition elements z
0
,
…
,
z
k
. Therefore, when k
=
3, we can find the partition starting from parameters of the block design. This means, in particular, that the partition φ
D
,
B does not depend on the choice of a block B.
(3) This is a simple corollary of the well-known fact (see [2, page 110]) that in a symmetric design every two distinct blocks have λ points in common.Corollary 10.
Any finite projective plane is friends with itself.Proof.
Recall that a finite projective plane is a block design withb
=
v and λ
=
1.Example 11.
Here is a design that is friends with itself. The parameters are (v
=
9, b
=
12, r
=
8, k
=
6, λ
=
5), so this example is not covered by Theorem 9. This design is taken from [4, page 474]:(10)
1
2
4
5
7
8
2
3
5
6
8
9
1
3
4
6
7
9
1
3
5
6
7
8
1
2
4
6
8
9
2
3
4
5
7
9
1
2
5
6
7
9
1
3
4
5
8
9
2
3
4
6
7
8
4
5
6
7
8
9
1
2
3
4
5
6
1
2
3
7
8
9 The corresponding partition of 12 is 0
,
0
,
0
,
2
,
9
,
0
,
1.Although it is natural to suggest that every block design is friends with itself, this is not true. For block designs which are not friends with themselves, see Example18.Transitivity does not hold for the relationship of friendship either. To see this we first prove the following simple lemma.Lemma 12.
LetD be a block design v
,
b
,
r
,
k
,
λ built on a set V such that k
<
v
-
1
. Then D is friends with the full design D
v
-
1.Proof.
It is straightforward to compute the partitionsφ
D
,
D
v
-
1
i
=
z
0
,
z
1
,
…
,
z
k and φ
D
v
-
1
,
D
i
=
w
0
,
w
1
,
…
,
w
k. One obtains z
k
-
1
=
r, z
k
=
b
-
k, w
k
-
1
=
k, and w
k
=
v
-
k; all other entries vanish.Corollary 13.
The relationship of friendship is not transitive.Proof.
Consider two block designs built on the same setV which are not friends of each other and such that their block sizes are smaller than v
-
1. By the lemma they are both friends with D
v
-
1.


## 4. Friendly Families of Block Designs

In this section we consider a family of designs which are pairwise friends of each other. Let us call such a family (or set)friendly. For example, the set of full designs D
j
j
=
0
v is a friendly family. Such a set admits a partial order as follows.Definition 14.
Let two block designsD and D
¯ be friends with k
<
k
¯, where k and k
¯ are the sizes of blocks of D and D
¯, respectively, and φ
D
,
D
¯
=
z
0
,
z
1
,
…
,
z
k. One says that D
<
D
¯ if z
k
>
0.We thus have two partially ordered sets: a friendly set of block designs built on a setV and the power set P
V (ordered by inclusion). It turns out that there exists a map between these two sets that preserves the ordering.Proposition 15.
LetD
=
D
i
i
∈
I be a friendly family of designs built on V. Suppose that no two designs of D share a block and that the set of all blocks of all designs in D gives the power set P
V. Then there exists a map α
:
P
V
→
D preserving the partial order.Proof.
The mapα
:
P
(
V
)
→
D is defined as follows. It sends a subset U of V to the design in D which contains this subset U as a block. By the assumptions of the proposition, there exists a unique block design for which U is a block. Note that we consider the empty set and the full set V as degenerate designs included in D.
Now, suppose thatX
,
Y
∈
P
V, X
⊂
Y, and X
≠
Y; that is, X
<
Y. We want to show that α
X
<
α
Y. Since X
≠
Y, we have that X and Y belong to two distinct block designs from D, say, X
∈
D, Y
∈
D
¯ with k
<
k
¯, where k and k
¯ are block sizes of D and D
¯, respectively. Since D and D
¯ are friends and X
<
Y, then for φ
D
,
D
¯
=
z
0
,
z
1
,
…
,
z
k we have z
k
>
0, and therefore α
X
<
α
Y.In the following example, we construct a friendly family of designs that satisfies conditions of Proposition15 and that is different from the set of full designs D
j
j
=
0
v.Example 16.
All designs are built on the setV
=
1
,
2
,
…
,
7
.
LetP
3
=
B
1
,
…
,
B
7 be the finite projective plane from Example 5. Denote by D
3
′ the design with b
=
28 and k
=
3 whose blocks are given by all sets of three elements of V which are not blocks of P
3
.
Denote byD
4 the design with b
=
7 and k
=
4 whose blocks are complements of the blocks of P
3; that is, D
4
=
B
¯
1
,
…
,
B
¯
7, where B
¯
i
=
V
∖
B
i
. Similarly, by D
4
′, we denote the design with b
=
28 and k
=
4 whose blocks are the sets of four elements which are not blocks of D
4.
To the familyP
3
,
D
3
′
,
D
4
,
D
4
′ we also add the empty set D
0 and D
1
,
D
2
,
D
5
,
D
6
,
D
7
=
V, where D
k is the full design of block size k.
In this family all designs are pairwise friends. Moreover, we haveD
1
<
D
2, D
2
<
P
3 and D
2
<
D
3
′, D
3
′
<
D
4 and D
3
′
<
D
4
′, P
3
<
D
4
′, D
4
<
D
5, and D
4
′
<
D
5
<
D
6
<
D
7.In this section we presented a new way of constructing a partially ordered set (a poset) given by a full (satisfying conditions of Proposition15) friendly family of block designs. The condition of pairwise friendship seems to be a very strong one; therefore we expect such families to possess interesting properties. There arise a few interesting questions, for example, to say how many different full friendly sets of block designs one can construct on a given set V and to find analogues of the result of [5, 6] for such friendly families.


## 5. Constructing Friends of Block Designs

In this section we use the procedure of intersecting blocks of a design by various sets to form block designs starting with a given one.LetD be a design built on a set V whose blocks are of size k. Now, for every n
=
1,2
,
…
,
v consider the set N
n of all subsets of V of size n.We now subdivide the setN
n into classes of subsets D
j
n as follows. Consider the map Φ from the set N
n to the set of partitions of v which for a set S
∈
N
n gives Φ
S
=
φ
D
,
S
. In this way, we obtain a number of partitions in the image: Φ
N
n
=
φ
1
n
,
…
,
φ
s
n
n. Denote by D
j
n the class of sets from N
n given by the inverse image of φ
j
n; that is, D
j
n
=
Φ
-
1
φ
j
n.The family of these classes forms a special subdivision of the power setP
V into nonintersecting equivalence classes. In other words, we may say that two subsets of V are equivalent if and only if they belong to the same class D
j
n for some n and j. Let us denote this subdivision of P
V by M.If the original design is a projective plane on seven elements with blocks of size three,D
=
P
3, this subdivision coincides with the one described in Example 16; that is, M
=
D
0
,
D
1
,
D
2
,
P
3
,
D
3
′
,
D
4
,
D
4
′
,
D
5
,
D
6
,
D
7. For a projective plane with k
=
4 it is easy to verify that all D
j
n are block designs and that the family M is again friendly and satisfies conditions of Proposition 15.We conjecture that if the original designD is a Desargues projective plane, the above construction yields a friendly family of designs.The next theorem gives some cases when the described procedure results in block designs that are friends with the original one.Theorem 17.
LetD be a block design with parameters v
,
b
,
r
,
k
=
3
,
λ. Then one has the following:(i)
There are two classes of setsD
1
3
=
D and D
2
3 with the upper index (
3
). Both of them are block designs and both are friends with D.
(ii)
Ifλ
=
1, there are two classes of sets D
1
4 and D
2
4 with the upper index (
4
). In this case, both of them are block designs and both are friends with D.Proof.
(i) DefineD
2
3 to be the set of all 3 subsets of V which are not blocks of D and define D
1
(
3
) to coincide with D. As it is easy to see, all 3 subsets of V are covered by these two classes. Then D
1
3
=
D is trivially a block design and is friends with itself by Theorem 9.
To prove thatD
2
3 is a block design, we need to find its parameters v
2
3
b
2
3
,
r
2
3
,
k
2
3
,
λ
2
3. Two of these parameters are known: v
2
3
=
v and k
2
3
=
3. The remaining parameters are obtained easily knowing that the blocks of D
2
3 and those of D exhaust all triples of elements of V, we have b
2
3
=
v
3
-
b, r
2
3
=
v
-
1
2
-
r, and λ
2
3
=
v
-
2
-
λ.
Let us now prove thatD and D
2
3 are friends. Let B
i be a block of D
2
3 and consider the partition φ
D
,
B
i
=
z
0
,
z
1
,
z
2
,
z
3. By the definition of D
2
3 we have z
3
=
0. The three remaining z
i are found from the three equations of Lemma 3. By switching the roles of D and D
2
3 in the above calculation, we obtain that φ
D
2
3
,
D
i is also independent of i.
(ii) Define nowD
1
4
=
T
⊂
V
,
T
=
4
,
such
that
∃
D
i
⊂
T to be the set of all 4 subsets of V which contain at least one block of D. And define D
2
4
=
T
⊂
V
,
T
=
4
,
such
that
D
i
⊄
T
∀
i to be the set of all 4 subsets of V which do not contain any block of D. All 4 subsets of V are covered by these two classes.
Assuming thatλ
=
1, let us first prove that D
1
4 and D
2
4 are block designs. We do this by computing their parameters v
j
4, b
j
4, r
j
4, k
j
4, λ
j
4 for j
=
1,2. We know that v
j
4
=
v and k
j
4
=
4. To find b
j
4, let us note that the blocks of D
1
4 are obtained by taking a block of D and upending to it one element not already contained in the block. In this way, for every block of D, we get v
-
3 new sets in D
1
4. Since λ
=
1, sets obtained from different blocks of D will intersect by at most two elements. Thus they will all be distinct and we have b
1
4
=
b
v
-
3
. Now, r
1
4
=
r
v
-
3
+
b
-
r. This is because, for a given element for each of the r blocks in D that contain it, we get v
-
3 blocks in D
1
4; similarly, for each of the b
-
r blocks of D that do not contain the given element we can upend this element to obtain a block of D
1
4 that contains it. Reasoning analogously, we obtain λ
1
4
=
v
-
3
+
2
r
-
1
. Parameters of D
2
4 are determined knowing that the blocks of D
1
4 and D
2
4 exhaust all quadruples of elements of V.
Let us now prove thatD
j
4 and D are friends. We need to see that all four partitions φ
D
j
4
,
D
i and φ
D
,
D
j
4
i are independent of i. All of the partitions contain four parts z
0
,
z
1
,
z
2
,
z
3; thus, by Lemma 3, it is enough to determine one of the parts. As is easy to see, if λ
=
1, the z
3 part of φ
D
1
4
,
D
i is equal to v
-
3 and that of φ
D
2
4
,
D
i vanishes. Similarly we find that the z
3 part of φ
D
,
D
1
4
i is equal to one and that of φ
D
,
D
2
4
i vanishes by definition.Example 18.
Consider the following two Steiner triple systemsS
T
S
13, that is, two block designs with parameters (v
=
13, b
=
26, r
=
6, k
=
3, λ
=
1). We denote them by S
1 and S
2 and list all their blocks. The blocks are such that S
1
i
=
S
2
i for i
=
1
,
…
,
22, and the four remaining blocks are different in the two STS. Here is the list of the blocks: (11)
S
j
1
=
1,2
,
3
,
S
j
2
=
1,4
,
5
,
S
j
3
=
1,6
,
7
,
S
j
4
=
1,8
,
9
,
S
j
5
=
1,10,11
,
S
j
6
=
1,12,13
,
S
j
7
=
2,4
,
6
,
S
j
8
=
2,5
,
7
,
S
j
9
=
2,8
,
10
,
S
j
10
=
2,9
,
12
,
S
j
11
=
2,11,13
,
S
j
12
=
4,3
,
8
,
S
j
13
=
4,7
,
9
,
S
j
14
=
4,10,13
,
S
j
15
=
4,11,12
,
S
j
16
=
7,3
,
11
,
S
j
17
=
7,8
,
13
,
S
j
18
=
7,10,12
,
S
j
19
=
8,5
,
11
,
S
j
20
=
8,6
,
12
,
S
j
21
=
6,9
,
11
,
S
j
22
=
3,5
,
12and the four remaining blocks in each STS are (12)
S
1
23
=
3,6
,
10
,
S
1
24
=
3,9
,
13
,
S
1
25
=
5,6
,
13
,
S
1
26
=
5,9
,
10
,
S
2
23
=
3,6
,
13
,
S
2
24
=
3,9
,
10
,
S
2
25
=
5,6
,
10
,
S
2
26
=
5,9
,
13
.On these two block designs we perform the procedure described in the beginning of this section and find the sets D
j
n for n
=
3
,
4
,
5
,
6
. The corresponding sets for other values of n can be obtained using Proposition 7. (i)
For bothS
1 and S
2, the set Φ
N
3 contains two partitions, φ
1
3
=
10
,
15
,
0
,
1 and φ
2
3
=
11
,
12
,
3
,
0. The number of blocks in D
1
3 is 26 and the number of blocks in D
2
3 is 260.
(ii)
For bothS
1 and S
2, the set Φ
N
4 contains two partitions, φ
1
4
=
7
,
15
,
3
,
1 corresponding to 260 blocks in D
1
4 and φ
2
4
=
8
,
12
,
6
,
0 corresponding to 455 blocks in D
2
4.
(iii)
For bothS
1 and S
2, the set Φ
N
5 contains three partitions: φ
1
5
=
5
,
13
,
7
,
1 corresponding to 780 blocks in D
1
5, then φ
2
5
=
4,16,4
,
2 corresponding to 195 blocks in D
2
5, and φ
3
5
=
6
,
10
,
10
,
0 corresponding to 312 blocks in D
3
5.
(iv)
For bothS
1 and S
2, the set Φ
N
6 contains five partitions: φ
1
6
=
2
,
15
,
6
,
3, φ
2
6
=
1
,
18
,
3
,
4, φ
3
6
=
4
,
9
,
12
,
1, φ
4
6
=
3
,
12
,
9
,
2, and φ
5
6
=
5
,
6
,
15
,
0. However the number of blocks in the corresponding sets D
j
6 differs for S
1 and S
2. Namely, the sets D
1
6 contain 208 and 228 blocks for S
1 and S
2, respectively. The numbers of blocks for D
2
6 are 13 and 8, for D
3
6 are 468 and 488, for D
4
6 are 988 and 958, and for D
5
6 are 39 and 34, respectively. It turns out that for n
=
3
,
4
,
5 all the obtained sets D
j
n are block designs; moreover for n
=
3 and n
=
4, we obtain friendly families of block designs. For n
=
5 the obtained block designs are not friends of one another nor are they friends with themselves. They are, however, friends with the original Steiner triple system. For n
=
6 none of the sets D
j
6 is a block design.



---

*Source: 7092474-2016-07-28.xml*