Page 49 - Ellingham, Mark, Mariusz Meszka, Primož Moravec, Enes Pasalic, 2014. 2014 PhD Summer School in Discrete Mathematics. Koper: University of Primorska Press. Famnit Lectures, 3.
P. 49
iusz Meszka: Combinatorial Designs 37
2.1 Balanced incomplete block designs
A design (or combinatorial design, or block design) is a pair (V, ) such that V is a finite
set and is a collection of nonempty subsets of V . Elements in V are called points while
subsets in are called blocks.
One of the most important classes of designs are balanced incomplete block designs.
Definition 1. A balanced incomplete block design (BIBD) is a pair (V, ) where |V | = v
and is a collection of b blocks, each of cardinality k , such that each element of V is
contained in exactly r blocks and any 2-element subset of V is contained in exactly λ
blocks. The numbers v , b , r , k an λ are parameters of the BIBD.
Since r = λ(v −1) and b = λv (v −1) must be integers, the following are obvious arith-
k −1 k (k −1)
metic necessary conditions for the existence of a BIBD(v,b, r, k , λ):
(1) λ(v − 1) ≡ 0 (mod k − 1),
(2) λv (v − 1) ≡ 0 (mod k (k − 1)).
Parameter sets that satisfy (1) and (2) are called admissible.
The five parameters: v , b , r , k , λ are not independent; three of them: v , k and λ
uniquely determine the remaining two as r = λ(v −1) and b = vr . Hence we often write
k −1 k
(v, k , λ)-design (or (v, k , λ) − BIBD) to denote a BIBD(v,b, r, k , λ).
Example 1. A (7, 3, 1) − BIBD (the "Fano plane"):
V = {0, 1, . . . , 6},
= {{0, 1, 2}, {0, 3, 4}, {0, 5, 6}, {1, 3, 5}, {1, 3, 6}, {2, 3, 6}, {2, 4, 5}}.
Example 2. A (11, 5, 2) − BIBD:
V = {0, 1, . . . , 10},
= {{0, 1, 2, 6, 9}, {0, 1, 5, 8, 10}, {0, 2, 3, 4, 8}, {0, 3, 5, 6, 7}, {0, 4, 7, 9, 10}, {1, 2, 3, 7, 10},
{1, 3, 4, 5, 9}, {1, 4, 6, 7, 8}, {2, 4, 5, 6, 10}, {2, 5, 7, 8, 9}, {3, 6, 8, 9, 10}}.
The necessary conditions are also sufficient for the existence of a (v,k,1)-BIBD with
small k :
when k = 2, v ≥ 2,
when k = 3, v ≡ 1, 3 (mod 6),
when k = 4, v ≡ 1, 4 (mod 12),
when k = 5, v ≡ 1, 5 (mod 20).
For k = 6, a (v, 6, 1) − BIBD exists if v ≡ 1, 6 (mod 15) and v = 16, 21, 36, 46; 51, 61, 81, 166,
226, 231, 256, 261, 286, 316, 321, 346, 351, 376, 406, 411, 436, 441, 471, 501, 561, 591, 616, 646,
651, 676, 771, 796, 801. In the case of the orders v = 16, 21, 36, 46 it is proven that a (v, 6, 1)−
BIBD does not exists, in the case of remaining 29 orders the existence problem is still
unsettled.
A convenient way to represent a BIBD, other than a list of its blocks, is an incidence
matrix. The incidence matrix of a (v, k , λ) − BIBD (V, ), where V = {xi : 1 ≤ i ≤ v } and
= {Bj : 1 ≤ j ≤ b }, is a v ×b matrix A = (a i j ), in which a i j = 1 when xi ∈ Bj and a i j = 0
otherwise.
Lemma 1. If A is an incidence matrix of a (v, k , λ)−BIBD, then AAT = (r −λ)I +λJ , where
I is a v × v identity matrix and J is a v × v all ones matrix.
Theorem 2 (Fisher’s inequality). If a (v, k , λ) − BIBD exists with 2 ≤ k < v , then b ≥ v .
2.1 Balanced incomplete block designs
A design (or combinatorial design, or block design) is a pair (V, ) such that V is a finite
set and is a collection of nonempty subsets of V . Elements in V are called points while
subsets in are called blocks.
One of the most important classes of designs are balanced incomplete block designs.
Definition 1. A balanced incomplete block design (BIBD) is a pair (V, ) where |V | = v
and is a collection of b blocks, each of cardinality k , such that each element of V is
contained in exactly r blocks and any 2-element subset of V is contained in exactly λ
blocks. The numbers v , b , r , k an λ are parameters of the BIBD.
Since r = λ(v −1) and b = λv (v −1) must be integers, the following are obvious arith-
k −1 k (k −1)
metic necessary conditions for the existence of a BIBD(v,b, r, k , λ):
(1) λ(v − 1) ≡ 0 (mod k − 1),
(2) λv (v − 1) ≡ 0 (mod k (k − 1)).
Parameter sets that satisfy (1) and (2) are called admissible.
The five parameters: v , b , r , k , λ are not independent; three of them: v , k and λ
uniquely determine the remaining two as r = λ(v −1) and b = vr . Hence we often write
k −1 k
(v, k , λ)-design (or (v, k , λ) − BIBD) to denote a BIBD(v,b, r, k , λ).
Example 1. A (7, 3, 1) − BIBD (the "Fano plane"):
V = {0, 1, . . . , 6},
= {{0, 1, 2}, {0, 3, 4}, {0, 5, 6}, {1, 3, 5}, {1, 3, 6}, {2, 3, 6}, {2, 4, 5}}.
Example 2. A (11, 5, 2) − BIBD:
V = {0, 1, . . . , 10},
= {{0, 1, 2, 6, 9}, {0, 1, 5, 8, 10}, {0, 2, 3, 4, 8}, {0, 3, 5, 6, 7}, {0, 4, 7, 9, 10}, {1, 2, 3, 7, 10},
{1, 3, 4, 5, 9}, {1, 4, 6, 7, 8}, {2, 4, 5, 6, 10}, {2, 5, 7, 8, 9}, {3, 6, 8, 9, 10}}.
The necessary conditions are also sufficient for the existence of a (v,k,1)-BIBD with
small k :
when k = 2, v ≥ 2,
when k = 3, v ≡ 1, 3 (mod 6),
when k = 4, v ≡ 1, 4 (mod 12),
when k = 5, v ≡ 1, 5 (mod 20).
For k = 6, a (v, 6, 1) − BIBD exists if v ≡ 1, 6 (mod 15) and v = 16, 21, 36, 46; 51, 61, 81, 166,
226, 231, 256, 261, 286, 316, 321, 346, 351, 376, 406, 411, 436, 441, 471, 501, 561, 591, 616, 646,
651, 676, 771, 796, 801. In the case of the orders v = 16, 21, 36, 46 it is proven that a (v, 6, 1)−
BIBD does not exists, in the case of remaining 29 orders the existence problem is still
unsettled.
A convenient way to represent a BIBD, other than a list of its blocks, is an incidence
matrix. The incidence matrix of a (v, k , λ) − BIBD (V, ), where V = {xi : 1 ≤ i ≤ v } and
= {Bj : 1 ≤ j ≤ b }, is a v ×b matrix A = (a i j ), in which a i j = 1 when xi ∈ Bj and a i j = 0
otherwise.
Lemma 1. If A is an incidence matrix of a (v, k , λ)−BIBD, then AAT = (r −λ)I +λJ , where
I is a v × v identity matrix and J is a v × v all ones matrix.
Theorem 2 (Fisher’s inequality). If a (v, k , λ) − BIBD exists with 2 ≤ k < v , then b ≥ v .
