Orthogonal Latin squares based on groups (Q721708)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Orthogonal Latin squares based on groups
scientific article

    Statements

    Orthogonal Latin squares based on groups (English)
    0 references
    0 references
    19 July 2018
    0 references
    As the title suggests, this book indicates how groups can be used to generate interesting results about orthogonal Latin squares. The book can be viewed as an update and expansion of [\textit{A. B. Evans}, Orthomorphism graphs of groups. Berlin: Springer-Verlag (1992; Zbl 0796.05001)]. It is well written, accessible, and largely self-contained. A Latin square of order \(n\) is an \(n\times n\) array with \(n\) symbols such that no symbol is repeated in any row or column. Two Latin squares of order \(n\) are orthogonal if, when superimposed to form an \(n\times n\) array of ordered pairs of symbols, no ordered pair is repeated. The study of orthogonal Latin squares began with Euler's 1770's ``rank and regiment'' problem, from which he conjectured that no Latin square of order \(n=4k+2\) possesses an orthogonal Latin mate. Latin squares and orthogonality, which originally were recreational curiosities, are intimately connected to incidence structures such as projective planes and transversal designs. They are now a staple in statistical and combinatorial design theory. It is important to emphasize that meaningful results concerning orthogonal Latin squares are hard, and that fundamental, longstanding open problems remain. We illustrate this by considering two questions: First, when does a Latin square possess an orthogonal mate? Remember Euler's conjecture: It is true for \(n=2\) and \(n=6\), the latter proved by \textit{G. Tarry} [Ass. Franç. Paris (1900) 29, 170--203 (1900; JFM 32.0219.04)], having eluded Euler. However, the conjecture fails for every other singly even value of \(n\); this was not established until 1960 with the groundbreaking work of \textit{R. C. Bose} et al. [Can. J. Math. 12, 189--203 (1960; Zbl 0093.31905)]. Second, what is the maximum size of a collection of mutually orthogonal Latin squares (MOLS) of order \(n\)? It is not difficult to show that there are at most \(n-1\) MOLS of order \(n\), and it has long been known that this upper bound is achievable when \(n\) is a prime power. However, aside from \(n=6\) and \(n\) a prime power, the maximum size of a set of MOLS is unknown. Work along these lines has focused mainly on producing large lower bounds on the size of a family of MOLS. A relatively recent list of these bounds is given in [\textit{C. J. Colbourn} (ed.) and \textit{J. H. Dinitz} (ed.), The CRC handbook of combinatorial designs. 2nd ed. Boca Raton, FL: Chapman \& Hall/CRC (2007; Zbl 1101.05001)]. A semblance of order can be brought to the chaos of hard problems by imposing structure. In the present setting, the author imposes an algebraic structure. For a finite group \(G\) consider a Latin square \(L_G\) formed by permuting the rows/columns of a Cayley table for \(G\) (relabeling is also permitted). We say that \(L_G\) is based on \(G\). For Latin squares based on groups, the two questions framed above can be recast in terms of groups: The square \(L_G\) has an orthogonal mate if and only if the Cayley table for \(G\) possesses a transversal, and this occurs if and only if there is a bijection \(\theta :G\rightarrow G\) such that \(g\mapsto g\theta (g)\) is also a bijection \(G\rightarrow G\). The mapping \(\theta\) is called a complete mapping. Therefore, the first question above translates to ``Which groups possess complete mappings?'' Meanwhile, a bijection \(\phi :G\rightarrow G\) is an orthomorphism if \(g\mapsto g^{-1}\phi (g)\) is a bijection. Further, two orthomorphisms \(\phi, \psi\) are orthogonal if \(g\mapsto \phi^{-1}(g)\psi (g)\) is a bijection. It turns out that there exist a set of \(r\) pairwise orthogonal orthomorphisms of \(G\) if and only if there exist \(r+1\) MOLS, all based on \(G\), obtained by permuting the columns of the Cayley table for \(G\). So, in this setting, the second question above translates to ``What is the maximum size of a collection of mutually orthogonal orthomorphisms?'' Many of the known best lower bounds on the number of MOLS, including the classical result for prime power orders, are obtained using Latin squares based on groups. This book consists of four parts. After a first part devoted to background material on Latin squares, orthogonality, and groups, the second part addresses the existence of complete mappings. The Hall-Paige conjecture is a key feature of this part of the manuscript. In the 1950's Hall and Paige proved that if the Sylow 2-subgroup of a finite group \(G\) is nontrivial and cyclic, then \(G\) does not possess any complete mappings. Interestingly, this result shows that Euler's conjecture holds for Latin squares based on groups. Hall and Paige conjectured the converse. The author presents a proof of the Hall-Paige conjecture, in which possible minimal counterexamples are systematically eliminated (through the separate and rather recent work of Wilcox, Evans, and Bray, the latter unpublished). The author also presents several classes of groups that do admit complete mappings, e.g., solvable groups, Mathieu groups, Suzuki groups, and some linear groups, such as \(\text{SL}(2,q)\). Orthomorphism graphs are discussed in part three of the book. The vertices of an orthomorphism graph for \(G\) are the normalized orthomorphisms of \(G\) and an edge indicates orthogonality of two orthomorphisms. The clique number of an orthomorphism graph corresponds to the size of a large set of MOLS, in fact, a maximal set of MOLS based on groups where each is obtained by permuting the columns of the Cayley table for \(G\). Currently many of the best known lower bounds on the size of MOLS arise in this way. In this section the structure of orthomorphism graphs and corresponding clique numbers are considered for abelian groups and some non-abelian groups, such as the dihedral groups, \(\text{GL}(2,q)\), and \(\text{SL}(2,q)\) (\(q\) even). The final portion of the book is dedicated to additional topics, and an extensive list of questions.
    0 references
    Latin square
    0 references
    group
    0 references
    MOLS
    0 references
    orthomorphism
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references