Computing autotopism groups of partial latin rectangles

Computing Autotopism Groups of Partial Latin Rectangles REBECCA J. STONES, Nankai University and Beijing Jiaotong University, China RAÚL M. FALCÓN, Universidad de Sevilla, Spain DANIEL KOTLAR, Tel-Hai College, Israel TRENT G. MARBACH, Ryerson University, China Computing the autotopism group of a partial Latin rectangle (PLR) can be performed in multiple ways. This study has two aims: comparing some of these methods experimentally to identify those that are competitive; and identifying design goals for developing practical software. We compare six families of algorithms (two backtracking and four graph-theoretic methods), with and without using entry invariants (EIs), in a range of settings. Two EIs are considered: frequencies of row, column, and symbol representatives; and 2 ×2 submatrices. The best approach to computing autotopism groups varies. When PLRs have many autotopisms (such as having very few entries or being a group table), the McKay, Meynert, and Myrvold (MMM) method computes generators for the autotopism group efficiently. (The MMM method is the standard way to compute autotopisms.) Otherwise, PLRs ordinarily have trivial or small autotopism groups, and the task is to verify this. The so-called PLR graph method is slightly more efficient in this setting than the MMM method (in some circumstances, around twice as fast). With an intermediate number of entries, the quick-to-compute strong EIs are effective at reducing the need for computation without introducing significant overhead. With a full or almost-full PLR, a more sophisticated EI is needed to reduce down-the-line computation. These results suggest a hybrid approach to computing autotopism groups: The software decides on suitable EIs based on the input; and the user chooses between the MMM or the PLR graph methods, depending on their dataset. This article expands the authors’ previous article Computing autotopism groups of PLRs: a pilot study. CCS Concepts: • Mathematics of computing →Combinatorial algorithms;Graph coloring;Graph algorithms; Additional Key Words and Phrases: Autotopism, Latin square, partial Latin rectangle Marbach and Stones’s work is partially supported by NSF of China (61602266, 61872201), the Science and Technology Development Plan of Tianjin (17JCYBJC15300, 16JCYBJC41900), and the Fundamental Research Funds for the Central Universities and SAFEA: Overseas Young Talents in Cultural and Educational Sector. Stones was supported by her NSFC Research Fellowship for International Young Scientists (grant numbers: 11450110409, 11550110491), and the Thousand Youth Talents Plan in Tianjin. Falcón’s work is partially supported by the research project FQM-016 from Junta de Andalucía and the Departmental Research Budget of the Department of Applied Mathematics I of the University of Seville. Authors’ addresses: R. J. Stones, College of Computer Science, Nankai University, Tianjin, P. R. China and Department of Mathematics, Beijing Jiaotong University, Beijing, 100044 P. R. China; email: [email protected]; R. M. Falcón, School of Building Engineering, Department of Applied Mathematics I, Universidad de Sevilla, 41012 - Seville, Spain; email: [email protected]; D. Kotlar, Computer Science Department, TelHai College, Upper Galilee, 1220800 Israel; email: [email protected]; T. G. Marbach, Department of Mathematics, Ryerson University, 350 Victoria St., Toronto, ON, Canada; email: [email protected]. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. https://doi.org/10.1145/3412324 1.12:2 R. J. Stones et al. ACM Reference format: Rebecca J. Stones, Raúl M. Falcón, Daniel Kotlar, and Trent G. Marbach. 2020. Computing Autotopism Groups of Partial Latin Rectangles. J. Exp. Algorithmics 25, 1, Article 1.12 (September 2020), 39 pages. https://doi.org/10.1145/3412324 1 INTRODUCTION Let [n]:= {1, 2,...,n}.Anr × s partial Latin rectangle is an r × s matrix containing symbols from [n] ∪{·} such that each row and each column contains at most one copy of any symbol in [n]. This is a partial Latin square if r = s = n.LetPLR(r, s, n) denote the set of such matrices. Every L ∈ PLR(r, s, n) is uniquely determined by its entry set Ent(L) := {(i, j, L[i, j]) : i ∈ [r], j ∈ [s], L[i, j] ∈ [n]}. We call any triple (i, j, L[i, j]) ∈ Ent(L) an entry of L, while any pair (i, j) ∈ [r] × [s] is called a cell. We call a cell (i, j) empty if L[i, j] = ·, in which case, we consider L[i, j] as being undefined.IfL ∈ PLR(r, s, n) does not have empty cells, then L is a Latin rectangle. The standard definition of a Latin rectangle [84] requires s = n, so we are considering a generalization of this. Any L ∈ PLR(n, n, n) with no empty cells is a Latin square of order n. This constitutes in turn the Cayley table of a quasigroup of the same order; that is, an algebraic structure endowed of left- and right-division. Particularly, every associative quasigroup is indeed a group. For a positive integer m,letSm denote the symmetric group on [m]. Any triple θ := (α, β,γ ) ∈ Sr × Ss × Sn acts on PLR(r, s, n), with θ acting on L ∈ PLR(r, s, n) by permuting its rows, columns, and symbols by α, β,and γ , respectively. The triple θ is called an isotopism (an isomorphism if α = β = γ ). Moreover, it is said that Lθ ∈ PLR(r, s, n) is isotopic to L (see Reference [36] for a recent survey on the theory of isotopisms). If L = L[i, j], then Ent(Lθ ) = {(α (i), β (j),γ (L[i, j])) : (i, j, L[i, j]) ∈ Ent(L)} and we write (i, j, L[i, j])θ = (α (i), β (j),γ (L[i, j])). Isotopism induces an equivalence relation among partial Latin rectangles. In particular, even though the number and distribution of Latin squares into isotopism classes are known [49, 59, 68] for order up to 11, the number of partial Latin rectangles is only known for orders r, s, n ≤ 7, and their distribution into isotopism classes is only known for orders r, s, n ≤ 6 (see References [31, 32, 35, 39, 41]). If L = Lθ ,thenθ is said to be an autotopism of L.ThesetAtop(L) of autotopisms of L forms a group, called the autotopism group of L. From the Orbit-Stabilizer Theorem, the computation of this group is crucial for determining the set of partial Latin rectangles that are isotopic to L, and hence, the distribution of partial Latin rectangles into isotopism classes [41]. The exponential growth of both the number of partial Latin rectangles and the number of their possible autotopism groups is a handicap to deal with those orders from six to eleven, even though the distribution of Latin squares into isotopism classes is known for these orders. In this regard, this article is a preliminary study for setting the technical standards for further development of software capable of computing autotopism groups of partial Latin rectangles efficiently, which would enable work on the problems of counting, enumerating, and classifying partial Latin rectangles of orders r, s, n > 6. More specifically, in this article, we implement and experimentally compare six families of algorithms for computing autotopism groups of partial Latin rectangles, with and without the use of invariants. Some of these algorithms have been used in prior research on partial Latin rectangles, while others are new. A brief sketch of this study has recently been exposed by the authors [88]. Here, we delve into the development of efficient algorithms for the computational Computing Autotopism Groups of Partial Latin Rectangles 1.12:3 processes described in that previous work, along with a study of the reasons that give rise to better or worse experimental results. We note that it is unrealistic to expect a succinct solution to the problems of counting, enumerating, and classifying partial Latin rectangles for arbitrary orders (and hence, to the problem of computing their autotopism groups), since they include the analogous problems for Latin squares, which constitute long-standing research problems in Combinatorics. Though widely studied in the literature, these problems on Latin squares have been completely solved only for orders up to 11. This fact shapes the underlying difficulty of dealing with much higher orders and motivates our experiments to be focused on smaller instances, of orders r,s,n≤20. 1.1 Literature Review Autotopisms of (partial) Latin squares have arisen in a range of topics and are also studied in their own right [3,10,15,16,22,26,30,37,38,50,56,57,60,72–74,86,96]. Thus, they are beginning to find applications in cryptography [28,89,99], for graph coloring games [2,34], erasure codes [87, 101], and Blackburn partial Latin squares [87,94] (which relate to perfect hash families [11], parentidentifying codes [1], coded caching schemes [100], and 2-increasing sequences [44]). However, autotopisms of (partial) Latin rectangles have only been studied in a few recent papers [31,39–41]. The standard way of computing autotopism groups of Latin squares was given by McKay, Meynert, and Myrvold [68], who described a vertex-colored graph whose automorphism group is isomorphic to the autotopism group of the corresponding Latin square. As such, they suggested the use of the software nauty [69], which is one of the most widely used computational tools to deal with the graph isomorphism problem [78] using vertex invariants; that is, properties of vertices of graphs that are preserved under isomorphisms (as, for instance, the number of edges incident with a given vertex). These invariants make the computation of automorphism groups of graphs faster, because they partition the vertices of a graph so none of its automorphisms permute vertices from one part to another. Vertices of a graph may therefore be uniquely colored according to any given vertex invariant without changing its automorphism group. The motivation of McKay, Meynert, and Myrvold for using colored graph isomorphisms was based on the observed expressivity of colored graphs in representing combinatorial families (such as partial Latin rectangles) for symmetry computations. Notice in this regard that the use of colored graphs representing certain symmetrical properties of (partial) Latin rectangles had already been dealt in the literature in the late 1970s [19,20,43,47,48,98]. Furthermore, it had already been established by Miller [75] that the problem of determining whether two Latin squares are isotopic when both are Cayley tables is polynomial time many-one reducible to the graph isomorphism problem. Moreover, Miller himself [76] generalized Tarjan’s algorithm for deciding in O(nlog2n+O(1))steps whether two Latin squares of order nare isomorphic. The more general problem of efficiently computing symmetric groups of combinatorial objects has been observed in the literature for at least 40 years [17,64,65]. Since these early papers, the particular use of combinatorial invariants to speed up such a computation is standard practice [53, 54]. Let us mention in this regard, for instance, the use of combinatorial invariants for computing automorphism groups of Hadamard matrices [62,92], error-correcting codes [63,80], and graphs, from which we emphasize McKay’s seminal and highly influential works [66,69]. To reduce the runtime of the expensive computation that would be required by nauty for determining the autotopism group of a Latin square using the mentioned vertex-colored graph, McKay, Meynert, and Myrvold [68] also suggested the use of isotopism invariants based on rows, columns, and symbols of the corresponding Latin squares. As an illustrative example, they proposed to identify each row of the Latin square under consideration with its number of 2 ×2 Latin subsquares (known as intercalates) involving such a row. Previously, Wanless [95] had already indicated the use of the 1.12:4 R. J. Stones et al. so-called trains as isotopism invariants that accelerate the computation in nauty of autotopisms and conjugate symmetries of atomic Latin squares. Furthermore, the use of new isotopism invariants for computing autotopism groups of Latin squares would not only complement the combinatorial invariants that are already implemented in nauty, but would also enable the improvement of the design, analysis, and development of different strategies that are carried out by the software for dealing with data structure and algorithm engineering. Recall that using some variants of the Weisfeiler-Lehman individualization-refinement procedure [97], the processing of vertex invariants in nauty makes use of backtracking, hashing, search trees, pruning techniques based on orbit stabilizer algorithms, target cell selections, and canonical labeling [66, 67, 69]. A generalization of the method by McKay, Meynert, and Myrvold to deal with symmetries of partial Latin squares was introduced by Stones [85], who also used three basic invariants (the number of entries in a row or column, and the total number of copies of a symbol) to reduce the search space. Regarded as vector invariants, they were, respectively, established as row, column, and symbol invariants. These vector invariants are closely related to the notion of type introduced by Keedwell [55]. Since asymmetry can exist even in the case that all these vector invariants are unique, Stones also established a method for verifying asymmetry of partial Latin squares of order n in O (nconstant) steps. Stones implemented a backtracking algorithm that proceeded row-by-row then column-by-column for determining asymmetric partial Latin squares. The corresponding generalization of the method by McKay, Meynert, and Myrvold for r × s partial Latin rectangles on n symbols was dealt with by Falcón and Stones [40]. More recently, the present authors [23] have studied some invariant refinement procedures to deal with the computation of the autotopism group of partial Latin rectangles. They are related to some ideas proposed by Kotlar [60, 61] concerning the computation of autotopisms of Latin squares by enumerating cycles belonging to rows. As such, it can be thought of as an example of what we will call in this article row invariants. The efficient use of these invariants in Reference [23] has required the implementation of a tree-based algorithm, and the particular use of red-black trees for dealing with the corresponding data structure. Furthermore, in the literature, one can also find some invariants that are used for computing autotopisms of partial Latin rectangles satisfying certain conditions. This is the case, for instance, of the recent use of Hilbert polynomials in Reference [33] as invariants for strong isotopisms (that is, isotopisms of the form (α, α,γ ) ∈ Sn × Sn × Sn ) of empty-diagonal symmetric partial Latin squares for which each one of its rows and columns has at least two non-empty cells. It is known [15] that a Latin square of order n has at most nO (log n) autotopisms, and hence, the computation of autotopism groups of Latin squares takes worst-case super-polynomial time. Nevertheless, almost all Latin squares have trivial autotopism groups [18, 71]. So, in almost all cases, computing the set of autotopisms for a Latin square L amounts to eliminating the possibility of a non-trivial autotopism (which is pertinent for applications involving canonically labeling Latin squares [42]). It seems reasonable to suspect that a related “almost all” claim holds for (partial) Latin rectangles under most conditions. However, it is not straightforward to generalize these proofs to (partial) Latin rectangles. Some obstacles are: (a) two empty columns in a partial Latin rectangle can be swapped, giving rise to a large family of partial Latin rectangles with a non-trivial (albeit uninteresting) autotopism; (b) 2 × n Latin rectangles always have non-trivial symmetries; and (c) partial Latin rectangles with very few entries must have non-trivial symmetries [85]. In this article, partial Latin rectangle graphs are used for computing autotopism groups of partial Latin rectangles. These graphs were introduced as a generalization of Latin square graphs [13]by Falcón and Stones [40], who showed their usefulness for proving symmetry properties of partial Latin rectangles. A recent study [24] considers realizing graphs as partial Latin rectangle graphs, and even their generalization to partial Latin hypercuboid graphs. As such, it is possible to solve Computing Autotopism Groups of Partial Latin Rectangles 1.12:5 the graph isomorphism (GI) problem for graphsGand Hthrough the construction of a partial Latin square whose autotopism group is isomorphic to the automorphism group of the graph G∪H.As a consequence, the computation of the autotopism group of a partial Latin square requires at least polynomially equivalent time to solving the GI problem, whose complexity is known [6,8,9]to be at most exp((logn)O(1)),wherenis the number of vertices. Notice that the development of new algorithms to deal with the GI problem is currently a very active area of research [5,7,45,46,58, 77,79]. In Section 2, we see in particular that the problem of computing the set of generators of the autotopism group of a partial Latin rectangle is graph-isomorphism complete (GI-complete). That is, it is polynomial-time equivalent to the GI problem. 1.2 Test Sets Throughout the article, we compare the runtimes of the algorithms experimentally on two randomly generated sets of partial Latin rectangles, described below. In both test sets, partial Latin rectangles are generated non-uniformly at random. It should be noted that the problem of uniformly generating random partial Latin rectangles with a specified number of entries is likely a non-trivial researchproblem, since it contains the sub-problemof generating random Latin squares [25,51]. 1.2.1 PLR Set A: Adding Random Entries. To generate a member of PLR set A, we begin with an empty PLR(r,s,n)and attempt xtimes to add an entry chosen uniformly at random from [r]× [s]×[n]. Three types of clashes might arise: (a) the cell is already full, (b) adding the entry would introduce a repeated symbol in a row, or (c) adding the entry would introduce a repeated symbol in a column. If a clash arises, we do nothing. The reason to fix the number of attempts in this PLR set A and not the number of filled cells is because fixing this last number may lead to a dead-end if no entry can be added. We are motivated to use this test set, since Stones [85] used a related randomized set. In the latter, generating a PLR restarted from scratch whenever a clash arose, so a uniform distribution on m-entry partial Latin squares was achieved. The generation method presented here does not generate PLR(r,s,n)’s uniformly at random, even if we restrict the number of entries. In the case r=s=n=2andx=5, the probabilities of generating each possible PLR(2,2,2)are tabulated in Table 1, where we see that these probabilities distinguish PLR(2,2,2)’s up to paratopism [35]. A random partial Latin rectangle generated in this way could have anywhere between 1 and min(x,rs)entries (provided x≥1), with the expected number of entries growing as the number of attempts xincreases. However, two random partial Latin rectangles generated by this process might not have the same number of entries, so we also consider the following PLR set. 1.2.2 PLR Set B: Deleting Random Entries. Assume n≥max{r,s}. Here, we generate a random Latin square of order n, truncate it, and then delete entries to obtain a random PLR(r,s,n)with exactly xentries. More specifically: (1) We use the Markov chain Monte Carlo algorithm described by Jacobson and Matthews [51] using random perturbations to generate random Latin squares of order nthat are approximately uniformly distributed. (2) We then delete the last n−rrows and the last n−scolumns, which gives a PLR(r,s,n) with rs entries. (3) We then delete rs −xrandom entries, which gives a PLR(r,s,n)with xentries. Figure 1illustrates this process. Importantly, the number of entries is the independent variable, whereas for PLR set A, the number of attempts at adding an entry is the independent variable. 1.12:6 R. J. Stones et al. Table 1. The Probability of Generating Each Partial Latin Square in PLR(2,2,2)after x=5Attempts at Adding Random Entries, Separated Into Groupings that Have Identical Probability; Probabilities were Calculated Using Exhaustive Computation (Classifying all 85Possible Sequences of Attempts). Fig. 1. Illustrating the process of generating a random PLR(r,s,n)with xentries. This process does not generate x-entry PLR(r,s,n)’s uniformly at random for two main reasons: (a) different x-entry PLR(r,s,n)’s complete to rs-entry PLR(r,s,n)’s in a different number of ways, and (b) different rs-entry PLR(r,s,n)’s may embed in a different number of Latin squares of order n. In fact, not every x-entry PLR(r,s,n)can be generated. For example, for r=s=n=2=x,the following PLR(2,2,2)cannot be generated, as it does not embed in a Latin square of order 2: The Jacobson and Matthews method gives an asymptotically uniform distribution of random Latin squares [4]. It is indeed the gold standard for generating random Latin squares, although DeSalvo [25] has recently claimed to improve upon this. In any case, the method of randomly generating Latin squares does not play a substantial role in our experimental results. Computing Autotopism Groups of Partial Latin Rectangles 1.12:7 2 AUTOTOPISMS OF PARTIAL LATIN RECTANGLES 2.1 Introduction Let us start with a characterization of the existence of an autotopism of a partial Latin rectangle with an unspecified symbol permutation, given specified row and column permutations, αand β, respectively. Lemma 2.1. Let L∈PLR(r,s,n).Ifα∈Srand β∈Ss, then there exists γ∈Snfor which θ= (α,β,γ)∈Atop(L)if and only if (1) L[α(i),β(j)]is defined for all (i,j,L[i,j])∈Ent(L),and (2) L[α(i),β(j)]=L[α(i),β(j)]whenever L[i,j]=L[i,j]∈[n]. The permutations γfor which θ∈Atop(L)are those satisfying γ(L[i,j])=L[α(i),β(j)], for all (i,j,L[i,j])∈Ent(L). Proof. Let θ=(α,β,γ)∈Atop(L). Then, Condition 1 holds by definition. If Condition 2 were false, then some two entries (α(i),β(j),L[α(i),β(j)])=(i,j,L[i,j])θ and (α(i),β(j),L[α(i),β(j)])=(i,j,L[i,j])θ disagree at the third coordinate, contradicting the assumption that L[i,j]=L[i,j]. Now, assume Conditions 1 and 2 hold for some α∈Srand β∈Ss. We choose any mapγ:[n]→ [n] such that γ(L[i,j])=L[α(i),β(j)] for all entries (i,j,L[i,j])∈Ent(L), and such that γis a permutation of the symbols in [n] that do not occur in L. Conditions 1 and 2 ensureγis indeed a map. Condition 2 further implies γis injective, and thus γis a permutation of [n]. Since γis defined such that Ent(L(α,β,γ))=Ent(L), we have an autotopism θ∈Atop(L). Lemma 2.1 also suggests a backtracking algorithm for simultaneously determining whether or not αand βparticipate in an autotopism of Las respective row and column permutations, and identifying which third coordinates γare possible. This procedure is described in Algorithm 1. Specifically, the symbols k∈[n] for which γ(k)is left undefined in Algorithm 1are those that do not appear in L∈PLR(r,s,n). These symbols can be arbitrarily permuted among themselves and hence (α,β,γ)is an autotopism of L. This is established formally (and more generally) in Lemma 2.2 below. Lemma 2.2. Let Lbe a partial Latin rectangle in the set PLR(r,s,n)with exactly r≤rnon-empty rows, s≤snon-empty columns, and n≤nused symbols. Then, Atop(L)Sr−r×Ss−s×Sn−n×Atop(L∗), where L∗∈PLR(r,s,n)is the partial Latin rectangle that results from eliminating the empty rows and columns of Land relabeling the symbols used in Lby using those in [n]. Consequently, |Atop(L)|=(r−r)!(s−s)!(n−n)!|Atop(L∗)|. Algorithm 1identifies every autotopism with first and second components αand β, respectively. An output autotopism from our implementation might look like [?4??6?1]; [???5?63]; [???453?] where ?denotes an unused row, column, or symbol where α,β,orγis left undefined, respectively (and we index from 0 using C++). This states thatαcan be any permutation that maps 1 → 4, 4 → 6, and 6 → 1, and likewise for βand γ. Lemma 2.2 implies that all such isotopisms are autotopisms. 1.12:8 R. J. Stones et al. ALGORITHM 1: ExtendAlphaBeta(α,β) Require: L∈PLR(r,s,n), and permutations α∈Srand β∈Ss Ensure: an autotopism (α,β,γ)∈Atop(L),orfail if no such autotopism exists 1: Set γ[k]←undefined and γ−1[k]←undefined for all k∈[n] 2: for all entries (i,j,k)∈Ent(L)do 3: if L[α(i),β(j)]=undefined then 4: return fail {clash:entry(i,j,k)maps to an empty cell} 5: end if 6: Set k←L[α(i),β(j)]{γmaps kto k} 7: if γ[k]=undefined then 8: Set γ[k]←kand γ−1[k]←k 9: else 10: if γ[k]kthen 11: return fail {clash:γalso maps kto something else} 12: end if 13: if γ−1[k]kthen 14: return fail {clash:γalso maps something else to k} 15: end if 16: end if 17: end for 18: return (α,β,γ) 2.2 Entry Invariants An entry invariant Pis any property of the entries of partial Latin rectangles that is preserved under autotopisms. That is, if Lis a partial Latin rectangle, then P(e)=P(eθ), for all e∈Ent(L) and θ∈Atop(L). Lemma 2.3. Let L∈PLR(r,s,n). The following properties are entry invariants of L.Foreach (i,j,L[i,j])∈Ent(L): (1) The number of entries in row i. (2) The number of entries in column j. (3) The number of times the symbol L[i,j]appears in L. (4) The number of distinct symbols in the union of row iand column j. Example 2.4. We illustrate the third assertion in Lemma 2.3 with a simple example. On the right-hand side above, we present the entry invariant matrix, which is obtained by relabeling each entry in the partial Latin rectangle L under study by a positive integer so (a) the first occurrences of these integers appear in natural order row-after-row; and (b) if the invariants associated to two entries coincide, then they are relabeled by the same positive integer. From Lemma 2.3, if two non-empty cells (i, j) and (i, j) within this matrix contain distinct positive integers, then no autotopism of L maps the entry (i, j, L[i, j]) to the entry (i, j, L[i, j]).Here, this procedure partitions the entry set of L in two parts, {(1, 1, 1), (2, 2, 1)} and {(1, 2, 2), (2, 3, 3)}. Hence, each part is fixed set-wise under the action of any autotopism of L. Computing Autotopism Groups of Partial Latin Rectangles 1.12:9 Let us see in the following result how the entry invariants described in Lemma 2.3 enable us to ensure that computing the autotopism group of a given partial Latin rectangle is as hard as deciding whether two given arbitrary graphs are isomorphic. Proposition 2.5. The problem of computing the set of generators of the autotopism group of a partial Latin rectangle is GI-complete. Proof. We have from Reference [88] (see also Section 3.2.2 in this article) that every partial Latin rectangle Lis uniquely related to a bipartite graph so the autotopism group of the former is isomorphic to a subgroup of the automorphism group of the latter. Thus, to prove the result, let us see that every bipartite graph G=(V(G),E(G)) may be embedded into a partial Latin rectangle L(G)so the set of generators of the automorphism group Aut(G)of the graph Gmay be obtained from the set of generators of the autotopism group Atop(L(G)). Then, the result would follow from the known fact that computing a set of generators for the automorphism group of a given bipartite graph is GI-complete [12]. Let ebe the number of edges of the bipartite graph Gand let us suppose that the set of vertices V(G)is bipartitioned into a set of rred vertices R(G)={v1,...,vr}and a set of ccyan vertices C(G)={w1,...,wc},soeveryedgeinE(G)is incident to both a red and a cyan vertex. Without loss of generality, we can also suppose that r≤c≤e,e>1 and that no isolated vertices exist in G.Then,letusdefinean(r+2e)×(c+2e)partial Latin rectangle L(G)containing symbols from the set [(r+c−1)e]∪{·}by following the next four stages, where, from now on, d(v)and N(v) denote, respectively, the degree and the neighborhood of a vertex v∈V(G). (a) Each red vertex vi∈R(G)is uniquely associated with Row icontaining the set of entries ⎧ ⎪ ⎨ ⎪ ⎩ i, i−1  m=1 d(vm)+k, i−1  m=1 d(vm)+k :1≤k≤d(vi)⎫ ⎪ ⎬ ⎪ ⎭ in Ent(L(G)). Each one of these entries is uniquely related to an edge incident with the vertex vi. Moreover, the symbol assigned to the former may be considered as a label of the latter. Hence, once this stage finishes, one can define a labeling Lab : E(G)→[e] viwj→Lab(viwj). (b) Each cyan vertex wjis uniquely associated with Column e+jcontaining the set of entries ⎧ ⎪ ⎨ ⎪ ⎩ r+ j−1  m=1 d(wm)+k,e+j,sk :1≤k≤d(wj),sk∈{Lab(vwj):v∈N(wj)}⎫ ⎪ ⎬ ⎪ ⎭ in Ent(L(G)),whereskskif kk. Then, similarly to the previous stage, each one of these entries is uniquely related to an edge incident with the vertex wj. (c) For each positive integer s∈{e+1,...,re}, we introduce a series of extra entries of the form (i,c+e+j,s)∈Ent(L(G)), for some arbitrary positive integers i≤rand j≤e,sotheith row of L(G)has exactly e entries, for all i≤r. (d) For each positive integers∈{re +1,...,(r+c−1)e)}, we introduce a series of extra entries of the form (r+e+i,e+j,s)∈Ent(L(G)), for some arbitrary positive integers i≤eand j≤c,sothe(e+j)th column of L(G)has exactly eentries, for all j≤c. 1.12:16 R. J. Stones et al. Fig. 4. The average runtime of the entrywise backtracking methods, with and without the use of SEIs and/or square invariants (sq.); parameters (r,s,n)=(5,5,5). ALGORITHM 4: EntrywiseBacktracking(t) Require: L∈PLR(r,s,n)with mentries Ensure: autotopism group Atop(L) 1: Set Atop(L)←∅ 2: Set α[i]←undefined and α−1[i]←undefined and αcount[i]←0foralli∈[r] 3: Set β[j]←undefined and β−1[j]←undefined and βcount[j]←0forallj∈[s] 4: Set γ[k]←undefined and γ−1[k]←undefined and γcount[k]←0forallk∈[n] 5: Set i←et[1] and j←et[2] and k←et[3] 6: for all u∈[m]do 7: Set a←eu[1] and b←eu[2] and c←eu[3] {we try mapping (i,j,k)to (a,b,c)} 8: if EntryChecks((i,j,k),(a,b,c)) returns fail then 9: continue {Algorithm 5} 10: end if 11: Set α[i]←aand α−1[a]←iand αcount[i]←αcount[i]+1 12: Set β[j]←band β−1[b]←jand βcount[j]←βcount[j]+1 13: Set γ[k]←cand γ−1[c]←kand γcount[k]←γcount[k]+1 14: if t=mthen 15: Add (α,β,γ)to Atop(L) 16: else 17: EntrywiseBacktracking(t+1) 18: end if 19: Set αcount[i]←αcount[i]−1andβcount[j]←βcount[j]−1andγcount[k]←γcount[k]−1 20: if αcount[i]=0then 21: α[i]←undefined and α−1[a]←undefined 22: end if 23: if βcount[j]=0then 24: β[j]←undefined and β−1[a]←undefined 25: end if 26: if γcount[k]=0then 27: γ[k]←undefined and γ−1[a]←undefined 28: end if 29: end for Computing Autotopism Groups of Partial Latin Rectangles 1.12:17 ALGORITHM 5: EntryChecks((i,j,k),(a,b,c)) 1: if entry invariant Pis being used and P((i,j,k)) P((a,b,c)) then 2: return fail {entries (i,j,k)and (a,b,c)have different entry invariants} 3: end if 4: if row invariant PRis being used and PR(i)PR(a)then 5: return fail {rows iand ahave different row invariants} 6: end if 7: if column invariant PCis being used and PC(j)PC(b)then 8: return fail {columns jand bhave different column invariants} 9: end if 10: if α[i]undefined and α[i]athen 11: return fail {clash:αalso maps ito something else} 12: end if 13: if α−1[a]undefined and α−1[a]ithen 14: return fail {clash:αalso maps something else to a} 15: end if 16: if β[j]undefined and β[j]bthen 17: return fail {clash:βalso maps jto something else} 18: end if 19: if β−1[b]undefined and β−1[b]jthen 20: return fail {clash:βalso maps something else to b} 21: end if 22: if γ[k]undefined and γ[k]cthen 23: return fail {clash:γalso maps kto something else} 24: end if 25: if γ−1[c]undefined and γ−1[c]kthen 26: return fail {clash:γalso maps something else to c} 27: end if As indicated in the introductory section, the autotopism group of a partial Latin rectangle Lmay be computed via graph automorphisms. This generally follows a three-step process: (1) Compute some graph Gfrom L. Such a graph has to be chosen so we have some mechanism for computing the autotopism group Atop(L)from the automorphism group Aut(G)(which is Step 3 below). The procedure for computing the autotopism group Atop(L)varies with such a choice. (2) Compute the automorphism group Aut(G). In this work, we perform this computation using nauty. For the purpose of this article, nauty functions like a “black box”: We input a graph and nauty outputs its automorphism group. (3) Compute the autotopism group Atop(L)from the automorphism group Aut(G). In addition to being able to list the automorphisms of the graph, nauty also outputs a function called orbits, which gives the finest possible vertex invariant partition (that is, for two vertices u and vin the same part, there is an automorphism that maps uto v). In the graphs we study, the vertex set is or contains the set of entries Ent(L)for some partial Latin rectangle L∈PLR(r,s,n). In these cases, entry invariants can be used to color these vertices. In general, this coloring does not correspond to a vertex invariant, as it might not be preserved under all automorphisms of the graph. However, the automorphisms that have been destroyed by coloring the vertices do not correspond to autotopisms of L. 1.12:18 R. J. Stones et al. Fig. 5. Converting a partial Latin rectangle Linto its related vertex-colored McKay, Meynert, and Myrvold graph GL. 3.2.1 Adapted McKay, Meynert, and Myrvold Method. We adapt the method by McKay, Meynert, and Myrvold (MMM) [68] to partial Latin rectangles. We define the vertex-colored graph GLby V(GL):=Ent(L)∪{Ri:i∈[r] and row iof Lis non-empty}, ∪{Sj:j∈[s]andcolumnjof Lis non-empty}, ∪{Nk:k∈[n]andsymbolkoccurs in L}, and assign each of the four vertex subsets Ent(L),{Ri},{Sj},and{Nk}a distinct vertex color. We also define the edge set E(GL):={eRi,eSj,eNL[i,j]:e:=(i,j,L[i,j])∈Ent(L)}. Figure 5gives an example of this construction. By restricting Aut(GL)to the vertices Ent(L),we determine Atop(L)(up to permutations of empty rows and columns, and unused symbols). It is easily verified that the implementation of the color refinement algorithm (which partitions the vertices of a graph according to their iterated degree sequence) to the graph GLto make faster the computation of their automorphism group is equivalent to the implementation of the exhaustive natural refinement (described in Section 2.2.1) of the partial Latin rectangle Lfor improving the computation of its autotopism group. More specifically, the degree of the vertices Ri,Sj,and Nkcoincide, respectively, with the number of entries in the ith row of L, the number of entries in the jth column of L,and the number of times the symbol kappears in L. 3.2.2 Bipartite Graph Method. For each L∈PLR(r,s,n),weconsiderthe(0,1)-matrix defined as M=M[i,j]r×swith M[i,j]=1 if and only if L[i,j] is defined. This matrix is called the shape [29,35]ofLand can be interpreted as the biadjacency matrix of a bipartite graph BM,whereone bipartition corresponds to the rows, and the other to the columns. An example is drawn in Figure 6. The pairs of permutations (α,β)∈Sr×Ssactonthesetofr×s(0,1)-matrices by permuting the rows by αand the columns by β;wedefineanautotopism of a (0,1)-matrix as a stabilizer under this group action. The group Atop(L)is isomorphic to a subgroup of the autotopism group of M. This gives rise to two ways of computing Atop(L): (1) Use nauty to compute the automorphism group of BM. This determines the autotopism group of M, from which we check each (α,β)in the autotopism group of Mto see if it defines an autotopism of Lthrough Lemma 2.1. (2) Use nauty to compute the orbits of BM, which partition [r] and [s]. The latter are, respectively, preserved by αand βin any autotopism (α,β,γ)of L.Wethenapplyoneof Computing Autotopism Groups of Partial Latin Rectangles 1.12:19 Fig. 6. Converting a partial Latin rectangle Linto its corresponding bipartite graph. Edge colors are not included in the graph, but are included in the figure to illustrate how the construction works. the backtracking methods of Section 3.1 with the added condition that these partitions are preserved. Notice in particular that the implementation of the color refinement algorithm in the graph BM derives from the use of the SEIs (in this case, without using the appearances of symbols). 3.2.3 Partial Latin Rectangle Graph Method. We define the edge-colored graph Γcolor Lwith vertex set V(Γcolor L):=Ent(L)and: •green edges between two distinct entries if they share a row, •orange edges between two distinct entries if they share a column, and •purple edges between two distinct entries if they share a symbol. It is known [40] that any automorphism of Γcolor Lis equivalent to an autotopism of L.Specifically, if the vertex (i,j,L[i,j])maps to (i,j,L[i,j])in Γcolor L, then the entry (i,j,L[i,j])maps to (i,j,L[i,j])in L. Thus, we can directly compute the autotopism group of Lby computing the automorphism group of Γcolor Lusing graph automorphism software—no further filtering is needed. However, nauty does not allow its input graphs to have edge colors. We consider two ways to overcome this. The first one is to simply ignore the edge colors, which we denote ΓL,then check each automorphism of ΓLreturned by nauty to see if it corresponds to an autotopism of L. The second method consists of defining a new non-edge-colored graph ΓLwhose automorphisms correspond to those of the edge-colored graph Γcolor L(see Figure 7). It has vertex set V(ΓL):=Ent(L)∪{Re:e∈Ent(L)}∪{Se:e∈Ent(L)}∪{Ne:e∈Ent(L)}, where each one of the four vertex subsets appearing as operands of the unions above is monochromatic, but any two of them have distinct vertex colors; and edge set E(ΓL):={eRe,eSe,eNe:e∈Ent(L)} ∪{Re1Re2: distinct entries e1and e2belong to the same row} ∪{Se1Se2: distinct entries e1and e2belong to the same column} ∪{Ne1Ne2: distinct entries e1and e2share the same symbol}. The graph ΓLhas more vertices than ΓL,sonauty takes longer to compute its automorphism group. However, the automorphism group of ΓL, when restricted to the vertices in the part Ent(L), gives the autotopism group of Ldirectly (i.e., no further filtering is required). It is also possible to use entry invariants to color the vertices in Ent(L)of ΓLor refining the vertex coloring of ΓL. 1.12:20 R. J. Stones et al. Fig. 7. Converting a partial Latin rectangle Linto its corresponding edge-colored partial Latin rectangle graph Γcolor L, and a vertex-colored non-edge-colored graph ΓLwith the same automorphism group as the edge-colored ΓLfor use in nauty. One more time, and similarly to the adapted MMM method, the implementation of the color refinement algorithm in both graphs ΓLand ΓLis uniquely related to the use of SEIs. The same happens in the following method. 3.2.4 Rook’s Graph Method. We define the edge-colored graph Ξcolor Lfrom the partial Latin rectangle graph Γcolor Lby deleting the purple edges; we also define ΞLfrom Ξcolor Lby ignoring the edge colors. Thus, ΞLforms an induced subgraph of the rook’s graph (that is, the Cartesian product of Krand Ks). Any autotopism of Lis equivalent to an automorphism of ΞL. The converse does not necessarily hold, so after nauty has been called, we check each automorphism of ΞLto see if it corresponds to an autotopism of L. Differing from partial Latin rectangle graphs, we define ΞL with V(ΞL):=Ent(L)∪{Re:e∈Ent(L)}∪{Se:e∈Ent(L)}∪{k∈[n]: symbolkappears in L}, where the unions above indicate distinct vertex colors, and edge set E(ΞL):={eRe,eSe:e∈Ent(L)} ∪{Re1Re2: distinct entries e1and e2belong to the same row} ∪{Se1Se2: distinct entries e1and e2belong to the same column} ∪{Rek:e∈Ent(L)and ehas symbol k} ∪{Sek:e∈Ent(L)and ehas symbol k}. Figure 8 illustrates this graph. It is also possible to use entry invariants to color the vertices in E(L) in both ΞL and ΞL. As with ΓL, the automorphism group of ΞL, when restricted to the vertices in thepartEnt(L), gives the autotopism group of L directly. 3.2.5 Additional Remarks. For an m-entry PLR(r, s, n) with no unused rows, columns, nor symbols, Table 2 tabulates the number of vertices and edges in the aforementioned graphs. An alternative way to achieving an edge-colored version of ΓL or ΞL would be to subdivide each colored edge, coloring the vertex used to subdivide it according to the edge color. This is illustrated below Table 2 in thecaseof ΓL. Computing Autotopism Groups of Partial Latin Rectangles 1.12:21 Fig. 8. Converting a partial Latin rectangle Linto its corresponding edge-colored induced subgraph of the rook’s graph ΞL, and a vertex-colored non-edge-colored graph ΞLwith the same automorphism group as the edge-colored ΞLfor use in nauty. Table 2. The Number of Vertices and Edges in an m-entry PLR(r,s,n)with no Unused Rows, Columns, nor Symbols no. vertices no. edges MMM graph m+r+s+n3m bipartite graph r+sm PLR graph ΓLmp∈0,...,m 2 PLR graph ΓL4m3m+p rook’s graph ΞLmq∈0,...,m 2 rook’s graph ΞL3m+n4m+q Note:Wemusthaveq≤p. In this setting, this subdivided version of ΓLis similar to the McKay, Meynert, and Myrvold (MMM) graph. More specifically, it is equivalent to taking the MMM graph and replacing each Ri with deg(Ri) 2vertices, each connected to a distinct pair of neighbors of Ri, and likewise for Sjand Nk. It has between m+pand 2pedges, with 0 ≤p≤m 2. The subdivided version of ΞLis similar to the subdivided version of ΓL, but we delete the vertices Nk, so the automorphism group of the graph will also not directly give the autotopism group of the partial Latin rectangle. It has between m+qvertices and 2qedges, with 0 ≤q≤m 2. We choose not to include these graphs in our experiments, as we expect them to be inferior to the MMM graph, particularly when mis much larger than r,s,andn. Moreover, unlike the MMM graph, the automorphism group of the subdivided version of ΞLdoes not directly give Atop(L). 1.12:22 R. J. Stones et al. We also choose not to include a tripartite graph version, with vertex tripartition {Ri}∪{Sj}∪ {Nk}and triangles RiSjNkwhenever L[i,j]=k. For Latin squares of order n, this graph would be isomorphic to Kn,n,nand using nauty to compute its automorphism group would not be helpful. 4 EXPERIMENTS A series of experiments testing the efficiency of all the algorithms described in the previous section have been implemented in C++, whose source codes are available in https://sites.google.com/site/ rebeccajstones/home/atop.tar.gz. 4.1 Setup In our experiments, we set the goal of computing the autotopism group size. While all of the described methods are capable of generating each element in the autotopism group (and we actually perform this task for the correctness certificate; see Section 4.1.1), the anticipated user of such software may or may not need such a list. However, some of the described methods cannot compute the autotopism group size without generating each element in the autotopism group, specifically the backtracking methods. Other methods require filtering nauty’s results, which we do by checking each element one-by-one. The three methods that do not need to generate the whole autotopism group are: •The MMM method. •The vertex-colored partial Latin rectangle graph method. •The vertex-colored rook’s graph method. In these cases, nauty gives generators of the automorphism groups of the input graphs, which are sufficient to determine the autotopism group size. In all other cases, we use nauty to generate the whole automorphism group, since the autotopism group of the input partial Latin rectangle is only isomorphic to a subgroup of the automorphism group computed by nauty. The six families of algorithms for computing autotopism groups that have been discussed throughout the article (two backtracking algorithms in Section 3.1 and four graph-theoretic algorithms in Section 3.2), together with the different autotopism invariants that we have mentioned (column vectors, SEIs, square invariants, and vertex invariants), give rise to 47 distinct methods to compare. We first run some tests to verify that these 47 methods function correctly. After this, we compare the 47 methods experimentally to deduce the five best methods, which are used for further experimentation. Unless otherwise specified, we calculate the average runtime over 10K random PLR(r, s, n)’s for some fixed parameters r, s,and n. We do this for each value of the independent variable x of the two test sets described in Section 1.2. Note that the independent variable x is different for the two test sets. The experimental platform has an Intel Core i7-4700MQ, 2.40 GHz processor (four physical cores) with 7895 MiB RAM running Linux Mint 19 (64-bit). The code was written in C++ (without parallelism, using static memory allocation) and compiled using G++ version 7.3.0 with -O3 optimization. Where possible, the same code is re-used for each method. Partial Latin rectangles are internally stored as lists of entries. 4.1.1 Correctness. Before the experimental program executes, a “correctness certificate” is generated. We perform the computation of the autotopism group for seven different input partial Latin rectangles, choosing the following variety of inputs: . Computing Autotopism Groups of Partial Latin Rectangles 1.12:23 •A random Latin square of order five. •A random Latin square of order nine that has been truncated to have five rows and seven columns. •A random Latin square of order six that has had four entries deleted. •A random Latin square of order 20 that has been truncated to have 10 rows and 10 columns, then has had 10 entries deleted. •ArandomPLR(7,8,9)after 100 tries at adding a random entry. •ArandomPLR(8,8,8)after 10K tries at adding a random entry. •ArandomPLR(7,7,7)after 3 tries at adding a random entry. Each of the 47 methods tested prints out their computed autotopism group for the same input, which is used to verify the computations are consistent. Moreover, a VERBOSE mode has been implemented in the C++ code, which if set, prints out the 47 autotopism group sizes computed for the first 20 samples in each experiment. These checks are not performed during experimentation, since it would interfere with the runtime measurements. 4.2 Choosing which to Compare We perform some initial experiments over all 47 methods and variations, for (r,s,n)∈{(5,5,5),(5,5,6),(5,6,6),(5,6,7)}. Based on these results, we eliminate six methods that would make subsequent experiments impractical to conduct, because of being simply too slow: (1)α-βbacktracking,(4)PLR graph (nauty,EC,SEI), (2)entrywise backtracking,(5)Rooksgraph(nauty,EC),and (3)PLR graph (nauty,EC),(6)Rooksgraph(nauty,EC,SEI). Regarding PLR set B for (r,s,n)=(5,5,5), there are only two species of Latin square of order five: one has an autotopism group of order 120 (the Cayley table of Z5) and the other one has an autotopism group of order 12 (formed by completing a 2 ×2 subsquare to a Latin square of order five). Thus, when we generate a random Latin square of order five, the result must be an autotopism group of order either 120 or 12. This situation is unlike random Latin squares of larger order, which have trivial autotopism groups with high probability [71]. Consequently, the runtime behavior for such small (r,s,n)may differ significantly to the behavior for larger (r,s,n). 4.3 Experimental Results 4.3.1 Run-time Experiments. Figure 9plots the best and average runtimes for the 41 remaining methods for (r,s,n)=(7,7,7). Notice that no single method is consistently best over all inputs. Indeed, simple backtracking methods are faster in many instances: Other methods are delayed by the time spent computing invariants and converting graphs to nauty’s internal graph format. Further, Figure 9also shows a significant difference in runtimes between “sparse” and “dense” partial Latin rectangles. This gives the motivation to investigate these two situations separately. 4.3.2 Instability. Figure 10 illustrates some methods showing instability on PLR Set A. We expect this instability arises because dense PLRs (particularly Latin rectangles and Latin squares) incur significantly higher runtimes than sparse PLRs. The method used to generate random PLRs in PLR Set A (which adds non-clashing entries randomly) sporadically generates dense PLRs and hence sporadically leads to significantly higher runtimes. This instability is an important design 1.12:24 R. J. Stones et al. Fig. 9. The best and average runtimes for (r,s,n)=(7,7,7)for the 41 methods (excluding 6 methods that are too slow to perform, as described in the main text). We mark which family of methods achieves the best runtime. Fig. 10. The runtimes for (r, s, n) = (7, 7, 7) for methods that indicate some instability. consideration for a user studying PLRs generated via a method akin to the method for PLR Set A (like Stones [85]). This issue does not arise in PLR Set B. Notice that Figure 10 shows some “spikes” in runtimes common to several methods, while other “spikes” are not common. We attribute this property to sporadically encountering random PLRs that happen to have many autotopisms. The α-β and entrywise bipartite graph methods (which only utilize nauty’s orbits) incur a significant runtime overhead when the partitions determined by nauty’s orbits contain large parts. This is unlike the plain bipartite graph method (which uses nauty’s internal functions for iterating through automorphisms of the bipartite graph). 4.3.3 Entry Invariants. When using entry invariants, we often deduce that the autotopism group is trivial (up to the autotopisms counted in Lemma 2.2). In these cases, further computation is not required. Figure 11 plots the proportion of partial Latin rectangles that require further computation when (r, s, n) ∈{(7, 7, 7), (7, 7, 8), (7, 8, 8), (7, 8, 9)}. We find that entry invariants are ineffective when a PLR has very few entries (likely because the PLR has non-trivial autotopisms). Further, while SEIs are more efficient to compute than square invariants, Figure 11 indicates that square invariants are more useful at reducing subsequent . Computing Autotopism Groups of Partial Latin Rectangles 1.12:25 Fig. 11. The proportion of partial Latin rectangles for which further computation is required, i.e., entry invariants alone cannot prove a trivial autotopism group. Fig. 12. The average runtime of the α-βbacktracking method with SEIs (left) and the proportion of partial Latin rectangles for which further computation is required when using SEIs (right). computation when there are many entries. Nevertheless, square invariants also become less useful as the density of the partial Latin rectangle increases. We conclude that sometimes it is worthwhile spending additional time in computing sophisticated entry invariants (such as for dense partial Latin rectangles), and sometimes it is not worthwhile (e.g., when the quickly computed SEI suffices to deduce a trivial autotopism group). 4.3.4 Sparse PLRs. We define an r×spartial Latin rectangle as sparse if its number of entries is at most 0.9rs. The motivation behind this 0.9 factor threshold is experimental. The first conclusion of our experiments is that the precise values of r,s,andndo not have a major effect on the average runtimes for sparse partial Latin rectangles. In contrast, for dense partial Latin rectangles, there is a significant difference between the s=nand s=n−1cases. Figure 12 (left) plots the average runtime of the α-βbacktracking method (using SEIs) for various (r,s,n)triples. This method consistently encounters huge runtimes with especially sparse partial Latin rectangles. Some versions of the bipartite graph method also have the problem with especially sparse partial Latin rectangles. Figure 13 plots the average runtime of the entrywise backtracking method using SEIs or square invariants for various (r,s,n)triples. We see that this method is reasonably stable and does not encounter the same problem as the α-βbacktracking method as in Figure 12.WealsoseeinFigure13 that the square-invariant runtime increases almost linearly with density or equivalently with the number of entries (with the gradient determined by rs). 1.12:32 R. J. Stones et al. Example 5.1. Let us consider the following partial Latin square of order six. L≡ 1· · 2· · ·3· · 4· · · 5· · 6 2· · 1· · ·4· · 3· · · 6· · 5 The ordered set E={(1,1,1),(2,2,3),(3,3,5)}constitutes a base of the autotopism group Atop(L).Toproveit,letθ=(α,β,γ)∈Atop(L)be a pointwise stabilizer of the set E. Sinceδ(i)=i, for all δ∈{α,β}and i∈{1,2,3},itmustbeδ(j)=j, for all j∈{4,5,6}. As a consequence, the autotopism θis indeed the trivial permutation in the symmetric group S6. The implementation of our theoretical graph methods in nauty (with the extra coloring of those vertices related to the corresponding pointwise stabilizer) enables us to ensure that Atop(L)(2)=((2356),(2356),(35)(46)),((2653),(2356),(36)(45)),((36),(36),Id),((36),Id,(56))  and Atop(L)(3)=((36),(36),Id),((36),Id,(56)) . In particular, •|Atop(L)(3):Atop(L)(4)|=4, because Atop(L)(3)((3,3,5)) ={(3,3,5)(3,6,6),(6,3,6),(6,6,5)};and •|Atop(L)(2):Atop(L)(3)|=8, because Atop(L)(2)((2,2,3)) =Ent(L)\{(1,1,1),(1,4,2),(4,1,2),(4,4,1)}. Furthermore, we have that the five autotopisms ((Id,(14),(12)),((14),Id,(12)),((14),(14),Id), ((12)(45),(12)(45),(13)(24)) and ((13)(46),(13)(46),(15)(26)) of the partial Latin square L map, respectively, the entry (1, 1, 1) to the entries (1, 4, 2), (4, 1, 2), (4, 4, 1), (2, 2, 3), and (3, 3, 5). This fact, together with the already described sets Atop(L)(3) ((3, 3, 5)) and Atop(L)(2) ((2, 2, 3)), enables us to ensure that the orbit of the entry (1, 1, 1) under the action of the autotopism group Atop(L) is the whole entry set Ent(L). In fact, the autotopism group Atop(L) acts transitively on the entry set Ent(L). Hence, from Equation (1), we have that |Atop(L)| = 12 · 8 · 4 = 384. Outside of cases with few entries, when working with randomly generated PLRs, computation mostly verifies that a PLR has a trivial autotopism group, unless some specific structure is imposed on the dataset. In these cases, invariants usually play a fundamental role. Nevertheless, as we are going to show now, one can find partial Latin rectangles for which these invariants are not useful. Choice of invariants. Entry invariants show varying usefulness as the experimental parameters change. This is mainly due to the existence of partial Latin rectangles for which the proposed entry invariants (more specifically, SEIs and square invariants) do not give any extra information about their autotopism groups. Thus, for instance, it is readily verified that SEIs are not useful for dealing with Latin squares. In any case, fullness is not a mandatory condition for finding this type of hard case. Thus, for instance, neither SEIs nor square invariants are useful to deal with the partial Latin Computing Autotopism Groups of Partial Latin Rectangles 1.12:33 square described in Example 5.1. The same happens, for example, with the following partial Latin rectangles. 1 2 · 2·1 ·1 2 1· · 2· · ·3· · 2· · · 1· · 3 Furthermore, there are partial Latin rectangles with non-trivial autotopism groups for which none of the proposed entry invariants gives the finest partition of rows and columns to determine their autotopism groups explicitly. The already-mentioned approach concerning bases of autotopism groups may also be useful for dealing with these kinds of partial Latin rectangles. This occurs in the following example, which has also been considered by the authors in a recent paper [23]. Example 5.2. Let us consider the following partial Latin square of order nine: L≡ ·94287·5 1 · · · 3· · 6· · 8 5 7 4 1 · · 9 2 5·1 8 7 9 ·2 4 9 2 5 7 4 1 ·8· 4 7 2 1 9 8 · · 5 1 4 ·9 2 5 ·7 8 · · · 6· · 3· · 7 1 8 5 ·2·4 9 The refinement methods described in Reference [23], which include in particular both SEIs and square invariants, establish 512,096,256,000 possible candidates for the autotopism group Atop(L), whose size is, however, 14. More specifically, all of these candidates preserve the following sets of rows, columns, and symbols, where rows and columns are labeled in natural order. •The two sets of rows {1,3,4,5,6,7,9}and {2,8}. •The three sets of columns {1,2,3,5,6,8,9},{4},and {7}. •The two sets of symbols {1,2,4,5,7,8,9}and {3,6}. To observe the efficiency of dealing with a base of the autotopism group Atop(L), let us consider, for instance, the ordered set {(1,9,1),(2,4,3)}⊂Ent(L). It constitutes a base of Atop(L),because the only non-trivial autotopism of Lpreserving the entry (1,9,1)is ((28),Id,(36)) ∈Atop(L).This fact also enables us to ensure that |Atop(L)(2):Atop(L)(3)|=2. From Equation (1), the size of the autotopism group is uniquely determined by the orbit of the entry (1,9,1)under the action of Atop(L). To compute such an orbit, we have made a repetitive use of the PLR method. More specifically, besides the usual description of that method, we have colored in an exclusive and equal way both the vertex corresponding to the entry (1,9,1)and a different vertex corresponding to any of the other entries. In this way, those vertex-colored graphs for which a non-trivial automorphism exists determine the orbit of the entry (1,9,1). According to nauty, they correspond to the six vertices (3,8,9),(4,5,7),(5,2,2),(6,1,4),(7,6,5),and (9,3,8). Together with the trivial autotopism, it enables us to ensure that |Atop(L)(1):Atop(L)(2)|=7, and hence, from Equation (1), that the size of the autotopism group Atop(L)is 14. 1.12:34 R. J. Stones et al. Further, we feel that software for computing autotopism groups would benefit from dynamically choosing which entry invariant to use. (1) Intermediate number of entries. A cheap-to-compute entry invariant (such as the SEI) is usually sufficient to prove a trivial autotopism group in this setting, and thus computing more sophisticated entry invariants would be wasteful. (2) Large number of entries. In this setting, the SEI is no longer effective, and we should use more sophisticated entry invariants. Moreover, we observed a “trap” in Section 4.3.6, where sorting a large number of similar entry invariants performs slowly, which is important to avoid. (3) Latin squares. Figure 16 indicates that methods for computing autotopism groups for PLRs will likely not work for Latin squares. The runtimes are wildly different for Latin squares and partial Latin rectangles in general, so we think of this as a separate problem. Other entry invariants may be more useful than the simple ones we propose here. For example, it may be possible to adapt the “train” entry invariant by Wanless [95] (for Latin squares) to partial Latin rectangles. It would also be interesting to explore a quadrangle-based entry invariant. A quadrangle of a Latin square L=(L[i,j])is a 4-tuple (L[i,j],L[i,j],L[i,j],L[i,j])for distinct rows iand i, and columns jand j.Then,Lis said to satisfy the quadrangle criterion if no two quadrangles agree at exactly three coordinates. If Lsatisfies the quadrangle criterion, then Lis isotopic to a group table. Thus, computing a quadrangle-based entry invariant will also facilitate distinguishing group-table Latin squares from non-group-table Latin squares.Notice in this regard that the former tend to have large autotopism groups, although group tables do not always achieve the maximum autotopism group sizes [21, Prob. 509]. Similarly to the just-mentioned quadrangle criterion, there exist some other methods for distinguishing group-table Latin squares from non-group-table Latin squares (see Reference [27]) that could also be implemented into the description of new entry invariants. A pair of these methods are: •The Thomsen condition [91]: A Latin square L=(L[i,j])is the Cayley table of an abelian group if and only if, for all three rowsi,j,kand three columns i,j,k, one has that L[i,j]= L[j,i], together with L[i,k]=L[k,i], implies that L[j,k]=L[k,j]. •The rectangle rule [14]: Let L=(L[i,j])be a reduced Latin square (that is, there exists a row and a column esuch that L[e,i]=L[i,e]=i, for all i). Moreover, for each row i,leti∗be such that L[i,i∗]=e.Then,Lis the Caley table of a group if and only if L[L[i,j∗],L[j,k∗]] = L[i,k∗], for all i,j,k. In this article, we have aimed to compare various algorithms for computation, so we have experimented using two basic entry invariants. The authors intend to study entry invariants, both theoretically and computationally, in future work. Large autotopism groups. In this work, we mainly experiment using randomized PLRs, where most have a trivial autotopism group (except when we have very few entries). We envisage this simulating a user’s average case, similar to how Stones [85] studied partial Latin rectangles. It is possible that a user instead wants to perform the computation for a set of partial Latin rectangles that likely includes symmetries. Or a user may be studying PLRs with large (or even transitive) autotopism groups. In this situation, entry invariants are less effective, or possibly even useless (such as for transitive autotopism groups). It is unlikely we can solve these challenge cases efficiently without, say, proving Graph Isomorphism is in P. Indeed, Stones [85] showed that any finite group is the autotopism group of a partial Computing Autotopism Groups of Partial Latin Rectangles 1.12:35 Latin square. In these settings, it may be beneficial to offload these problematic cases onto, e.g., a graphics processing unit (GPU) for separate computation. To achieve this, we need a method to recognize such cases. 5.2 Future Implementation Ideas In this article’s experiments, we observe that the MMM graph and PLR graph methods offer reasonable and stable performance under most conditions. Perhaps surprisingly, the PLR graph method is ordinarily faster than the standard MMM method. We attribute this to the PLR graph being smaller than the MMM graph. However, the MMM method is much faster than the PLR graph method when the Latin squares have many autotopisms, which we attribute to the filtering stage (needed in the PLR graph method, but not the MMM method). The PLR graph method could be improved by (1) finding mathematical conditions on when automorphisms of non-edge-colored partial Latin rectangle graphs are autotopisms of the corresponding partial Latin rectangle, (2) developing software for edge-colored graph automorphism,1or (3) developing purpose-built software that adapts the individualization/refinement approach of nauty and Bliss to the problem of computing autotopisms of partial Latin rectangles. In addition to eliminating the conversion overhead, this would allow us to directly use the inherent nature of autotopisms, rather than encode these as a graph. Furthermore, let us remark that one of the aims for developing the experiments of this study was to compare the efficiency of the proposed methods with those existing in the recent literature that make use of autotopism groups for solving the problems of counting, enumerating, and classifying PLRs [31,32,35,39,41]. Since all of them make use of non-parallel computing, this has also been our first choice. Nevertheless, to advance our long-term aim of developing efficient software for computing autotopism groups of PLRs, a much deeper theoretical and computational work has to be done to deal with the parallel processing approach of the problem. It is also established as further work. Notice in this regard that this parallel computing is particularly interesting for dealing with the already-mentioned PLRs with large (or even transitive) autotopism groups, where entry invariants do not aid subsequent computation. It might be possible to offload these problematic cases onto, for example, a GPU for separate computation. Finally, a much deeper study of bases and strong generating sets of autotopism groups of partial Latin rectangles, which have been briefly described in Section 5.1, is also established as further work. In computational group theory, such a study constitutes an efficient way for searching elements satisfying certain given properties within the group under consideration. More specifically, bases and strong generating sets are used to prune efficiently search trees having the group as root and its elements as leaves. In this regard, it is interesting to delve into the study about how known strong generators of the autotopism group of a given partial Latin rectangle can be used for pruning the search space in our backtracking methods to get more efficient algorithms. 5.3 Test Suites Generating suitable test suites also seems to be a difficult task. To identify the software design goals, we want a test suite that 1Bliss [52], available from http://www.tcs.hut.fi/Software/bliss/, also does not incorporate edge colors. 1.12:36 R. J. Stones et al. •is comparable to one a user may realistically be interested in studying, •tests the effectiveness of both entry invariants and the subsequent computation, •is not overly difficult to perform experiments on (given the instability of some of the methods), and •is parameterized, so we can compare how the methods scale as the parameters change. Instead of mostly verifying a partial Latin rectangle has a trivial autotopism group, a user may instead be researching partial Latin rectangles (or even Latin squares) with enforced symmetries, in which case the subsequent computation would be more significant. Designing an experimental test suite with enforced symmetries where the parameters can change is challenging, particularly when we want to vary the number of entries m. ACKNOWLEDGMENTS The authors want to express their gratitude to the anonymous referees for the comprehensive reading of the article and their pertinent comments and suggestions, which helped improve the manuscript. In particular, we are very grateful to the anonymous reviewer who noticed the fact that the problem of computing the set of generators of the autotopism group of a partial Latin rectangle is in fact graph-isomorphism complete (GI-complete) and who also suggested the use of bases and strong generating sets to deal with such a problem. The authors thank Zhuanhao Wu for assistance coding. REFERENCES [1] Nogan Alon, Eldar Fischer, and Mario Szegedy. 2001. Parent-identifying codes. J. Comb. Theory Series A 95, 2 (2001), 349–359. [2] Stephan D. Andres and Raúl M. Falcón. 2019. Colouring games based on autotopisms of Latin hyper-rectangles. Quaest. Math. 42 (2019), 953–975. [3] Raphael Artzy. 1954. A note on the automorphisms of special loops. Riveon Lemat. 8 (1954), 81. In Hebrew. [4] Masood Aryapoor and Ebadollah S. Mahmoodian. 2011. On uniformly generating Latin squares. Bull. Inst. Comb. Appl. 62 (2011), 48–58. [5] Pawan Aurora and Shashank K. Mehta. 2018. The QAP-polytope and the graph isomorphism problem. J. Comb. Optim. 36, 3 (2018), 965–1006. [6] László Babai. 2016. Graph isomorphism in quasipolynomial time. In Proceedings of the 48th ACM Symposium on Theory of Computing. ACM, New York, 684–697. [7] László Babai. 2018. Group, graphs, algorithms: the graph isomorphism problem. In Proceedings of the International Congress of Mathematicians. World Sci. Publ., Hackensack, NJ, 3319–3336. [8] László Babai. 2019. Canonical form for graphs in quasipolynomial time: Preliminary report. In Proceedings of the 51st ACM Symposium on Theory of Computing. ACM, New York, 1237–1246. [9] László Babai, William M. Kantor, and Eugene M. Luks. 1983. Computational complexity and the classification of finite simple groups. In Proceedings of the 24th IEEE Symposium on Foundations of Computer Science. IEEE, 162–171. [10] Rosemary A. Bailey. 1982. Latin squares with highly transitive automorphism groups. J. Aust. Math. Soc. 33 (1982), 18–22. [11] Simon R. Blackburn. 2000. Perfect hash families: Probabilistic methods and explicit constructions. J. Comb. Theory Ser. A 92 (2000), 54–60. [12] S. Booth and Charles J. Colbourn. 1979. Problems Polynomially Equivalent to Graph Isomorphism. Technical Report CS-77-04, Computer Science Department, University of Waterloo. [13] Raj C. Bose. 1963. Strongly regular graphs, partial geometries and partially balanced designs. Pacif. J. Math. 13 (1963), 389–419. [14] Heinrich Brandt. 1927. Über eine verallgemeinerung des gruppenbegriffes. Math. Ann. 96, 1 (1927), 360–366. [15] Joshua Browning, Douglas S. Stones, and Ian M. Wanless. 2013. Bounds on the number of autotopisms and subsquares of a Latin square. Combinatorica 33 (2013), 11–22. [16] Darryn Bryant, Melinda Buchanan, and Ian M. Wanless. 2009. The spectrum for quasigroups with cyclic automorphisms and additional symmetries. Disc. Math. 304, 4 (2009), 821–833. [17] Gregory Butler and Clement W. H. Lam. 1985. A general backtrack algorithm for the isomorphism problem of combinatorial objects. J. Symb. Comput. 1, 4 (1985), 363–381. Computing Autotopism Groups of Partial Latin Rectangles 1.12:37 [18] Peter C. Cameron. 2015. Asymmetric Latin squares, Steiner triple systems, and edge-parallelisms. (2015). Retrieved from arXiv:1507.02190 [math.CO]. [19] Peter J. Cameron. 1975. Minimal edge-colourings of complete graphs. J. London Math. Soc. (2) 11, 3 (1975), 337–346. [20] Peter J. Cameron. 1976. Parallelisms of Complete Designs. Cambridge University Press, Cambridge-New York- Melbourne. 144 pages. [21] Peter J. Cameron. 2011. Research problems from the BCC22. Disc. Math. 311 (2011), 1074–1083. [22] Nicholas J. Cavenagh and Douglas S. Stones. 2011. Near-automorphisms of Latin squares. J. Combi. Des. 19 (2011), 365–377. [23] Eiran Danan, Raúl M. Falcón, Dani Kotlar, Trent G. Marbach, and Rebecca J. Stones. 2020. Refining invariants for computing autotopism groups of partial latin rectangles. Disc. Math. 343, 5 (2020), 111812, 21. [24] Fatih Demirkale, Akira Kamibeppu, Trent G. Marbach, Oktay Olmez, and Rebecca J. Stones. 2019. Graph Latinity. (2019). In preparation. [25] Stephen DeSalvo. 2016. Exact sampling algorithms for Latin squares and sudoku matrices via probabilistic divide- and-conquer. Algorithmica 79, 3 (2016), 1–21. [26] Arthur A. Drisko. 1997. Loops of order pn+1 with transitive automorphism groups. Adv. Math. 128 (1997), 36–39. [27] Anthony B. Evans. 2018. When Is a Latin Square Based on a Group? Springer International Publishing, Cham, 41–63. [28] Raúl M. Falcón. 2006. Latin squares associated to principal autotopisms of long cycles. Application in cryptography. In Proceedings of Transgressive Computing 2006: A Conference in Honor of Jean Della Dora. TC2006, 213–230. [29] Raúl M. Falcón. 2012. The compressed shape of a partial Latin rectangle. In Proceedings of the Spanish Meeting on Computer Algebra and Applications. 95–98. [30] Raúl M. Falcón. 2012. Cycle structures of autotopisms of the Latin squares of order up to 11. Ars Combin. 103 (2012), 239–256. [31] Raúl M. Falcón. 2013. The set of autotopisms of partial Latin squares. Disc. Math. 313, 11 (2013), 1150–1161. [32] Raúl M. Falcón. 2015. Enumeration and classification of self-orthogonal partial Latin rectangles by using the polynomial method. Eur. J. Comb. 48 (2015), 215–223. [33] Raúl M. Falcón. 2020. Using a CAS/DGS to analyze computationally the configuration of planar bar linkage mechanisms based on partial Latin squares. Math. Comput. Sci. 14 (2020), 375–389. [34] Raúl M. Falcón and Stephan D. Andres. 2019. Autotopism stabilized colouring games on rook’s graphs. Disc. Appl. Math. 266 (2019), 200–212. [35] Raúl M. Falcón, Óscar J. Falcón, and Juan Núñez. 2018. Counting and enumerating partial Latin rectangles by means of computer algebra systems and CSP solvers. Math. Meth. Appl. Sci. 41 (2018), 7236–7262. [36] Raúl M. Falcón, Óscar J. Falcón, and Juan Núñez. 2018. A historical perspective of the theory of isotopisms. Symmetry 10 (2018), 1–21. [37] Raúl M. Falcón and Jorge Martín-Morales. 2007. Gröbner bases and the number of Latin squares related to autotopisms of Order ≤7. J. Symb. Comput. 42, 11–12 (2007), 1142–1154. [38] Raúl M. Falcón and Juan Núñez. 2007. Partial Latin squares having a Santilli’s autotopism in their autotopism groups. J. Dyn. Syst. Geom. Theor. 5 (2007), 19–32. [39] Raúl M. Falcón and Rebecca J. Stones. 2015. Classifying partial Latin rectangles. Electron. Notes Disc. Math. 49 (2015), 765–771. [40] Raúl M. Falcón and Rebecca J. Stones. 2017. Partial Latin rectangle graphs and autoparatopism groups of partial Latin rectangles with trivial autotopism groups. Disc. Math. 340, 6 (2017), 1242–1260. [41] Raúl M. Falcón and Rebecca J. Stones. 2020. Enumerating partial Latin rectangles. Electron. J. Comb. 27, 2 (2020), #P2.47. [42] Wang Fang, Rebecca J. Stones, Trent G. Marbach, Gang Wang, and Xiaoguang Liu. 2019. Towards a Latinsquare search engine. In Proceedings of the IEEE International Conference on Parallel Distributed Processing with Applications, Big Data Cloud Computing, Sustainable Computing Communications, Social Computing Networking (ISPA/BDCloud/SocialCom/SustainCom’19). IEEE, 727–735. [43] Stanley Fiorini and Robin J. Wilson. 1976. Edge-colourings of graphs-Some applications. In Proceedings of the 5th British Combinatorial Conference. 193–202. [44] Timothy Gowers and Jason Long. 2016. The length of an s-increasing sequence of r-tuples. Retrieved from arXiv:1609.08688 [math.CO]. [45] Martin Grohe, Daniel Neuen, and Pascal Schweitzer. 2018. A faster isomorphism test for graphs of small degree. In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS’18). IEEE Computer Society, Los Alamitos, CA, 89–100. DOI:https://doi.org/10.1109/FOCS.2018.00018 [46] Martin Grohe, Daniel Neuen, Pascal Schweitzer, and Daniel Wiebking. 2018. An improved isomorphism test for bounded-tree-width graphs. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (LIPIcs), Vol. 107. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 14. 1.12:38 R. J. Stones et al. [47] Ram P. Gupta. 1978. On the chromatic index and the cover index of a multigraph. In Proceedings of the Theory and Applications of Graphs (Lecture Notes in Math.), Vol. 642. 204–215. [48] A. J. W. Hilton. 1977. Embedding incomplete Latin rectangles and extending the edge colourings of graphs. Nanta Math. 10, 2 (1977), 201–206. [49] Alexander Hulpke, Petteri Kaski, and Patric R. J. Östergård. 2011. The number of Latin squares of order 11. Math. Comp. 80 (2011), 1197–1219. [50] Edwin C. Ihrig and Benjamin M. Ihrig. 2008. The recognition of symmetric Latin squares. J. Comb. Des. 16, 4 (2008), 291–300. [51] Mark Jacobson and Peter Matthews. 1996. Generating uniformly distributed Latin squares. J. Comb. Des. 4, 6 (1996), 405–437. [52] Tommi Junttila and Petteri Kaski. 2007. Engineering an efficient canonical labeling tool for large and sparse graphs. In Proceedings of the SIAM Workshop on Algorithm Engineering and Experiments. SIAM, 135–149. [53] Petteri Kaski. 2005. Algorithms for Classification of Combinatorial Objects. Ph.D Thesis. Teknillinen Korkeakoulu, Helsinki, Finland. [54] Petteri Kaski and Patric R. J. Östergård. 2006. Classification Algorithms for Codes and Designs (Algorithms and Computation in Mathematics), Vol. 15. Springer-Verlag, Berlin. [55] A. D. Keedwell. 1994. Critical sets and critical partial Latin squares. In Proceedings of the Combinatorics, Graph Theory, Algorithms and Applications Conference. World Science Publishing, River Edge, NJ, 111–123. [56] Brent Kerby and Jonathan D. H. Smith. 2010. Quasigroup automorphisms and symmetric group characters. Comment. Math. Univ. Carol. 51, 2 (2010), 279–286. [57] Brent Kerby and Jonathan D. H. Smith. 2010. Quasigroup automorphisms and the Norton-Stein complex. Proc. Amer. Math. Soc. 138 (2010), 3079–3088. [58] Stefan Klus and Tuhin Sahai. 2018. A spectral assignment approach for the graph isomorphism problem. Inf. Inference 7, 4 (2018), 689–706. [59] G. Kolesova, C. W. H. Lam, and L. Thiel. 1990. On the number of 8 ×8 Latin squares. J. Comb. Theory Ser. A 54, 1 (1990), 143–148. [60] Daniel Kotlar. 2012. Parity types, cycle structures and autotopisms of Latin squares. Electron. J. Comb. 19, 3 (2012). [61] Daniel Kotlar. 2014. Computing the autotopy group of a Latin square by cycle structure. Disc. Math. 331 (2014), 74–82. [62] Jeffrey S. Leon. 1979. An algorithm for computing the automorphism group of a Hadamard matrix. J. Comb. Theory Ser. A 27, 3 (1979), 289–306. [63] Jeffrey S. Leon. 1982. Computing automorphism groups of error-correcting codes. IEEE Trans. Inf. Theory 28, 3 (1982), 496–511. [64] Jeffrey S. Leon. 1984. Computing automorphism groups of combinatorial objects. In Proceedings of the Conference on Computational Group Theory. Academic Press, London, 321–335. [65] Brendan D. McKay. 1978. Computing automorphisms and canonical labellings of graphs. In Proceedings of the International Conference on Combinatorial Mathematics (Lecture Notes in Math.), Vol. 686. Springer, Berlin, 223–232. [66] Brendan D. McKay. 1981. Practical graph isomorphism. Congr. Numer. 30 (1981), 45–87. [67] Brendan D. McKay. 1998. Isomorph-free exhaustive generation. J. Algor. 26, 2 (1998), 306–324. [68] Brendan D. McKay, Alison Meynert, and Wendy Myrvold. 2007. Small Latin squares, quasigroups, and loops. J. Comb. Des. 15 (2007), 98–119. [69] Brendan D. McKay and Adolfo Piperno. 2014. Practical graph isomorphism, II. J. Symb. Comput. 60 (2014), 94–112. [70] Brendan D. McKay and Ian M. Wanless. 1999. Most Latin squares have many subsquares. J. Comb. Theory Ser. A 86 (1999), 323–347. [71] Brendan D. McKay and Ian M. Wanless. 2005. On the number of Latin squares. Ann. Comb. 9 (2005), 335–344. [72] Brendan D. McKay, Ian M. Wanless, and Xiande Zhang. 2015. The order of automorphisms of quasigroups. J. Comb. Des. 23 (2015), 275–288. [73] Mahamendige J. L. Mendis and Ian M. Wanless. 2017. Autoparatopisms of quasigroups and latin squares. J. Comb. Des. 25 (2017), 51–74. [74] Hui Meng, Yumin Zheng, and Yuge Zheng. 2008. The classification construction and the non-isomorphism counting of symmetric Latin square. Adv. Stud. Contemp. Math. (Kyungshang) 17, 2 (2008), 169–179. [75] Gary L. Miller. 1977. Graph isomorphism, general remarks. In Proceedings of the 9th ACM Symposium on Theory of Computing. ACM, New York, 143–150. [76] Gary L. Miller. 1978. On the nlog nisomorphism technique: A preliminary report. In Proceedings of the 10th ACM Symposium on Theory of Computing. Springer, Berlin, 51–58. [77] Elchanan Mossel and Jiaming Xu. 2019. Seeded graph matching via large neighborhood statistics. In Proceedings of the 13th ACM-SIAM SDA. SIAM, 1005–1014. Computing Autotopism Groups of Partial Latin Rectangles 1.12:39 [78] Ronald C. Read and Derek G. Corneil. 1977. The graph isomorphism disease. J. Graph Theory 1, 4 (1977), 339–363. [79] Pascal Schweitzer and Daniel Wiebking. 2019. A unifying method for the design of algorithms canonizing combinatorial objects. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC’19).ACM, New York, 1247–1258. [80] Nicolas Sendrier. 2000. Finding the permutation between equivalent linear codes: The support splitting algorithm. IEEE Trans. Inform. Theory 46, 4 (2000), 1193–1203. [81] Ákos Seress. 2003. Permutation Group Algorithms (Cambridge Tracts in Mathematics), Vol. 152. Cambridge University Press, Cambridge, UK. [82] Charles C. Sims. 1970. Computational methods in the study of permutation groups. In Proceedings of the Conference on Computational Problems in Abstract Algebra. 169–183. [83] Charles C. Sims. 1971. Determining the conjugacy classes of a permutation group. In Computers in Algebra and Number Theory (Proceedings of the SIAM-AMS Symposium on Applied Mathematics, New York, 1970),Vol.IV.Amer. Math. Soc., Providence, RI, 191–195. [84] Douglas S. Stones. 2010. The many formulae for the number of Latin rectangles. Electron. J. Comb. 17 (2010), A1. [85] Douglas S. Stones. 2013. Symmetries of partial Latin squares. Eur. J. Comb. 34, 7 (2013), 1092–1107. [86] Douglas S. Stones, Petr Vojtěchovský, and Ian M. Wanless. 2012. Cycle structure of autotopisms of quasigroups and Latin squares. J. Comb. Des. 20 (2012), 227–263. [87] Rebecca J. Stones. 2020. K-plex 2-Erasure codes and Blackburn partial Latin squares. IEEE Trans. Inf. Theory 66, 6 (2020), 3704–3713. [88] Rebecca J. Stones, Raúl M. Falcón, Daniel Kotlar, and Trent G. Marbach. 2020. Computing autotopism groups of partial Latin rectangles: A pilot study. Comput. Math. Method. Early view (2020), e1094. DOI:https://doi.org/10.1002/ cmm4.1094 [89] Rebecca J. Stones, Ming Su, Xiaoguang Liu, Gang Wang, and Sheng Lin. 2015. A Latin square autotopism secret sharing scheme. Des. Codes Cryptogr. 35 (2015), 1–16. [90] The GAP Group. 2018. GAP—Groups, Algorithms, Programming—A system for computational discrete algebra. Retrieved from http://www.gap-system.org/. [91] Gerhard Thomsen. 1929. Topologische fragen der differentialgeometrie XII. schnittpunktssätze in ebenen geweben. Abh. Math. Sem. Univ. Hamburg 7, 1 (1929), 99–106. [92] Svetlana Topalova. 2003. Classification of Hadamard matrices of order 44 with automorphisms of order 7. Disc. Math. 260, 1–3 (2003), 275–283. [93] Ian M. Wanless. 2002. A generalisation of transversals for Latin squares. Electron. J. Comb. 9, 1 (2002). [94] Ian M. Wanless. 2004. A partial Latin squares problem posed by Blackburn. Bull. Inst. Comb. Appl. 42 (2004), 76–80. [95] Ian M. Wanless. 2005. Atomic Latin squares based on cyclotomic orthomorphisms. Electron. J. Comb. 12 (2005). [96] Ian M. Wanless and Edwin C. Ihrig. 2005. Symmetries that Latin squares inherit from 1-factorizations. J. Comb. Des. 13 (2005), 157–172. [97] B. Weisfeiler. 1976. On Construction and Identification of Graphs. Springer-Verlag, Berlin-New York. [98] David E. Woolbright. 1978. An n×nlatin square has a transversal with at least n−√ndistinct symbols. J. Comb. Theory Ser. A 24, 2 (1978), 235–237. DOI:https://doi.org/10.1016/0097-3165(78)90009-2 [99] Meng Yan, Jiaqi Feng, Trent G. Marbach, Rebecca J. Stones, Gang Wang, and Xiaoguang Liu. 2019. Gecko: A resilient dispersal scheme for multi-cloud storage. IEEE Access 7 (2019), 77387–77397. DOI:https://doi.org/10.1109/ACCESS. 2019.2920405 [100] Qifa Yan, Minquan Cheng, Xiaohu Tang, and Qingchun Chen. 2017. On the placement delivery array design for centralized coded caching scheme. IEEE Trans. Inf. Theory 63, 9 (2017), 5821–5833. [101] Liping Yi, Rebecca J. Stones, and Gang Wang. 2019. Two-erasure codes from 3-plexes. In Network and Parallel Computing, Xiaoxin Tang, Quan Chen, Pradip Bose, Weiming Zheng, and Jean-Luc Gaudiot (Eds.). Springer International Publishing, Cham, 264–276.