Page 62 - 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. 62
2.6 Other classes of designs
(A3) there exist three points not on a common line.
For a finite affine plane A, there is a positive integer n such that any line of A has
exactly n points. This number is the order of A. A finite affine plane of order n has n 2
points, n 2 + n lines, and n + 1 lines through each point.
Lemma 23. An affine plane or order n is a BIBD(n 2, n 2 + n , n , n + 1, 1). Conversely,
BIBD(n 2, n 2 + n , n , n + 1, 1) is an affine plane of order n .
Remark. An affine plane is resolvable.
Theorem 24. An affine plane of order n exists if n is a prime power.
Construction of an affine plane of a prime power order.
Let q = p k be a prime power. Let V = Fq × Fq .
For any a ,b ∈ Fq , define a block L a,b = {(x , y ) ∈ V : y = a x + b }.
For any c ∈ Fq , define L ∞,c = {(c , y ) ∈ V : y ∈ Fq }.
Finally, define = {L a,b : a ,b ∈ Fq } ∪ {L ∞,c : c ∈ Fq }.
(V, ) is a (q 2,q, 1) − BIBD.
Remark. The existence of an affine plane of order n is equivalent to the existence a set
of n − 1 MOLS(n).
Definition 16. A finite projective plane is a finite incidence structure such that the fol-
lowing axioms are satisfied:
(P1) any two distinct points are incident with exactly one line,
(P2) any two distinct lines are incident with exactly one point,
(P3) there exist four points no three of which are on the same line.
For a finite projective plane P, there is a positive integer n such that any line of P has
exactly n + 1 points. This number is the order of P. A finite projective plane of order n
has n 2 + n + 1 points, n 2 + n + 1 lines, and n + 1 lines through each point.
Lemma 25. A projective plane or order n is a BIBD(n 2 + n + 1, n 2 + n + 1, n + 1, n + 1, 1).
BIBD(n 2 + n + 1, n 2 + n + 1, n + 1, n + 1, 1) is a projective plane of order n .
Remark. A projective plane of order n exists if and only if an affine plane of order n exists.
Exercise 21.
Construct an affine plane of order 4.
2.6.2 Cycle systems
Definition 17. A k -cycle system of order n is a pair (X , ) where is a collection of edge-
disjoint k -cycles which partition the edge set of Kn with V (Kn ) = X .
Example 19. A 4-cycle system (X , ) of order 9:
V = {0, 1, . . . , 8}, = {(0, 1, 5, 2), (0, 3, 8, 7), (0, 4, 1, 8), (0, 5, 4, 6), (1, 2, 6, 3), (1, 6, 5, 7),
(A3) there exist three points not on a common line.
For a finite affine plane A, there is a positive integer n such that any line of A has
exactly n points. This number is the order of A. A finite affine plane of order n has n 2
points, n 2 + n lines, and n + 1 lines through each point.
Lemma 23. An affine plane or order n is a BIBD(n 2, n 2 + n , n , n + 1, 1). Conversely,
BIBD(n 2, n 2 + n , n , n + 1, 1) is an affine plane of order n .
Remark. An affine plane is resolvable.
Theorem 24. An affine plane of order n exists if n is a prime power.
Construction of an affine plane of a prime power order.
Let q = p k be a prime power. Let V = Fq × Fq .
For any a ,b ∈ Fq , define a block L a,b = {(x , y ) ∈ V : y = a x + b }.
For any c ∈ Fq , define L ∞,c = {(c , y ) ∈ V : y ∈ Fq }.
Finally, define = {L a,b : a ,b ∈ Fq } ∪ {L ∞,c : c ∈ Fq }.
(V, ) is a (q 2,q, 1) − BIBD.
Remark. The existence of an affine plane of order n is equivalent to the existence a set
of n − 1 MOLS(n).
Definition 16. A finite projective plane is a finite incidence structure such that the fol-
lowing axioms are satisfied:
(P1) any two distinct points are incident with exactly one line,
(P2) any two distinct lines are incident with exactly one point,
(P3) there exist four points no three of which are on the same line.
For a finite projective plane P, there is a positive integer n such that any line of P has
exactly n + 1 points. This number is the order of P. A finite projective plane of order n
has n 2 + n + 1 points, n 2 + n + 1 lines, and n + 1 lines through each point.
Lemma 25. A projective plane or order n is a BIBD(n 2 + n + 1, n 2 + n + 1, n + 1, n + 1, 1).
BIBD(n 2 + n + 1, n 2 + n + 1, n + 1, n + 1, 1) is a projective plane of order n .
Remark. A projective plane of order n exists if and only if an affine plane of order n exists.
Exercise 21.
Construct an affine plane of order 4.
2.6.2 Cycle systems
Definition 17. A k -cycle system of order n is a pair (X , ) where is a collection of edge-
disjoint k -cycles which partition the edge set of Kn with V (Kn ) = X .
Example 19. A 4-cycle system (X , ) of order 9:
V = {0, 1, . . . , 8}, = {(0, 1, 5, 2), (0, 3, 8, 7), (0, 4, 1, 8), (0, 5, 4, 6), (1, 2, 6, 3), (1, 6, 5, 7),
