Page 50 - 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. 50
2.1 Balanced incomplete block designs
This result, for instance, guarantees that a (21, 6, 1) − BIBD cannot exist, since b =
14 < 21 = v , even though the above arithmetic necessary conditions are satisfied.
A BIBD is called symmetric if v = b (and r = k ). The most fundamental necessary
condition for the existence of symmetric designs is due to Bruck, Ryser and Chowla.
Theorem 3 (Bruck-Ryser-Chowla). Let v , k and λ be integers satisfying λ(v −1) = k (k −1)
and for which there exists a symmetric (v, k , λ) − BIBD.
(1) If v is even, then n = k − λ is a square.
(2) If v is odd, then the equation z 2 = nx 2 + (−1)(v −1)/2λy 2 has a solution in integers x , y ,
z not all zero.
The dual of D is a design D∗ = ( , V ), where corresponds to a set of elements and
V to a set of blocks, such that B ∈ is an element contained in v ∈ V if and only if v
is contained in B in D. Thus, if M is an incidence matrix of D, then M T is an incidence
matrix of D∗.
Remark. The dual of a BIBD is a BIBD if and only if the BIBD is symmetric.
Also, the parameters of a symmetric design and its dual are the same, yet they are not
necessarily isomorphic.
All necessary conditions specified above (taken together) are still not sufficient for
the existence, for instance, of a symmetric (111, 111, 11, 11, 1) − BIBD. One can easily
check the set of parameters satisfies all conditions (including Fisher’s inequality and
Bruck-Ryser-Chowla theorem) but such design does not exist, what was proven by a de-
tailed structural analysis together with an exhaustive computational search. The general
existence question for BIBD’s remains crucial open problem for infinitely many sets of
parameters.
Definition 2. Two designs, (V1, 1) and (V2, 2), are isomorphic if there exists a bijection
α : V1 → V2 such that for any B1 ∈ 1 there exists B2 ∈ 2, where B2 = {α(xi ) : xi ∈ B1}.
An automorphism is an isomorphism from a design to itself. The set of all auto-
morphisms of a design forms a group called the full automorphism group. An automor-
phism group of a design is any subgroup of its full automorphism group. In particular, a
(v, k , λ) − BIBD is cyclic if it admits a cyclic group of order v as its automorphism group.
Specifying an automorphism group allows sometimes to construct a design in much
easier way. Then it is enough to select a set of base blocks which are representatives of
each orbit of blocks under the prescribed automorphism group. All remaining blocks are
obtained by action of the group on these base blocks.
Let G be a group of order v . A k -element subset D of G is a (v, k , λ)-difference set if
every non-zero element of G has exactly λ representations as a difference d − d with
elements from D.
Theorem 4. A set D = {d 1, d 2, . . . , d k } of k residues modulo v is a (v, k , λ)-difference set if
and only if the sets Bi = {d 1 + i , d 2 + i , . . . , d k + i } modv , i = 0, 1, . . . , v − 1 form blocks of a
cyclic (v, k , λ) − BIBD.
Example 3. {0, 1, 3, 9} is a (13, 4, 1)-difference set in the group Z13.
Thus {0, 1, 3, 9} is the base block of a cyclic (13, 4, 1) − BIBD.
The concept of a difference set may be extended to a larger number of sets. Let G be a
This result, for instance, guarantees that a (21, 6, 1) − BIBD cannot exist, since b =
14 < 21 = v , even though the above arithmetic necessary conditions are satisfied.
A BIBD is called symmetric if v = b (and r = k ). The most fundamental necessary
condition for the existence of symmetric designs is due to Bruck, Ryser and Chowla.
Theorem 3 (Bruck-Ryser-Chowla). Let v , k and λ be integers satisfying λ(v −1) = k (k −1)
and for which there exists a symmetric (v, k , λ) − BIBD.
(1) If v is even, then n = k − λ is a square.
(2) If v is odd, then the equation z 2 = nx 2 + (−1)(v −1)/2λy 2 has a solution in integers x , y ,
z not all zero.
The dual of D is a design D∗ = ( , V ), where corresponds to a set of elements and
V to a set of blocks, such that B ∈ is an element contained in v ∈ V if and only if v
is contained in B in D. Thus, if M is an incidence matrix of D, then M T is an incidence
matrix of D∗.
Remark. The dual of a BIBD is a BIBD if and only if the BIBD is symmetric.
Also, the parameters of a symmetric design and its dual are the same, yet they are not
necessarily isomorphic.
All necessary conditions specified above (taken together) are still not sufficient for
the existence, for instance, of a symmetric (111, 111, 11, 11, 1) − BIBD. One can easily
check the set of parameters satisfies all conditions (including Fisher’s inequality and
Bruck-Ryser-Chowla theorem) but such design does not exist, what was proven by a de-
tailed structural analysis together with an exhaustive computational search. The general
existence question for BIBD’s remains crucial open problem for infinitely many sets of
parameters.
Definition 2. Two designs, (V1, 1) and (V2, 2), are isomorphic if there exists a bijection
α : V1 → V2 such that for any B1 ∈ 1 there exists B2 ∈ 2, where B2 = {α(xi ) : xi ∈ B1}.
An automorphism is an isomorphism from a design to itself. The set of all auto-
morphisms of a design forms a group called the full automorphism group. An automor-
phism group of a design is any subgroup of its full automorphism group. In particular, a
(v, k , λ) − BIBD is cyclic if it admits a cyclic group of order v as its automorphism group.
Specifying an automorphism group allows sometimes to construct a design in much
easier way. Then it is enough to select a set of base blocks which are representatives of
each orbit of blocks under the prescribed automorphism group. All remaining blocks are
obtained by action of the group on these base blocks.
Let G be a group of order v . A k -element subset D of G is a (v, k , λ)-difference set if
every non-zero element of G has exactly λ representations as a difference d − d with
elements from D.
Theorem 4. A set D = {d 1, d 2, . . . , d k } of k residues modulo v is a (v, k , λ)-difference set if
and only if the sets Bi = {d 1 + i , d 2 + i , . . . , d k + i } modv , i = 0, 1, . . . , v − 1 form blocks of a
cyclic (v, k , λ) − BIBD.
Example 3. {0, 1, 3, 9} is a (13, 4, 1)-difference set in the group Z13.
Thus {0, 1, 3, 9} is the base block of a cyclic (13, 4, 1) − BIBD.
The concept of a difference set may be extended to a larger number of sets. Let G be a
