Chapter 8

Connections with geometry and graph theory

In this chapter we shall show firstly that there is a very intimate connection between latin squares and geometric nets and, as already noted in Section 5.2, between complete sets of MOLS and projective planes. As a consequence, a number of problems concerning the former may more easily be dealt with in the guise of geometry.

In the first section, we show that, with each bordered latin square or quasigroup, there is associated a corresponding geometric 3-net and that the geometrical properties of the 3-net reflect the algebraic properties of the quasigroup; while, as shown in Chapter 2, these in turn influence the structure of the latin square. Conversely, with each given 3-net, there is associated a class of isotopic quasigroups and related latin squares.

We go on to show that a k-net, for k > 3, is correspondingly associated with a set (or sets) of k − 2 MOLS. In particular, when k = n +1, the k-net becomes a projective plane and the n − 1 MOLS are then a complete set of MOLS. We point out that non-isomorphic projective planes exist for some orders n and explain how this leads to the existence of structurally distinct complete sets of MOLS of those orders.

In the third section, we discuss various connections between latin squares and graphs and indicate how these connections help in the solution of latin square problems and vice versa.

8.1 Quasigroups and 3-nets

The concept of a 3-net arises naturally in connection with the problem of assigning co-ordinates to the points and lines of an affine or projective plane. Historically, the concept arose also in the study of certain topological problems of differential geometry. Among early papers on the subject are Baer(1939,1940), Blaschke(1928), Blaschke and Bol(1938), Bol(1937), Reidemeister(1929) and Thomsen(1930). Later papers concerning the connections between quasigroups, geometric nets and projective planes are Bruck(1951), Ostrom(1968) and Pickert(1954). Extensive bibliographies of papers on the subject will be found in Aczél, Pickert and Radó(1960), in Aczél’s survey paper (1964) or (1965), in Bruck(1958), Pickert(1955) and Chapter 11 of Belousov(1967b). Two books devoted to the connection between nets and quasigroups are Belousov (1971,1972).

More recently, the subject has been treated in Chapter 2 of Pflugfelder(1990) (where it is shown in particular that the representation of a quasigroup by a geometric net leads naturally to the concepts of parastrophy and isostrophy(paratopy). Also, several chapters of Chien, Pflugfelder and Smith(1990) treat different aspects of the subject. (In the latter books, the word web is used in place of net.) The subject is also treated in various sections of the CRC Handbook of Combinatorial Designs [Colbourn and Dinitz(1996,2006)] where, in particular, the fact that a geometric net and a transversal design are geometrically dual concepts is pointed out.

Let us begin by giving a general definition of a net as used in geometry. We should mention here that the “lines” of our definition may be curves of the real plane in the applications to differential geometry or to nomograms.

Definition

A geometric net is a set of objects called “points” together with certain designated subsets called “lines”. The lines occur in classes called “parallel classes” such that (a) each point belongs to exactly one line of each parallel class; (b) if l ₁ and l ₂ are lines of different parallel classes, then l ₁ and l ₂ have exactly one point in common; (c) there are at least three parallel classes and at least two points on a line. A net possessing k parallel classes is called a k-net. (If the number of parallel classes is one or two and the remaining conditions are fulfilled, the system may be called a trivial net.)

If the net is finite, then it is characterized by a parameter n, called the order of the net, such that (i) each line contains exactly n points; (ii) each parallel class consists of exactly n lines; and (iii) the total number of points is n ².

Statements (i) and (ii) follow at once from conditions (a) and (b) of the definition of a net as soon as we postulate that one line of one parallel class has n points or that one parallel class has n lines. Then, since the lines of any one of the parallel classes contain all the points and since each of the n lines of this class has n points, statement (iii) follows. (Note that the number of parallel classes may be more or less than n.)

Definition

An affine plane π* comprises a set of objects called “points” together with certain distinguished subsets called “lines” such that (a) two distinct points belong to (are incident with) exactly one line; (b) every point exterior to a given line l of π* is incident with exactly one line which has no point in common with l; and (c) there are at least three points not all incident with one line.

The connection between affine planes and geometric nets follows immediately from the statement that:

Theorem 8.1.1

An affine plane is a geometric net in which each pair of points is incident with a line. (Equivalently, we may say that an affine plane of order n is a net of order n with n + 1 parallel classes.)

Proof

Let l be a line of the net containing n points and let P be a point not on l. Then there are exactly n + 1 lines through P if each pair of points of the net is connected by a line: for the joins of P to the points of l give n lines and there is also one line through P belonging to the parallel class of l. These n + 1 lines through P necessarily belong to distinct parallel classes, so there are n + 1 parallel classes. □

For the purpose of introducing co-ordinates for the points of a geometric net or an affine plane, we may assign arbitrary symbols to the lines of just two of its parallel classes, C ₁ and C ₂, and then assign the co-ordinate pair (x, y) to the point through which pass the line x of class C ₁ and the line y of class C ₂. There will be no loss of generality in using symbols from the same set Q (of cardinal n) for each of the two parallel classes C ₁ and C ₂. If the same set Q of symbols is used to label the lines of a third parallel class C ₃ and if the line w of this class is incident with the point (x, y), then we can define a binary operation (*) on the set Q by the statement x * y = w. The properties of the geometric net then ensure that each equation x * y = w is uniquely soluble for x, y or w in Q when the other two variables are specified, and so (Q, *) is a quasigroup.

Conversely, we may prove:

Theorem 8.1.2

If a bordered latin square of order n is given representing the multiplication table of a quasigroup (Q, *), then there can be associated with it a geometric net of order n having exactly three parallel classes and such that the lines x, y of the parallel classes C ₁ and C ₂ are incident with the line w of the parallel class C ₃ if and only if x * y = w.

Proof

As the n ² points of our 3-net, we take the n ² ordered pairs (x, y) of our quasigroup (Q, *). For each fixed choice of x, the n points (X, y), y ∈ Q, form a line l X ( 1 ) of the parallel class C ₁. For each fixed choice of y, the n points (x, Y), x ∈ Q, form a line l Y ( 2 ) of the parallel class C ₂. For each fixed choice of w, the set of all points (x, y) such that x * y = W form a line l W ( 3 ) of the parallel class C ₃. Since the multiplication table of (Q, *) is a latin square, each line of C ₃ has exactly n points.

It is immediate from the definitions that no two lines of C ₁ or C ₂ or C ₃ have a point in common and that each point belongs to exactly one line of each parallel class. Also, two lines belonging to distinct parallel classes have exactly one point in common. The lines l X ( 1 ) and l Y ( 2 ) have the point (X, Y) in common. The lines l X ( 1 ) and l W ( 3 ) have the point (X, y ¯ ) in common. where y ¯ is the unique solution of the equation X * y ¯ = W . The lines l Y ( 2 ) and l W ( 3 ) have the point ( x ¯ , Y) in common. where x ¯ is the unique solution of the equation x ¯ * Y = W . This completes the proof. □

As an example, we give in Figure 8.1.1 below a quasigroup of order 4 and its associated 3-net N.

Fig. 8.1.1

We shall show shortly that the algebraic properties of the quasigroup (Q.*) are reflected in the geometrical properties of its associated 3-net.

There is a close connection between an affine plane and a projective plane which latter we defined in Section 5.2. Indeed, the former may be regarded simply as a projective plane from which one line has been deleted. Precisely, we may make the following statement:

A projective plane of order n is an affine plane to which one extra line l _∞ has been adjoined, each of the n + 1 points of l _∞ being a point of concurrence (point at infinity) for the n + 1 lines of a parallel class. (Such a point on l _∞ is sometimes called the vertex of the parallel class.) Thus, a projective plane has a total of n ² + n + 1 lines and n ² + n +1 points. When one line and the points on it are deleted, we get a geometric net of order n having n + 1 parallel classes. That is, we get an affine plane.

In co-ordinatizing an affine (or projective) plane, it is usual to introduce two binary operations denoted by (+) and (·) respectively, the first being associated with a 3-net whose three “parallel” classes have their vertices A, B, E collinear on the special line l _∞ (that is, the lines of each parallel class are “parallel” in the sense used with reference to an affine plane), and the second being associated with a 3-net such that two of its “parallel” classes coincide with two of those of the addition net and have vertices on l _∞ while the third one comprises the pencil of lines through a finite point O say. The finite point (vertex of the parallel class) is regarded as having been deleted when treating the system as a net. More details are given in the next section of this chapter.

In the case of the real affine plane, these binary operations coincide with addition and multiplication of real numbers if the four parallel classes in question comprise the lines parallel to the x-axis, the lines parallel to the y-axis, the lines of gradient 1 and the lines through the origin O of cartesian co-ordinates.

Let us consider further the relation between latin squares and geometric 3-nets. In the first place, let us observe that if a 3-net is given, the choice of co-ordinatizing set Q and the procedure for assigning its elements one-to-one to the lines of each parallel class are not unique. Indeed, it is easy to see that change of the co-ordinatizing set of a 3-net N corresponds to a change of symbols in the associated latin square L, while changes of the order in assigning the elements of a given set of symbols to the lines of the parallel classes correspond to reorderings of (i) the row labels, (ii) the column labels, and (iii) the symbols in the body of the associated (bordered) latin square.

Equivalently, we may state:

Theorem 8.1.3

Isotopic quasigroups ¹ are associated with the same geometric 3-net and correspond to changes in the labelling set.

Proof

To see this, let (G, ·) and (H, *) be two quasigroups. These quasigroups are isotopic if there exists an ordered triple (θ, φ, ψ) of one-to-one mappings θ, φ, ψ of G onto H such that (xθ) * (yφ) = (x · y)ψ for all x, y in G. Geometrically, the mapping θ effects a replacement of the symbols of the set G which are assigned to the lines of one parallel class C ₁ of a geometric net by symbols of the set H. The mappings φ and ψ respectively effect similar re-labellings of the lines of the parallel classes C ₂ and C ₃. In the re-labelled set, the lines of the classes C ₁ and C ₂ labelled xθ and yφ are incident with the line (x · y)ψ when (xθ) * (yφ) = (x · y)ψ: that is, when the lines of the classes C ₁ and C ₂ which were originally labelled x and y are incident with the line of C ₃ which was originally labelled x · y. The latter lines are the same as the former. □

Corollary

Isotopisms of a quasigroup (G, ·) onto itself correspond to changes of order in the labelling set G of the associated, 3-net.

Proof

The mappings θ, φ, ψ, are now mappings of the set G onto itself. That is, they represent permutations of the labelling set. □

In Chapter 1, we proved that every isotope (H, *) of a quasigroup (G, ·) is isomorphic to a principal isotope of the quasigroup (Theorem 1.3.2) and that, among the principal isotopes of a quasigroup (G, ·), there always exist loops (Theorem 1.3.3). These facts imply the truth of the following theorem:

Theorem 8.1.4

If (G, ·) is a quasigroup associated with a given 3-net, then there are as many isomorphically distinct quasigroups associated with that net as there are principal isotopes of (G, ·). Moreover, among these quasigroups there always exist loops. Consequently any 3-net has loops among its co-ordinate systems.

We can interpret Theorem 1.3.3 of Chapter 1 geometrically as follows: In the 3-net whose parallel classes are the lines through the points X, Y, W, we may select the particular lines of the (X) and (Y) parallel classes which carry the labels u, v of (G, ·) as the ones to be re-labelled as the identity lines e for the principal isotope (G, ⊗). The point of intersection U of these particular lines will be called unit point. We now re-label the lines of the parallel classes (X) and (Y) in such a way that if w_i is any line of the parallel class (W) other than the line WU, then the line of the parallel class (X) through the point w_i ∩ YU will be labelled w_i and the line of the parallel class (Y) through the point w_i ∩ XU will also be labelled w_i . In the quasigroup (G, ⊗) thus defined, e ⊗ w_i = w_i = w_i ⊗ e. Moreover, if we now consider how we should re-label the line WU, we see that it should carry the same label e as XU and YU. So, the identity element e of (G, ⊗) is the element uv of (G, ·) as in Theorem 1.3.3. (See Figure 8.1.2.)

Fig. 8.1.2

Let us now show as promised how the two most important properties of a quasigroup are reflected in the geometrical properties of its associated 3-net.

Before doing so, it is desirable to mention again that, in plane projective geometry, two distinct types of 3-net arise, affine nets and triangular nets. In the first, the points A, B, E of l _∞ take the roles of X, Y, W and the parallel classes are the pencils with the collinear vertices A, B, E. For such nets, the quasigroup is usually written additively. Lines through E have “equations” of the form y = x + a. For triangular nets on the other hand, the vertices A, B, O of a proper triangle are the vertices of three pencils of lines representing the “parallel classes” (the lines of the pencil with vertex O being no longer parallel in the geometrical sense), and, for such nets, the associated quasigroup is usually written multiplicatively. Lines through O have “equations” of the form y = xm. (See Figure 8.1.3.) If the elements of either the additive or the multiplicative quasigroup satisfy some algebraic identity, this corresponds to closure of a certain geometrical configuration.

Fig. 8.1.3

Let us consider first the algebraic effect of requiring closure of the Pappus configuration in a triangular or affine 3-net. The assertion that the Pappus configuration has incidence closure is usually called Pappus’ theorem. This may be stated as follows: if P ₁, P ₂, P ₃ and Q ₁, Q ₂, Q ₃ are two triads of collinear points, then the triad of points R ₁, R ₂, R ₃, where R_i = P_jQ_k ∩ P_kQ_j (i, j, k = 1, 2, 3; i ≠ j ≠ k), are collinear. We have

Theorem 8.1.5

If the parallel classes of the net comprise the lines through the points X,Y, W and if the lines through X are denoted by x ₁, x ₂, … and the lines through Y are denoted by y ₁, y ₂, …, then Pappus’ theorem implies the algebraic relation

x 1 y 2 = x 2 y 1 and x 1 y 3 = x 3 y 1 ⇒ x 2 y 3 = x 3 y 2

for the quasigroup (G, ·), where the x_i and y_i are the symbols of G and where we identify the points P_i, Q_i, R_i with the points shown in Figure 8.1.4 .

Fig. 8.1.4

Proof

If we label the various lines of the configuration as in Figure 8.1.4, the result becomes obvious since x ₁ y ₂ = x ₂ y ₁ implies that the points P ₂, Q ₃ are collinear with W and x ₁ y ₃ = x ₃ y ₁ implies that the points P ₃, Q ₂ are collinear with W. □

To interpret the above result in terms of latin squares, let (G, ·) be a quasigroup associated with a 3-net in which the Pappus configuration has incidence closure and let a and a′ be fixed elements of the set G = {a, b ₁, b ₂, …}. Then, for b_i ∈ G, b_ia′ = h_i for some h_i ∈ G and there exists an element b_i ′ ∈ G such that ab_i ′ = h_i . Thus, to each b_i ∈ G, there corresponds another element b_i ′ ∈ G such that b_ia′ = ab_i ′. Moreover, when b_i = a, then b_i ′ = a′ since aa′ = aa′ is a tautological statement. Therefore, G = {a′, b ₁′, b₂′, …}. Then, if the Pappus configuration closes in the associated net, we shall have b_ib_j ′ = b_jb_i ′ for i, j = 1, 2, 3, …; i ≠ j. This follows from the fact that ab_i ′ = b_ia′ and ab_j ′ = b_ja′ together imply b_ib_j ′ = b_jb_i ′. Thus, the multiplication table of (G, ·) will be a bordered latin square of the form shown in Figure 8.1.5.

Fig. 8.1.5

If, instead of a triangular net with vertices X, Y, W (or say A, B, O in the application to the co-ordinatization of a projective plane discussed later), we have to deal with an affine net whose parallel classes have collinear vertices A, B and E, then the whole of the above discussion remains valid if the Pappus configuration is replaced by the Thomsen configuration [see Thomsen(1930)] which is illustrated in Figure 8.1.6. This may be regarded as the configuration obtained from the Pappus configuration when O → E on l _∞. The assertion that the Thomsen configuration has incidence closure is often called the axial minor theorem of Pappus. This may be stated as follows: If P ₁, P ₂, P ₃, Q ₂, Q ₃ are five given points such that P ₁, P ₂, P ₃ are collinear and if R ₁ is the point P ₂ Q ₃∪P ₃ Q ₂ and P ₁ R ₁ meets Q ₂ Q ₃ at Q ₁, then the points R ₁, R ₂ ≡ P ₁ Q ₃∪P ₃ Q ₁ and R ₃ ≡ P ₁ Q ₂ ∪ P ₂ Q ₁ are collinear.

Fig. 8.1.6

We consider next the algebraic consequence for a triangular net of requiring closure of the large Reidemeister configuration [see Reidemeister(1929)]. This asserts that, if the quadrangles P ₁ P ₂ P ₃ P ₄ and P ₁′P ₂’P ₃′P ₄′ have the joins of vertices P ₁ P ₂, P ₃ P ₄, P ₁′P ₂’, P ₃′P ₄′ concurrent in a point B, P ₂ P ₃, P ₁ P ₄, P ₂′P ₃′, P ₁′P ₄′ concurrent in a point A and P ₁ P ₁′, P ₂ P ₂′, P ₃ P ₃′, concurrent in a point O, then the join P ₄ P ₄′ passes through the same point O (see the left-hand diagram in Figure 8.1.7). In Argunov(1950), this configurational proposition has been denoted by the symbol mA(11, 11, 12).

Fig. 8.1.7

We have the following important result.

Theorem 8.1.6

If the lines through the point A have symbols x ₁, x ₂, …, and the lines through the point B have symbols y ₁, y ₂, …, then closure of the large Reidemeister configuration implies satisfaction of the algebraic relation

x 1 y 2 = x 2 y 1 , x 1 y 4 = x 2 y 3 and x 3 y 2 = x 4 y 1 ⇒ x 3 y 4 = x 4 y 3

in the quasigroup (G, ·) associated with the net whose parallel classes are the pencils of lines through the points A, B and O.

Proof

If we label the various lines of the configuration as in the left-hand diagram of Figure 8.1.7, the result becomes obvious since the first three equalities in the implication statement respectively imply that the pairs of points P ₂, P ₂′; P ₃, P ₃′; and P ₁, P ₁′ are collinear with the point O. □

Let us observe that the algebraic relation given in Theorem 8.1.6 is precisely the quadrangle criterion which was first introduced in Theorem 1.2.1. This observation makes it clear that our next result is only to be expected.

Theorem 8.1.7

Closure of the large Reidemeister configuration in the triangular 3-net associated with the quasigroup (G, ·) implies that all loops isotopic to (G, ·) are groups.

Proof

Let x⊗y = (xΣ)·(yτ), where xΣ ⁻¹ = xy ₁ and yτ ⁻¹ = x ₁ y. Then (G, ⊗) is a loop-principal isotope (LP-isotope) of (G, ·) with identity element x ₁ y ₁ by Theorem 1.3.3. Let p, q, r be arbitrarily chosen in G. Then, for fixed choices of x ₁ and y ₁, there exist elements x ₂, y ₂, x ₃ and y ₃ of G such that p = x ₃ y ₁, q = x ₁ y ₂ = x ₂ y ₁ and r = x ₁ y ₃. For x ₂, y ₂, x ₃ and y ₃ so defined, there are elements x ₄ and y ₄ in G such that x ₁ y ₄ = x ₂ y ₃ and x ₄ y ₁ = x ₃ y ₂. By the hypothesis of the theorem, we then have x ₃ y ₄ = x ₄ y ₃. Also,

( p ⊗ q ) ⊗ r = [ ( x 3 y 1 ) ⊗ ( x 1 y 2 ) ] ⊗ r = ( x 3 σ − 1 ⊗ y 2 τ − 1 ) ⊗ r = ( x 3 y 2 ) ⊗ r = ( x 4 y 1 ) ⊗ ( x 1 y 3 ) = x 4 σ − 1 ⊗ y 3 τ − 1 = x 4 y 3 ;

and

p ⊗ ( q ⊗ r ) = p ⊗ [ ( x 2 y 1 ) ⊗ ( x 1 y 3 ) ] = p ⊗ ( x 2 σ − 1 ⊗ y 3 τ − 1 ) = p ⊗ ( x 2 y 3 ) = ( x 3 y 1 ) ⊗ ( x 1 y 4 ) = x 3 σ − 1 ⊗ y 4 τ − 1 = x 3 y 4

Therefore, (p ⊗ q) ⊗ r = p ⊗ (q ⊗ r) and every LP-isotope of (G, ·) is associative. Since every loop isotopic to (G, ·) is isomorphic to a principal isotope, the statement of the theorem follows. □

The following result is both interesting and important.

Theorem 8.1.8

If all the loop-principal isotopes of the quasigroup (G, ·) are commutative, they are all associative too.

Proof

Let a, b, c be arbitrary elements of the quasigroup (G, ·) and let u, υ be fixed elements of (G, ·). Then there exist elements s, t such that a = us and b = ut. Also, there exists an element w such that c = wυ.

Let x ⊗ y = (xσ) · (yτ), where xσ ⁻¹ = xυ and yτ ⁻¹ = uy (so that sτ ⁻¹ = a and tτ ⁻¹ = b). Then (G, ⊗) is an LP-isotope of (G, ·) with identity element uυ as in the previous theorem. Also, let x ⊕ y = (xσ) · (yθ), where yθ ⁻¹ = wy (whence υθ ⁻¹ = wυ = c). Then (G, ⊕) is another loop-principal isotope of (G, ·) with identity element wυ = c.

Thence, h ⊗ b = (hσ) · (bτ) = (hσ) · t = h ⊕ (tθ ⁻¹) = h ⊕ (wt) = h ⊕ (wσ ⁻¹ ⊗ tτ ⁻¹) = h ⊕ [(wυ) ⊗ (ut)] = h ⊕ (c ⊗ b).

In particular, putting h = (c ⊗ a), we get (c ⊗ a) ⊗ b = (c ⊗ a) ⊕ (c ⊗ b) for arbitrary elements a, b, c ∈ G.

Similarly, h ⊗ a = (hσ) · (aτ) = (hσ) · s = h ⊕ sθ ⁻¹) = h ⊕ (ws) = h ⊕ (wσ ⁻¹ ⊗ sτ ⁻¹) = h ⊕ [(wυ) ⊗ (us)] = h ⊕ (c ⊗ a). In particular, putting h = (c ⊗ b), we get

( c ⊗ b ) ⊗ a = ( c ⊗ b ) ⊗ ( c ⊗ a )

Since ⊕ is commutative by hypothesis 2 , we deduce that (c ⊗ a) ⊗ b = (c ⊗ b) ⊗ a and thence, since ⊗ also is commutative, (a ⊗ c) ⊗ b = a ⊗ (c ⊗ b) and so (G, ⊗) satisfies the associative law, as claimed. □

Corollary 1

Under the hypotheses of the theorem (that is, in a net for which Pappus’ theorem is satisfied relative to the parallel classes with vertices A, B, O), every loop isotopic to (G, ·) is an abelian group.

Proof

As every isotope of a quasigroup is isomorphic to a principal isotope by Theorem 1.3.2, it follows that every loop isotopic to (G, ·) is isomorphic to an LP-isotope. The latter are commutative and associative, so they are abelian groups. □

Corollary 2

If Pappus’ theorem holds relative to the vertices A, B, O for all choices of lines with one line fixed through O, then it holds for all choices of lines through O.

Proof

In the argument above, the mapping σ is kept fixed as the LP-isotope varies. Geometrically, this corresponds to using the same line y = xυ through O throughout. □

In the first corollary to Theorem 8.1.8 above, we showed that, in a triangular net for which Pappus’ theorem is satisfied relative to the parallel classes with vertices A, B and O, every co-ordinatizing loop is an abelian group. This means, a fortiori, that every such loop is associative and so the large Reidemeister configuration closes (since (p ⊗ q) ⊗ r = p ⊗ (q ⊗ r) implies that x ₄ y ₃ = x ₃ y ₄ in Theorem 8.1.8). Thus, the geometric equivalent of Theorem 8.1.8 is the following:

Theorem 8.1.9

Closure of the Pappus configuration relative to the parallel classes with vertices A, B and O in a projective plane implies closure of the large Reidemeister configuration relative to these same parallel classes.

A wholly geometrical proof of this result is possible. See Hessenburg(1905) and Klingenberg(1952,1955).

When O → E (a point on AB), our triangular net is replaced by an affine net and the large Reidemeister configuration is replaced by the small Reidemeister configuration, denoted by the symbol aA(10; 11,13) in Argunov(1950) ³ and illustrated in the right-hand diagram of Figure 8.1.7.

In the application to co-ordinatizing a projective plane, closure of the latter configuration is the geometrical condition that the additive loop of the coordinate system of the projective plane is associative. The geometrical equivalent of Theorem 8.1.8 for such an affine net is

Theorem 8.1.10

Closure of the Thomsen configuration (or validity of the axial minor theorem of Pappus) relative to the parallel classes with vertices A, E and B in a projective plane implies closure of the configuration aA(10; 11, 13) relative to those same parallel classes.

A purely geometrical proof of this result has been given in Keedwell(1964).

Among the further infinite number of configurational propositions whose algebraic interpretations relative to a given 3-net we might consider, the so-called Bol configurations [first introduced by Bol(1937)], the central minor theorem of Pappus and the hexagon configuration have shown themselves to be of most importance. ⁴

However, it would be inappropriate in the present text to discuss the algebraic implications of each of these configurations in full detail and so we shall content ourselves with a summary of the most important results ⁵ .

The Bol configurations arise from the Reidemeister configurations when P ₁ lies on P ₃ P ₃′ (see Figure 8.1.8) and are denoted by mA(10; 11,11) and aA(9; 11,12) respectively in Argunov’s notation.

Fig. 8.1.8

From the manner of the derivation of these configurations from the Reidemeister configurations, it is immediately clear that the roles of the vertices A, B, O are no longer interchangeable. (It can be shown that closure of the Pappus and Reidemeister configurations relative to the parallel classes with vertices A, B, O taken in any one order implies their closure relative to these parallel classes taken in any other order. In particular, the following re-labelling of the points in the left-hand diagram of Figure 8.1.7 shows that the roles of O and B are interchangeable for the large Reidemeister configuration. Let

P ′ 2 P ′ 2 P 3 P ′ 3 → Q 1 Q 2 Q 3 Q 4 and P ′ 1 P 1 P 4 P ′ 4 → Q ′ 1 Q ′ 2 Q ′ 3 Q ′ 4 .

This shows us that, when the Reidemeister configuration has incidence closure with respect to the quadrangles P ₁ P ₂ P ₃ P ₄ and P ₁′P ₂′P ₃′P ₄′, it also has incidence closure with respect to the quadrangles Q ₁ Q ₂ Q ₃ Q ₄ and Q ₁′Q ₂′Q ₃′Q ₄′ and, for the latter quadrangles, the roles of the vertices O and B are interchanged)

If the vertices A, O, B are as in Figure 8.1.8, closure of the configuration mA(10; 11, 11) implies the condition

x 1 y 2 = x 2 y 1 and x 1 y 4 = x 2 y 3 = x 3 y 2 = x 4 y 1 ⇒ x 3 y 4 = x 4 y 3 ( condition B 3 ) .

If O and A are interchanged and the lines are suitably labelled (P ₂ P ₂′, P ₁ P ₁′, P ₄ P ₄′ as x ₁, x ₂, x ₄ and P ₃′P ₄′, P ₁′P ₂′, P ₃ P ₄, P ₁ P ₂ as y ₁, y ₂, y ₃, y ₄ respectively), then closure of the configuration implies the condition

x 1 y 2 = x 2 y 1 , x 1 y 4 = x 2 y 3 and x 3 y 2 = x 4 y 1 ⇒ x 2 y 4 = x 4 y 3 ( condition B 1 ) .

Finally, if O and B are interchanged instead and the lines are suitably labelled, then closure of the configuration implies the condition

x 1 y 2 = x 2 y 1 , x 1 y 4 = x 2 y 2 and x 3 y 2 = x 4 y 1 ⇒ x 3 y 4 = x 4 y 3 ( condition B 2 ) .

J. Aczél [in (1964) or its English equivalent (1965)] has shown algebraically that conditions B ₁ and B ₂ together imply condition B ₃ [a result originally proved in Bol(1937)] and he has also demonstrated the following results:

1. (1) condition B ₁ implies that all the LP-isotopes of the quasigroup (G, ·) are M ₁-loops: that is, loops with the property y(z · yx) = (y · zy)x for all x, y, z in the loop;
2. (2) condition B ₂ implies that all the LP-isotopes of the quasigroup (G, ·) are M ₂-loops: that is, loops with the property (xy · z)y = x(yz · y) for all x, y, z in the loop;
3. (3) if a loop is an M ₁-loop and an M ₂-loop, then it is a Moufang loop: that is, it has the property (xy · z)y = x(y · zy);
4. (4) if a loop is an M ₁-loop, its associated net satisfies condition B ₁; if a loop is an M ₂-loop, its associated net satisfies condition B ₂; if a loop is Moufang, its associated net satisfies all of the conditions B ₁, B ₂, B ₃.
   An equivalent set of results has also been given by Bruck(1963b). One implication of these results is that the multiplicative loop of any co-ordinate system of a projective plane that is based on the co-ordinatizing points A, B, O, E will be Moufang if and only if the configuration mA(10; 11, 11) has incidence closure relative to the “parallel” classes with vertices A, B and O.
   The central minor theorem of Pappus is the geometric dual of the axial minor theorem of Pappus discussed earlier. It is illustrated in the left-hand diagram of Figure 8.1.9. For a triangular net, its closure implies the condition

   x 1 y 2 = x 2 y 1 and x 1 y 3 = x 2 y 2 = x 3 y 1 ⇒ x 2 y 3 = x 3 y 2 ( condition H ) .

   

   
   

   
   

   Fig. 8.1.9

   
   For an affine net, the same condition is implied by the third minor theorem of Pappus: that is, by closure of the hexagon configuration which arises from the central minor theorem when O → E on AB. The third minor theorem of Pappus may be stated as follows: if P ₁, P ₂, Q ₁, Q ₂ are four points which form a proper quadrangle and if R ₃ is the point P ₁ Q ₂ ∩ P ₂ Q ₁, S is the point P ₁ P ₂ ∩ Q ₁ Q ₂, R ₃ S intersects P ₁ Q ₁ at R ₁ and P ₂ R ₁ ∪ Q ₁ Q ₂ ≡ Q ₃, Q ₂ R ₁ ∪ P ₁ P ₂ ≡ P ₃, then the point R ₂ ≡ P ₁ Q ₃ ∪ P ₃ Q ₁ lies on R ₁ R ₃ (see the right-hand diagram of Figure 8.1.9).
   The following facts are well-known:
   1. (5) Condition H implies and is implied by the statement that all loops isotopic to (G, ·) are power associative.
   2. (6) Condition H implies and is implied by the statement that, in each loop isotopic to (G, ·), each element has a two-sided inverse.

With the aid of the results (5) and (6), it is quite easy to prove the following important result:

Theorem 8.1.11

If all loops isotopic to the quasigroup (G, ·) are power associative, then they are all strongly power associative too. That is, if in any loop isotope (G, ⊗) of (G, ·) we define xⁿ by x ⁰ = e and xⁿ = x ⊗ x^{n −1} for n > 0, x ⁻¹ by x ⁻¹ ⊗ x = e and xⁿ = (x ⁻¹)⁻ⁿ for n < 0, then x^m ⊗ xⁿ = x^{m +n} for all integers m and n.

The interested reader will find proofs of all these results in Aczél(1964,1965).

We may summarize the results of this section by saying that every quasigroup (G, ·) (that is, every bordered latin square) determines a 3-net of a particular geometrical type which it co-ordinatizes. Conversely, to each such particular 3-net there corresponds a family of isotopic quasigroups any one of which coordinatizes it and this family includes loops. An identity such as (p ⊗ p) ⊗ p = p ⊗ (p ⊗ p) (validity of power associativity) which is valid in all loops isotopic to the quasigroup (G, ·) corresponds to closure of a certain geometrical configuration in the associated 3-net. This leads to the following definition:

Definition

An identity in a loop (G, ⊗) is called universal if it is satisfied in every loop isotopic to (G, ⊗).

Belousov and Ryzkov(1966) have given an algorithm for constructing the closure figure corresponding to a given universal identity and, as an illustration, have applied it to the Moufang identity x ⊗ [y ⊗ (x ⊗ z)] = [(x ⊗ y) ⊗ x] ⊗ z.

Some further discussion of connections between quasigroups and geometric nets will be found in Neumann(1960,1962), Sade(1958b) and Belousov(1967d).

This topic has recently undergone a renascence by the study of 3-nets whose points and lines are those of a projective plane. See Urzúa(2010), Blokhuis, Korchmáros and Mazzocca(2011). Korchmáros, Nagy and Pace(2014).

8.2 Orthogonal latin squares, k-nets and introduction of co-ordinates

In the previous Section, we defined a k-net and showed that every 3-net N defines a class of corresponding latin squares (representing the multiplication tables of a set of isotopic quasigroups Q_N ) and that the geometrical properties of the 3-net are reflected in the algebraic properties of the quasigroups associated with these squares. Also, in Section 5.2, we showed that each (n + 1)-net of order n (that is to say, each affine plane) defines a set of mutually orthogonal latin squares and conversely. Both of these results are special cases of the general statement that each geometric k-net N of order n defines and is defined by a corresponding set of k − 2 MOLS of order n.

Moreover, the discussion of the previous section makes it evident that the algebraic properties of the quasigroups whose multiplication tables are represented by these latin squares reflect geometrical properties of the various corresponding sub-3-nets of the net N.

A slight modification of the argument of Theorem 8.1.2 is all that is necessary to show that our general statement is true.

In view of its importance, we formulate it as a theorem:

Theorem 8.2.1

Each geometric k-net N of order n defines, and is defined by, a corresponding set of k − 2 MOLS of order n.

Proof

We designate the various parallel classes of the k-net N by calligraphic letters A , E , B 1 , B 2 , … , B k − 2 . Let the lines of these parallel classes be labelled as follows: a ₁, a ₂, …, a _n are the lines of the class A ; e ₁, e ₂, …, e_n are the lines of the class E ; b_{j 1}, b_{j 2}, …, b_jn are the lines of the class B j . Every point P(h, i) of N can then be identified with a set of k numbers (h, i, l ₁, l ₂, …, l_{k −2}) describing the k lines e h , a i , b 1 l 1 , b 2 l 2 , … , b k − 2 l k − 2 with which it is incident, one from each of the k parallel classes, and a set of k − 2 MOLS can be formed in the following way: In the jth square, put l_j in the (h, i)th place. Each square is latin since, as h varies with i fixed, so does l_j ; and, as i varies with h fixed, so does l_j . Each two squares L_p and L_q are orthogonal: for, if not, we would have two lines belonging to distinct parallel classes with more than one point in common.

Conversely, from a given set of k − 2 MOLS, we may construct a k-net N. We define a set of n ² points (h, i), h = 1, 2, …, n; i = 1, 2, …, n; where the point (h, i) is to be identified with the k-tuple of numbers (h, i, l ₁, l ₂, …, l_{k −2}), l_j being the entry in the hth row and ith column of the jth latin square L _j . We form kn lines b_jl , j = −1, 0, 1, 2, …, k − 2; l = 1, 2, …, n; where b_jl is the set of all points whose (j + 2)th entry is l and b _−1l ≡ e_l , b _0l ≡ a_l . Thus, we obtain k sets of n parallel lines. (Two lines are parallel if they have no point in commom) Also, from the orthogonality of the latin squares, it follows that any two lines from distinct parallel classes intersect in one and only one point, so we have a k-net □

Bruck(1951) has used the representation of a set of k − 2 MOLS by means of a k-net to obtain an interesting criterion for such a set of squares to have a common transversal and hence has obtained a simple necessary (but not sufficient) condition for such a set of squares to be extendible to a larger set (of the same order) In a subsequent paper, Bruck(1963a), and again using the net representation, he has obtained a sufficient condition in terms of the relative sizes of k and n for a set of MOLS to be extendible to a complete set We gave a detailed account of these results in Chapter 9 of [DK1] However, Bruck’s results have more recently been improved by Metsch(1991) See the next section.

In his well-known paper M.Hall(1943), that author has shown that co-ordinates may be introduced into an arbitrary projective plane (or k-net) in the following way:

We select any two points A, B in the given projective plane π. If from π we remove the line l _∞ joining A, B and the points on l _∞, the remaining plane π* is an affine plane. We use A and B as centres of perspectivities to introduce coordinates for the points of π*. No ambiguity will arise if, as we shall sometimes find convenient, we speak of π and π* as the same plane as long as l _∞ is fixed.

Let the lines of the pencil through A in π* be denoted by x = x ₀, x = x ₁, …, x = x_{r −1}, where r is their cardinal number and x ₀, x ₁, …, x_{r −1} are r different symbol Similarly, denote the lines of the pencil through B by y = y ₀, y = y ₁, …, y = y_{r −1}. (The cardinal number of the y’s is necessarily the same as that of the x’s.) Through every point P of π*, there is exactly one line x = x_i and one line y = y_j . Denote P by (x_i , y_j ). On an arbitrary line L of π*, not through A or B, there are points (x_i , y_j ) where each x and each y occurs exactly once. Henceforward, suppose that the symbols x ₀, x ₁, …, x_{r −1} are the same as y ₀, y ₁, …, y_{r −1}, though not necessarily in the same order. Then, an arbitrary line L, not through A or B, is associated with the permutation ( … x i … … y i … ) , where the (x_i , y_i ) are the points of L. This expresses the fact that L determines a one-to-one correspondence between the lines of the pencil through A and the lines of the pencil through B. Without confusion we may write L = ( … x i … … y i … ) since distinct lines contain at most one point in common and hence are associated with distinct permutations.

It is evident that the same method of co-ordinatization may be used for a k-net of order r.

We now choose two particular points O and I which are joined by a line but are not collinear with A or B and assign them the co-ordinates (0,0) and (1,1) respectively. (In the case of a projective plane, every two points are joined by a line and so the choice of O and I is entirely arbitrary.) This assignment of co-ordinates is equivalent to assigning the labels 0, 1 to two of the symbols x ₀, x ₁, …, x_{r −1}, say x ₀ = 0, x ₁ = 1.

Let OI meet AB at E and let the remaining points of AB be denoted by B ₂, B ₃, …, B_{k −2}, k ≤ r + 1. If the line OB_m meets the line AI at the point (1, m), denote the point B_m by the symbol (m). In particular, denote the point E(≡ B ₁) by the symbol (1). We are now able to define operations (+) and (★) on the symbols x ₀, x ₁, …, x_{r −1} by means of which the lines of the pencils with vertices E and O may be assigned equations. Each line through E has a permutation representation of the form ( 0 … x i … a … y i … ) . We define x_i + a = y_i for i = 0, 1, 2, …, r − 1 and say that the line has equation y = x + a. This defines the result of the operation (+) on every ordered pair of the r symbols. Each line through O has a permutation representation of the form ( 0 1 … x i … 0 m … y i … ) . We define x _i ★ m = y_i for i = 0, 1, 2, …, r − 1 and say that the line has equation y = x ★ m. This defines the result of the operation (★) for all choices of x and for k − 1 finite values of m.

We can provide equations for the remaining lines of the plane with the aid of a ternary operation defined on the set of symbols x ₀, x ₁, …, x_{r −1} in the following way. If x, m, a are any three of the symbols, but with m restricted to k − 1 finite values in the case of a k-net, we define T(x, m, a) = y, where y is the second co-ordinate of the point on the line joining the points (m) and (0, a) whose first co-ordinate is x. We can then say that y = T(x, m, a) is the “equation” of the line joining the points (m) and (0, a). The connection between this ternary operation on the symbols x ₀, x ₁, …, x_{r− 1} and the binary operations (+) and (★) previously introduced is given by the relations a + b = T(a, 1, b) and a ★ b = T(a, b, 0). We may also observe that, both in the case of a complete projective plane and in the case of a k-net with k < r + 1, the lines which pass through the point E are those which are represented in the permutation representation by permutations which displace all symbols and by the identity permutation. We shall denote this subset of the set S of permutations representing the lines by the symbol S ¯ .

Since each finite projective plane of order n defines, and is defined by, a complete set of n − 1 mutually orthogonal latin squares of order n (see Theorem 5.2.2), it is evident that the answer to the question “How many non-equivalent complete sets of mutually orthogonal latin squares of order n exist?” is closely related to the question ⁶ “How many geometrically distinct projective planes of order n exist?”. We have already shown that there exists a Galois or desarguesian ⁷ plane of every positive integral order n that is a power of a prime number (Theorem 5.2.3) and we wish now to demonstrate the existence of non-desarguesian planes.

The simplest type of non-desarguesian projective planes to describe are the so-called translation planes.

We may specify such a plane by the nature of its co-ordinate system. We suppose co-ordinates to have been introduced into the plane in the manner described above, so that there is a special line AB = l _∞ whose points are represented by symbols (m), there are two special points (0,0) and (1,1), and so that all other points are represented by co-ordinate pairs (x, y), where m, x, y belong to a coordinate set Σ. Also lines through A have equations of the type x = x_r , lines through B have equations of the form y = y_r and all other lines have equations of the form y = T(x, m, a), where T is a ternary operation on the set Σ. Further, by means of T, binary operations (+) and (★) may be defined on Σ. If then the algebraic system (Σ, +, ★) has the properties (i) (Σ, +) is an abelian group with 0 as its identity element, (ii) (Σ − 0, ★) is a loop with 1 as its identity element, (iii) (a + b) ★ m = (a ★ m) + (b ★ m) for all a, b, m in Σ, and (iv) if r ≠ s, the equation x ★ r = (x ★ s) + t has a unique solution x in Σ when r, s, t are in Σ, we say that it is a Veblen Wedderburn system or a right quasifield. If, further, the ternary operation T on Σ satisfies the condition T(a, m, b) = a ★ m + b, then we may easily verify as below that the axioms for a projective plane are satisfied and we call the resulting plane a translation plane. (It is easy to check that the condition T(a, m, b) = a ★ m + b is consistent with the relations describing the binary operations (+) and (★) in terms of T previously given.)

Proof

In the first place, we have to check that there is a unique line joining two given points (x_r , y_r ) and (x_s , y_s ). If x_r = x_s , the required unique line is that with equation x = x_r . Tf y_r = y_s the required line is y = y_s . Jf x_r ≠ x_s and y_r ≠ y_s , the required line is that with equation y = x ★ m + b where m and b satisfy the equations x_r ★ m + b = y_r and x_s ★ m + b = y_s : that is, m is the unique solution of the equation (x_r − x_s ) ★ m = y_r − y_s and b is then determined uniquely by the requirement that x_r ★ m + b = y_r . In the second place, there is a unique point common to each two lines. The lines x = x_r , x = x_s have the point A in common. Similarly, the lines y = y_r , y = y_s have the point B in common. The lines x = x_r , y = y_s have the point (x_r , y_s ) in common. The lines x = x_r and y = x ★ m + b have the point (x_r , x_r ★ m + b) in common. The lines y = y_s , y = x ★ m + b have the point (x_s , y_s ) in common, where x_s is the unique solution of the equation x_s ★ m = y_s − b.

Finally, the lines y = x★m ₁ + b ₁ and y = x★m ₂ + b ₂ intersect in the point whose x co-ordinate is the unique solution of the equation x ★ m ₁ = x ★ m ₂ + (b ₂ − b ₁) and whose y co-ordinate can then be obtained from either one of the equations of the two lines. □

It is easy to see that, in particular, every Galois field is a right quasifield. Moreover, in the case when the right quasifield is a Galois field, homogeneous coordinates can be introduced in a manner analogous to that used in elementary geometry and it is then quite simple to show that the plane is isomorphic to the Galois plane of the same order. For the details, the reader is referred to books on projective planes. [See, for example, Pickert(1955).] We deduce that the existence of finite translation planes which are geometrically distinct from the Galois planes is dependent upon the existence of finite right quasifields which are not fields.

M.Hall(1943) gave one method for constructing such quasifields but many methods for obtaining translation planes are now known and many papers on the subject have been published.

When the complete set of mutually orthogonal latin squares which are defined by a desarguesian plane, by a translation plane, or by the dual of a translation plane, are constructed and put into standardized form (see Section 5.1), it is found that the rows of any one square L_k of the set are the same as those of any other square L_h of the set, except that they occur in a different order. That this is necessarily so was proved for the case of desarguesian planes by Bose and Nair(1941). However, there exist other types of projective plane for which the squares do not have this property as the same authors pointed out, among them being a class of planes constructed by D.R.Hughes(1957) and called the Hughes planes. ⁸

From the point of view of the theory of latin squares it is therefore important to have a criterion for distinguishing the two cases. Such a necessary and sufficient condition has been given by Hughes himself [see Hughes(1955)], who has shown that linearity of the ternary operation is the required criterion, and in a more geometrical form by the present author, who has given a direct proof of the equivalent geometrical criterion: namely,

Theorem 8.2.2

A necessary and sufficient condition that, in a standardized, complete set of mutually orthogonal latin squares, the rows of the square L_k be the same as those of the square L_h, except that they occur in a different order is that the squares represent the incidence structure of a projective plane in which the first minor theorem of Desargues ⁹ holds affinely with E as a vertex of perspective and A, B_h, B_k as meets of corresponding sides of the two triangles. ¹⁰ (The notation is that used earlier in this section.)

In Figure 8.4.3 of [DK1], a complete set of MOLS of order 9 was displayed [taken from Paige and Wexler(1953)] which it was claimed represented the Hughes plane of that order but in fact they represent the dual of the unique translation plane of order 9 as has been proved by Owens(1992). For more details of how this came to light, see Section 6 of Chapter 11 in [DK2]. Since that book was published, Owens and Preece(1995,1997) have carried out a complete analysis of the possible non-equivalent sets ¹¹ of MOLS of order 9 and, for each, which plane it represents. They found that there are 19 non-equivalent sets. We also draw the reader’s attention to the facts that it is now known that there are just four different planes of order 9 (namely, the Desarguesian plane, one translation plane, its dual, and the Hughes plane) and that no projective plane of order 10 exists. It has not, so far as the author is aware been decided whether a triple of MOLS of order 10 exists though recent work, in particular that of McKay, Meynert and Myrvold(2007), makes it extremely unlikely.

For more recent work on “Latin Squares and Geometry” which supercedes and includes much of that in [DK1] other than that included here, the reader is recommended to read Chapter 11 of [DK2].

We end this section by re-presenting a problem mentioned in [DK1] but which remains unsolved.

A finite projective plane Π is said to be with characteristic h when a positive integer h exists such that, in any co-ordinatization of the plane by means of a Hall ternary ring (described earlier in this section), all elements of the loop formed by the co-ordinate symbols under the operation (+) have the same order h. In the case when h is a prime this is equivalent to requiring that each proper quadrangle (set of four points no three of which are collinear) of the plane generates a subplane of order h. Thus, for example, every desarguesian plane of order pⁿ , p prime, has characteristic p.

Two questions arise:

Firstly, as to what can be said about the orders of such planes and, secondly, whether non-desarguesian planes with characteristic can exist. As regards the case when h = 2, it has been shown by Gleason(1956) that every finite projective plane of characteristic two is desarguesian and consequently that it has order equal to a power of two. For the case h = 3, it has been shown in Keedwell(1963) that, under an additional restriction, the order must be a power of three. More recently, the same author has shown that, if h = p, p prime, then, under the same restriction, the order of the plane is a power of p. [See Keedwell(1971).] In the author’s attempt to deal with the second question for the case h = 3, it proved effective to use the latin square representation [see Keedwell(1965)] and two orthogonal latin squares suitable for the construction of a non-desarguesian projective plane in which affine quadrangles would generate subplanes of order three were quite easily constructed. However, the question as to the existence or non-existence of such planes remains unanswered to this day.

8.3 Latin squares and graphs

There are several ways of representing a latin square as an edge (or vertex) coloured graph. See Keedwell(1996) ¹² for three of these. See also Shee(1970). Such representations enable latin square problems to be translated into graph theory questions or vice versa. One which has proved particulaly useful is as follows:

Let L be a latin square of order n. We denote the complete (undirected) bipartite graph with 2n vertices by K_n,n . Let one partite set {c ₁, c ₂, …, c_n } denote the columns of L and let the second partite set {s ₁, s ₂, …, s_n } denote the symbols. If, in row r_i , symbol s_k occurs in column c_j , colour the edge [c_j , s_k ] with colour r_i . This defines a proper n-colouring of the edges of K_n,n in which the edges coloured with a particular colour form a 1-factor of K_n,n .

If we regard L as a collection of n ² triples (see page 14), we easily see that the roles of row, column and symbol can be permuted in this representation and so each latin square L defines six ways of colouring K_n,n of which up to three may be distinct.

We may use this representation to re-interpret the problem of finding partial latin squares which are uniquely completable to L (see Section 3.2) into that of finding partial edge-colourings of K_n,n which can be completed uniquely to a proper colouring of all the edges of K_n,n . For more details of this and of the general concepts of uniquely completable and critical partial colourings of the vertices or edges of a graph, see Keedwell(1994,1996); also Mahmoodian, Naserasr and Zaker(1997), who re-introduced the same idea without acknowledgement, Mahmoodian and Mahdian(1997) and Hajiabolhassan, Mehrabadi, Tusserkani and Zaker(1999), Burgess and Keedwell(2001),

Harary(1960) has pointed out that, in the above representation, a 1-factor of K_n,n whose edges have distinct colours corresponds to existence of a transversal in L. So, if no such 1-factor exists, L is without transversals and is consequently a bachelor square as defined in Section 9.1.

The above representation has also been used by Wanless in his investigation of so-called atomic latin squares (see Section 9.4). For that purpose, he needed 1-factorizations of K_n,n with the property that the union of every pair of 1-factors defines a Hamiltonian circuit of K_n,n . Such 1-factorizations are called perfect.

The similar property for 1-factorizations of the complete directed and undirected graphs K n * and K_n is closely connected to the existence of latin squares and rectangles which are row complete. (See Section 2.6 for the definition.) We explained in Section 3.1 the connections between row complete latin rectangles and decompositions of K_n into Hamiltonian paths and cycles and also decompositions into Eulerian cycles. There are analogous connections between latin squares which are row complete and decompositions of K n * . We have:

Theorem 8.3.1

If a row complete latin square of order n exists, then (i) the complete directed graph on n vertices can be separated into disjoint Hamiltonian paths, and (ii) the complete directed graph on n + 1 vertices can be separated into n disjoint Hamiltonian circuits.

Proof

For (i), we associate a directed graph with the given row complete latin square in such a way that the vertices of the graph correspond to the n distinct elements of the latin square and that an edge of the graph directed from the vertex x to the vertex y exists when and only when the elements x and y appear as an ordered pair of adjacent elements in some row of the latin square. Then, because the latin square is row complete, the graph obtained will be the complete directed graph on n vertices. Moreover, it is immediate to see that the rows of the latin square define n disjoint Hamiltonian paths into which the graph can be decomposed.

For (ii) we adjoin an extra column to the given row complete latin square L, the elements of which are equal but distinct from the n elements of the latin square. We associate a directed graph with the n × (n + 1) matrix so formed in the same way as before but this time treating each row cyclically so that if the rth row ends with the element x and begins with the element y then the associated graph has an edge directed from the vertex labelled x to the vertex labelled y. Because each element of L appears just once in its last column and just once in its first column, the directed graph on n +1 vertices which we obtain is complete. Also, the rows of the n × (n + 1) matrix define n disjoint circuits into which it can be decomposed. □

The relationship described in Theorem 8.3.1(i) has been pointed out in Dénes and Török(1970) and also in Mendelsohn(1968). That described in Theorem 8.3.1 (ii) does not seem to have been noticed until it was mentioned in [DK1].

Illustrative examples of these decompositions are given in Figure 8.3.1 and Figure 8.3.2. Figure 8.3.1 shows the decomposition of the complete directed graph with four vertices into disjoint Hamiltonian paths with the aid of the 4 × 4 complete latin square displayed earlier in Figure 2.6.1. Figure 8.3.2 shows the decomposition of the complete directed graph with five vertices into disjoint circuits of length five with the aid of the 4 × 5 matrix obtained by augmenting this same 4 × 4 complete latin square in the way described in Theorem 8.3.1.

Fig. 8.3.1

Fig. 8.3.2

By virtue of Theorem 2.6.1, decompositions of the above kind always exist when n is even. Also, as noted in Section 3.1, when the decomposition is effected with the aid of a row complete latin square formed in the manner described in Theorem 2.6.1, one half of the paths obtained are the same as the other half but described in the opposite direction.

K.O. Strauss posed the question whether a complete directed graph with an odd number n of vertices can likewise be separated into n disjoint Hamiltonian paths. By virtue of the fact that row complete latin squares of every composite order exist [see Higham(1998) and Section 2.6], the question is answered in the affirmative for non-prime odd orders but it remains unanswered for prime values of n.

Another graph problem of a similar kind to that just discussed and which has been shown by Kotzig to have connections with a particular type of latin square concerns the more general problem of the decomposition of a complete undirected graph into a set of disjoint circuits of arbitrary lengths.

In Kotzig(1970), that author gave the name P-groupoid (partition groupoid) to a groupoid (V, ·) which has the following properties: (i) a · a = a for all a ∈ V; (ii) a ≠ b implies a ≠ a · b ≠ b for all a, b ∈ V; (iii) a · b = c implies and is implied by c · b = a for all a, b, c ∈ V.

He showed that there exists a one-to-one correspondence between P-groupoids of n elements and decompositions of complete undirected graphs of n vertices into disjoint circuits. This correspondence is established by labelling the vertices of the graph with the elements of the P-groupoid and prescribing that the edges [a, b] and [b, c] shall belong to the same closed path of the graph if and only if a · b = c, a ≠ b. We illustrate this relationship in Figure 8.3.3 and from it we easily deduce:

Fig. 8.3.3

Theorem 8.3.2

In any P-groupoid (V, ·) we have (i) the number of elements is necessarily odd, and (ii) the equation x · b = c is uniquely soluble for x.

Proof

The result (i) is deduced by using the correspondence between P-groupoids and graphs just described. Since for a complete undirected graph which separates into disjoint circuits the number of edges which pass through each vertex must clearly be even, any such complete undirected graph must have an odd number of vertices all together. This is because each vertex has to be joined to an even number of others. The number of elements of a P-groupoid is equal to the number of vertices in its associated graph.

The result (ii) is a consequence of the definition of a groupoid and the fact that x · b = c implies c · b = x. □.

Corollary

The multiplication table of a P-groupoid is a column latin square.

(See Section 3.1 for the definition of the latter concept.)

The example given in Figure 8.3.3 illustrates the fact that there exist P-groupoids which are not quasigroups. This observation leads us to make the following definition:

Definition

A P-groupoid which is also a quasigroup will be called a P-quasigroup.

Theorem 8.3.3

Let (V, ·) be a P-quasigroup and let a groupoid (V, ★) be defined by the statement that a · (a ★ b) = b holds for all a, b ∈ V. Then (V, ★) is an idempotent and commutative quasigroup. Moreover, with any given idempotent commutative quasigroup (V, ★) there is associated a P-quasigroup (V, ·) related to (V, ★) by the correspondence a · b = c ⇔ a ★ c = b.

Proof

In a P-quasigroup, the equation a · x = b is uniquely soluble for x, so the binary operation (★) is well-defined. Also, a · x = b implies b · x = a so b ★ a = a ★ b; that is (V, ★) is commutative. The equation a · x = a has the solution x = a, so a ★ a = a and (V, ★) is idempotent. If the equation a ★ y = c or the equation y ★ a = c had two solutions for y, the groupoid property of (V, ·) would be contradicted ¹³ . Hence, (V, ★) is a quasigroup.

The second statement of the theorem may be justified similarly by defining the operation (·) in terms of the operation (★) by the statement that a★(a · b) = b for all a, b ∈ V. □

The multiplication table of the quasigroup (V, ★) is an idempotent symmetric latin square. Thus, a consequence of Theorem 8.3.2 and Theorem 8.3.3 above is another proof that idempotent symmetric latin squares exist only for odd orders n, a result which we may contrast with the fact that unipotent symmetric latin squares exist only when n is even. (See also Theorem 1.5.4 and Theorem 2.1.1.)

It also follows from Theorem 8.3.3 that each idempotent symmetric latin square of (necessarily odd) order n defines a P-quasigroup of order n and hence a decomposition of the complete undirected graph on n vertices into disjoint circuits.

Kotzig has pointed out that each idempotent symmetric latin square of order n also defines a partition of the complete undirected graph on n vertices into n nearly linear factors. By a nearly linear factor is meant a set F of (n − 1)/2 edges such that each vertex of the graph is incident with at most one edge of F. It is immediately clear that exactly one vertex of the graph is isolated relative to a given nearly linear factor F.

As an illustration of this concept, let us point out that the three edges [1, 2], [3, 7], [4, 6] of the complete undirected graph on seven vertices 1, 2, …, 7 form a nearly linear factor F ₅. Likewise, the three edges [1, 3], [4, 7], [5, 6] form another nearly linear factor F ₆ of the same graph. (See also Figure 8.3.4.) We shall formulate this result of Kotzig’s as a theorem:

Fig. 8.3.4

Theorem 8.3.4

To each idempotent symmetric latin square of order n there corresponds a partition of the complete undirected graph on n vertices into n nearly linear factors, and conversely.

Proof

The correspondence is established as follows. Let k be a fixed element of the idempotent commutative quasigroup (V, *) defined by the given symmetric latin square. Then there exist (n − 1)/2 unordered pairs (a_i ; b_i ) of elements of V such that a_i ★ b_i = k(= b_i ★ a_i ). These (n − 1)/2 pairs define the (n − 1)/2 edges [a_i , b_i ] of a nearly linear factor of the complete undirected graph K_n whose n vertices are labelled by the elements of V. The truth of this statement follows immediately from the fact that (V, ★) is an idempotent and commutative quasigroup and that the element k consequently occurs (n − 1)/2 times in that part of its multiplication table which lies above the main left-to-right diagonal and at most once in each row and at most once in each column.

The converse is established by defining a quasigroup (V, ★) by means of a given decomposition of K_n into nearly linear factors according to the following rules: (i) if [a_i , b_i ] is an edge of the nearly linear factor whose isolated vertex is labelled k, then a_i ★ b_i = k = b_i ★ a_i and (ii) for each symbol k ∈ V, k ★ k = k. □

Kotzig has asserted further that if n = 2k − 1 and either n or k is prime then there exists a partition of the corresponding complete graph on n vertices into n nearly linear factors with the property that the union of every two of them is a Hamiltonian path of the graph and has suggested that a partition of the same kind may exist for all odd values of n. [See Kotzig(1970).] For more recent results, see the comment on Problem 9.1 of [DK1] later on in this book.

As an example of the above situation we give in Figure 8.3.4 an idempotent and commutative quasigroup (V, ★) of order 7 which defines a decomposition of the complete graph K ₇ on seven vertices into nearly linear factors whose unions in pairs are Hamiltonian paths of K ₇.

In Figure 8.3.5 we give the P-quasigroup (V, ·) which defines and is defined by the idempotent commutative quasigroup (V, ★) of Figure 8.3.4 and show the associated partitions of the graph K ₇ into circuits.

Fig. 8.3.5

It is also easy to see that each idempotent symmetric latin square (and consequently each corresponding P-quasigroup) of order 2m − 1 defines a 1-factorization of K _2m . Let an additional vertex 0 be adjoined to K _2m−1 in Theorem 8.3.4. Then each nearly linear factor F_h of K _2m−1 defines a 1-factor of K _2m whose additional edge is [0, h]. However, as shown by a counter-example in Keedwell(1978), the correspondence between P-quasigroups of order 2m − 1 and 1-factorizations of K _2m is certainly not always one-to-one.

We showed in Theorem 6.4.1 that a Room design of order 2m is equivalent to a pair of perpendicular commutative idempotent quasigroups each of order 2m − 1. It follows that such a design is also equivalent to a pair of perpendicular P-quasigroups where

Definition

Two P-quasigroups (Q, ⊙) and (Q, ⊗) are perpendicular if (i) for a, x, y ∈ Q, the equations x ⊙ a = y and x ⊗ a = y both hold if and only if x = y = a; and (ii) for a, b ∈ Q, there is at most one pair of elements x, y ∈ Q such that x ⊙ a = y and x ⊗ b = y.

In fact, given a Room square R of side 2m − 1, we may define the (not necessarily unique) associated pair of perpendicular P-quasigroups of order 2m − 1 directly as follows: We may assume that the Room square is defined on the symbols {∞, 1, 2, …, 2m − 1}. We first permute the rows and subsequently the columns of R so as to obtain it in standard form R ^★ with the pair (∞, i) in the cell (i, i). If (b ₁, b ₁′), (b ₂, b ₂′), …, (b_{m −1}, b′ _{m −1}) are the pairs distinct from (∞, i) which are to be found in the ith row [column] of R ^★ then the ith column in the multiplication table of the P-quasigroup (Q, ⊙) [(Q, ⊗)] which is associated with the rows [columns] of R* is obtained by applying the permutation whose cycle form is (i)(b ₁, b ₁′ (b ₂, b ₂′)… (b_{m −1}, b′ _{m −1}) to the column border of (Q, ⊙) [(Q, ⊗)], where Q is the set {1, 2, …, 2m − 1}.

In Keedwell(1978), the set of edge-disjoint circuits into which a P-quasigroup of order 2m − 1 separates the edges of the complete graph K _2m−1 were said to form a P-circuit design and the separate circuits were called linked blocks of that design. The P-circuit design was called uniform if all its blocks were of the same size and none contained repeated vertices (elements).

Concepts of perpendicularity, skew-perpendicularity, and of being cyclic were introduced and it was shown that P-quasigroups with these special properties could be used to construct Room squares with the corresponding properties.

Steiner triple systems provide particular examples of uniform P-circuit designs and so the above results generalize Theorem 6.4.4.

In his paper of 1970, Kotzig raised the further question: “For what orders n does a P-quasigroup exist which defines a partition of G into an Eulerian circuit?”

Subsequently, the present author proved in Keedwell(1975) that P-quasigroups of the above kind exist whenever n is an integer of the form 4r + 3 such that r ≢ 2 mod 5 and r ≢ 1 mod 6. They also exist when n = 4r + 3 and 0 ≤ r ≤ 7. In a subsequent paper with Hilton, the two authors together proved that such P-quasigroups exist for all n = 4r + 3 except possibly when r ≡ 127 mod 595 and they also showed existence for many values of n = 4r + 1. [See Hilton and Keedwell(1976).] The problem was solved completely by Korovima(1984) who showed existence for all odd n ≠ 5.

Some further connections between special kinds of latin square, P-quasigroups and graph decompositions are mentioned in Keedwell(1976a,1976b,1982) and in [DK1], pages 308-311.

As already mentioned earlier in this chapter, Bruck(1963a) used the concepts of both k-nets and graphs to obtain conditions under which a given set of MOLS may be extended to a larger set. His main result was as follows:

Let S be a set of k − 2 MOLS of order n and let d = (n − 1) − (k − 2), which is the deficiency from being a complete set. Then, (1) whenever n > (d − 1)², if S can be completed to a complete set of MOLS at all, it can be so completed in only one way; (2) a sufficient (but not necessary) condition that such a set S can be augmented to a complete set of MOLS in at least one way is that n > 1 2 ( d − 1 ) 4 + ( d − 1 ) 3 + ( d − 1 ) 2 + 3 2 ( d − 1 ) .

However, more recently this result has been improved and superceded by one due to Metsch(1991):

Let S be a set of k − 2 MOLS of order n. and let d = n − k + 1, be the deficiency from being a complete set as before. Then, S can be extended to a complete set if n > 8 3 d 3 − 6 d 2 + 8 3 d + 4 3 .

In Jungnickel(1996), that author gave a survey of results on this topic so we refer the reader to that paper for further information. However, a paper by Bose(1963) introducing the concept of a partial geometry (or partial geometric net) and relating it to strongly regular graphs deserves special mention because it generalizes some of the results of Bruck mentioned above.

We end this section by mentioning a connection between latin squares and graphs which is somewhat indirect. In a series of papers, Choudhuri(1948,1949,1957), that author has devised a means of defining an ordering relation on any quasigroup Q and with the aid of this definition has associated a directed graph Γ with Q. The properties of Γ serve to illuminate those of Q.

---

¹ The concept of isotopy between quasigroups was introduced in Section 1.3.

² If c is kept fixed as here, then w is as before and so the loop (G, ⊕) is unaltered.

³ In Argunov’s notation, which makes some attempt to be systematic, the leading lower case letter m or a stands for “multiplication” or “addition”, the capital letter A stands for “associativity” and the three numbers following, say (R; P, L) are respectively the rank, the number of points, and the number of lines of the configuration. The rank R is defined by the formula R = 2(P + L) − I, where I is the number of incidences in the unclosed configuration.

⁴ The configuration of Desargues is of crucial importance in the theory of affine and projective planes but not so much so in the theory of 3-nets.

⁵ For a detailed and comprehensive account of the subject of the inter-relations between geometrical configurations and quasigroup identities treated from the geometrical point of view, the reader is referred to Argunov’s paper(1950) and to Pickert’s book(1955) on projective planes. Among other sources of information are Aczél’s paper(1964) [or (1965)], Belousov(1971) and chapter 8 of Belousov(1967b).

⁶ The questions are not the same because different choices of l _∞ in a particular plane may yield inequivalent sets of latin squares. See later in this section.

⁷ A Galois plane is called a desarguesian plane because in such a plane the well-known configurational theorem of Desargues concerning perspective triangles is universally valid. (It is conjectured that every plane of prime order is desarguesian.)

⁸ In fact, the Hughes plane of order 9 was first constructed by Veblen and Wedderburn(1907).

⁹ The first minor theorem of Desargues is the special case of Desargues’ theorem in which the vertex of perspectivity of the two triangles lies on the axis of perspectivity. It is said to be satisfied affinely when this axis is the special line l _∞.

¹⁰ Theorem 6.3 on page 368 of [DK2] is a strengthened form of this theorem due to Owens(1992).

¹¹ Two complete sets of latin squares are said to be equivalent if one set can be obtained from the other by a combination of the following operations: (i) simultaneously permuting the rows of all the squares; (ii) simultaneously permuting the columns of all the squares; and (iii) (for each independently) permuting the symbols of any of the squares.

¹² Cayley(1878b) was the first to propose a way of representing a group both graphically and as a latin square.

¹³ a ★ y ₁ = c and a ★ y ₂ = c ⇒ a · c = y_i for i = 1, 2.