Page 51 - 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. 51
iusz Meszka: Combinatorial Designs 39
group of order v . A collection = {D1, D2, . . . Ds } of k -element subsets of G , where Di =
{d i , d i , . . . d i }, i = 1, 2, . . . s , forms a (v, k , λ)-difference family if every non-zero element
1 2 k
p p
of G occurs exactly λ times as a difference d i − d j .
Theorem 5. If a set = {D1, D2, . . . , Ds } is a (v, k , λ)-difference family over the cyclic group
G , then Or bG (D1)∪Or bG (D2)∪. . .∪Or bG (Ds ) is the collection of blocks of a cyclic (v, k , λ)−
BIBD.
Example 4. {{0, 2, 10, 15, 19, 20}, {0, 3, 7, 9, 10, 16}} is a (21, 6, 3)-difference family in the
group Z21.
Let G be a group of order v − 1. A collection = {D1, D2, . . . Ds } of k -element subsets
of G ∪{∞}, is a 1-rotational (v, k , λ)-difference family if every non-zero element of G ∪{∞}
p p
occurs exactly λ times as a difference d i − d j .
Theorem 6. If a set = {D1, D2, . . . , Ds } is a 1-rotational (v, k , λ)-difference family over
the group G , then Or bG (D1) ∪ Or bG (D2) ∪ . . . ∪ Or bG (Ds ) is the collection of blocks of a
(v, k , λ) − BIBD admitting an automorphism group fixing one point and acting sharply
transitively on the other points.
Example 5. {{0, 1, 3}, {0, 1, 5}}, {0, 2, 5}}, {0, 4, ∞}} is a 1-rotational (12, 3, 2)-difference fam-
ily.
The concept of a difference family has been generalized by Bose to form a basis of
a method that is called the method of pure and mixed differences. Let G be an additive
abelian group and let T be a t -element set. Consider the set V = G × T . For any two
elements (x , i ) = (y , j ) of V , the differences arising from this pair may be of two kinds:
(1) if i = j then ±(x − y ) is a pure difference of class i
(2) if i = j then ±(x − y ) is a mixed difference of class i j .
A pure difference of any class may equal to any nonzero element of G while a mixed
difference may equal to any element of G .
Suppose that there exists a collection of k -element sets = {D1, D2, . . . , Ds } such that
every nonzero element of G occurs exactly λ times as a pure difference of class i for each
i ∈ T , and moreover every element of G occurs exactly λ times as a mixed difference of
class i j for all i , j ∈ T , i = j . Then the sets in form a basis of a (v, k , λ) − BIBD (V, ),
where = {Di + g : g ∈ G , i = 1, 2, . . . s }.
Example 6. Let G = Z5 and T = {1, 2}.
= {{01, 21, 31, 32}, {01, 22, 32, 42}}, {01, 11, 02, 22}} is a basis for a (10, 4, 2) − BIBD.
Example 7. Let G = Z3 and T = {1, 2, 3}.
= {{01, 11, 02}, {02, 12, 03}, {01, 03, 13}}, {01, 12, 23}} is a basis for a (9, 3, 1) − BIBD.
The above construction may be extended by adding one fixed point.
Example 8. Let V = (Z7 × {1, 2}) ∪ {∞}.
= {{01, 11, 31}, {01, 02, 12}, {01, 22, 42}}, {01, 32, 62}, {01, 42, ∞}} is a basis for a (15, 3, 1) −
BIBD.
A complement of a design (V, ) is a design (V, ), where = {V \ B : B ∈ }. Thus
a complement of a BIBD(v,b, r, k , λ) is a BIBD(v,b,b − r, v − k ,b − 2r + λ). A supplement
of a BIBD(v,b, r, k , λ) is a BIBD obtained by taking all k -subsets which are not in as
blocks; in this way we get a BIBD(v, v −b, v −1 − r,k , v −2 − λ).
k k −1 k −2
group of order v . A collection = {D1, D2, . . . Ds } of k -element subsets of G , where Di =
{d i , d i , . . . d i }, i = 1, 2, . . . s , forms a (v, k , λ)-difference family if every non-zero element
1 2 k
p p
of G occurs exactly λ times as a difference d i − d j .
Theorem 5. If a set = {D1, D2, . . . , Ds } is a (v, k , λ)-difference family over the cyclic group
G , then Or bG (D1)∪Or bG (D2)∪. . .∪Or bG (Ds ) is the collection of blocks of a cyclic (v, k , λ)−
BIBD.
Example 4. {{0, 2, 10, 15, 19, 20}, {0, 3, 7, 9, 10, 16}} is a (21, 6, 3)-difference family in the
group Z21.
Let G be a group of order v − 1. A collection = {D1, D2, . . . Ds } of k -element subsets
of G ∪{∞}, is a 1-rotational (v, k , λ)-difference family if every non-zero element of G ∪{∞}
p p
occurs exactly λ times as a difference d i − d j .
Theorem 6. If a set = {D1, D2, . . . , Ds } is a 1-rotational (v, k , λ)-difference family over
the group G , then Or bG (D1) ∪ Or bG (D2) ∪ . . . ∪ Or bG (Ds ) is the collection of blocks of a
(v, k , λ) − BIBD admitting an automorphism group fixing one point and acting sharply
transitively on the other points.
Example 5. {{0, 1, 3}, {0, 1, 5}}, {0, 2, 5}}, {0, 4, ∞}} is a 1-rotational (12, 3, 2)-difference fam-
ily.
The concept of a difference family has been generalized by Bose to form a basis of
a method that is called the method of pure and mixed differences. Let G be an additive
abelian group and let T be a t -element set. Consider the set V = G × T . For any two
elements (x , i ) = (y , j ) of V , the differences arising from this pair may be of two kinds:
(1) if i = j then ±(x − y ) is a pure difference of class i
(2) if i = j then ±(x − y ) is a mixed difference of class i j .
A pure difference of any class may equal to any nonzero element of G while a mixed
difference may equal to any element of G .
Suppose that there exists a collection of k -element sets = {D1, D2, . . . , Ds } such that
every nonzero element of G occurs exactly λ times as a pure difference of class i for each
i ∈ T , and moreover every element of G occurs exactly λ times as a mixed difference of
class i j for all i , j ∈ T , i = j . Then the sets in form a basis of a (v, k , λ) − BIBD (V, ),
where = {Di + g : g ∈ G , i = 1, 2, . . . s }.
Example 6. Let G = Z5 and T = {1, 2}.
= {{01, 21, 31, 32}, {01, 22, 32, 42}}, {01, 11, 02, 22}} is a basis for a (10, 4, 2) − BIBD.
Example 7. Let G = Z3 and T = {1, 2, 3}.
= {{01, 11, 02}, {02, 12, 03}, {01, 03, 13}}, {01, 12, 23}} is a basis for a (9, 3, 1) − BIBD.
The above construction may be extended by adding one fixed point.
Example 8. Let V = (Z7 × {1, 2}) ∪ {∞}.
= {{01, 11, 31}, {01, 02, 12}, {01, 22, 42}}, {01, 32, 62}, {01, 42, ∞}} is a basis for a (15, 3, 1) −
BIBD.
A complement of a design (V, ) is a design (V, ), where = {V \ B : B ∈ }. Thus
a complement of a BIBD(v,b, r, k , λ) is a BIBD(v,b,b − r, v − k ,b − 2r + λ). A supplement
of a BIBD(v,b, r, k , λ) is a BIBD obtained by taking all k -subsets which are not in as
blocks; in this way we get a BIBD(v, v −b, v −1 − r,k , v −2 − λ).
k k −1 k −2
