Page 52 - 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. 52
2.2 Latin squares
A design (V , ) is a subdesign of (V, ) if V ⊂ V and ⊂ .
Given a design D = (V, ), a block intersection graph G (D) is a graph with the vertex
set and the edge set {{Bi , Bj } : Bi ∩ Bj = }. In particular, for a (v, k , 1) − BIBD, G (D) is
strongly regular.
Exercise 1.
(1) Construct a (6, 3, 2) − BIBD.
(2) Construct a (13, 4, 1) − BIBD.
Exercise 2.
Find an isomorphism for the Fano plane given in Example 1 and its dual.
Exercise 3.
Prove that Fano plane is unique up to automorphism. Determine the order of its full
automorphism group.
Exercise 4.
Find a (41, 5, 1)-difference family in the group Z41.
Exercise 5.
Construct a cyclic (21, 3, 1) − BIBD.
Exercise 6.
Given a BIBD(v,b, r, k , 1), determine the parameters (i.e., order, size, degree, clique num-
ber, the number of common neighbors for each pair of adjacent vertices and for each pair
of nonadjacent vertices) of its block intersection graph.
2.2 Latin squares
Definition 3. A latin square of order n (or side n ) is an n × n array in which each cell
contains a single symbol from an n-element set S, such that each symbol occurs exactly
once in each row and exactly once in each column.
The nature of symbols in S is of no importance so usually we take S := {1, 2, . . . , n}.
Definition 4. A quasigroup is an algebraic structure (Q, ◦), where Q is a set and ◦ is a
binary operation on Q such that the equations a ◦ x = b and y ◦ a = b have unique so-
lutions for every pair of elements a , b in Q. If Q is finite, then |Q| = n is the order of the
quasigroup.
A latin square can be viewed as a multiplication table of a quasigroup with the head-
line and sideline removed. Thus latin squares and quasigroups are equivalent combina-
torial objects and we may use these two terms interchangeably.
Example 9. Latin square of order 4 and its corresponding quasigroup of order 4.
1243 ◦1234
3421 11243
4132 23421
2314 34132
42314
A design (V , ) is a subdesign of (V, ) if V ⊂ V and ⊂ .
Given a design D = (V, ), a block intersection graph G (D) is a graph with the vertex
set and the edge set {{Bi , Bj } : Bi ∩ Bj = }. In particular, for a (v, k , 1) − BIBD, G (D) is
strongly regular.
Exercise 1.
(1) Construct a (6, 3, 2) − BIBD.
(2) Construct a (13, 4, 1) − BIBD.
Exercise 2.
Find an isomorphism for the Fano plane given in Example 1 and its dual.
Exercise 3.
Prove that Fano plane is unique up to automorphism. Determine the order of its full
automorphism group.
Exercise 4.
Find a (41, 5, 1)-difference family in the group Z41.
Exercise 5.
Construct a cyclic (21, 3, 1) − BIBD.
Exercise 6.
Given a BIBD(v,b, r, k , 1), determine the parameters (i.e., order, size, degree, clique num-
ber, the number of common neighbors for each pair of adjacent vertices and for each pair
of nonadjacent vertices) of its block intersection graph.
2.2 Latin squares
Definition 3. A latin square of order n (or side n ) is an n × n array in which each cell
contains a single symbol from an n-element set S, such that each symbol occurs exactly
once in each row and exactly once in each column.
The nature of symbols in S is of no importance so usually we take S := {1, 2, . . . , n}.
Definition 4. A quasigroup is an algebraic structure (Q, ◦), where Q is a set and ◦ is a
binary operation on Q such that the equations a ◦ x = b and y ◦ a = b have unique so-
lutions for every pair of elements a , b in Q. If Q is finite, then |Q| = n is the order of the
quasigroup.
A latin square can be viewed as a multiplication table of a quasigroup with the head-
line and sideline removed. Thus latin squares and quasigroups are equivalent combina-
torial objects and we may use these two terms interchangeably.
Example 9. Latin square of order 4 and its corresponding quasigroup of order 4.
1243 ◦1234
3421 11243
4132 23421
2314 34132
42314
