A census of critical sets based on non-trivial autotopisms of Latin squares of order up to five

See discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/344513568 A census of critical sets based on non-trivial autotopisms of Latin squares of order up to five ArticleinAIMS Mathematics · October 2020 DOI: 10.3934/math.2021017 CITATIONS 0 READS 5 3 authors, including: Some of the authors of this publication are also working on these related projects: Codes, Designs, Cryptography and Optimization View project Generalized isotopisms View project Raúl M. Falcón Universidad de Sevilla 215 PUBLICATIONS475 CITATIONS SEE PROFILE All content following this page was uploaded by Raúl M. Falcón on 10 October 2020. The user has requested enhancement of the downloaded file. http://www.aimspress.com/journal/Math AIMS Mathematics, 6(1): 261–295. DOI:10.3934/math.2021017 Received: 14 August 2020 Accepted: 07 October 2020 Published: 10 October 2020 Research article A census of critical sets based on non-trivial autotopisms of Latin squares of order up to five Ra´ ul M. Falc´ on1,∗, Laura Johnson2and Stephanie Perkins2 1Department of Applied Mathematics I. Universidad de Sevilla, Spain 2School of Computing and Mathematics. University of South Wales, United Kingdom *Correspondence: Email: rafalg[email protected]. Abstract: This paper delves into the study of critical sets of Latin squares having a given isotopism in their autotopism group. Particularly, we prove that the sizes of these critical sets only depend on both the main class of the Latin square and the cycle structure of the isotopism under consideration. Keeping then in mind that the autotopism group of a Latin square acts faithfully on the set of entries of the latter, we enumerate all the critical sets based on autotopisms of Latin squares of order up to five. Keywords: Latin square; autotopism; cycle structure; critical set; enumeration Mathematics Subject Classification: 05B15 1. Introduction Apartial Latin square of order nis an n×narray whose cells are either empty or filled by one element of a set of ndistinct symbols so that each symbol appears at most once per row and at most once per column. The number of non-empty cells is its size. If this size is n2(that is, if all the cells are filled), then the partial Latin square is indeed a Latin square of order n. From here on, let PLSnand LSnrespectively denote the set of partial Latin squares of order nand its subset of Latin squares of the same order, both of them having the set [n] :={1,...,n}as sets of symbols. Every partial Latin square P=(pi j)∈PLSnis uniquely determined by its set of entries Ent(P) :={(i,j,pi j): i,j,pi j ∈[n]}. Acompletion of Pis any Latin square L∈LSnsuch that Ent(P)⊆Ent(L). Then, it is said that Pis completable to L. If there exists precisely one such a Latin square L, then Pis said to be uniquely completable. The problem of deciding whether a partial Latin square is uniquely completable is NP- complete [1], even if one such completion is previously given. In fact, the problem of deciding the existence of a completion also is NP-complete [2]. 262 In 1977, John Ashworth Nelder [3] termed critical set of a Latin square L∈LSnto any partial Latin square P∈PLSnthat is uniquely completable to Land such that, for every P0∈PLSnsatisfying that Ent(P0)⊂Ent(P), there exists a distinct Latin square L0∈LSn\ {L}such that Ent(P0)⊂Ent(L0). It is said to be minimal if there does not exist any critical set of Lof a smaller size. Furthermore, it is said to be strong if its set of entries can sequentially be filled by a series of forced entries. Remind in this regard that a forced entry in a partial Latin square P∈PLSnis a triple (i,j,k)∈[n]×[n]×[n] such that the cell (i,j) is the only empty one either in the ith row or the jth column of P, and the symbol k is the only one not appearing in the respective row or column. Illustrative examples of strong minimal critical sets of Latin squares of order up to six appear in [4] (for higher orders, see also [5,6]). Nelder also introduced the problem of determining the respective sizes, scs(n) and lcs(n), of the smallest and largest critical set of any given Latin square of order n. Two years later, Bohdan Smetaniuk [7] proved that scs(2n)≤ bn2/4c, by also ensuring indeed the existence of critical sets of such size, as conjectured by Nelder. At the same time, this fact was independently discovered by Donald Joseph Curran and Gerrit Hendrik Johannes Van Rees [8], who also proved the same inequality for the odd case. Moreover, they determined the value scs(n), for all n≤5, together with some bounds for both sizes scs(n) and lcs(n). This last value was also analyzed in 1982 by Douglas Robert Stinson and van Rees [9]. Since these first studies, a wide amount of authors have dealt with critical sets of Latin squares. For several surveys on this topic, we refer the reader to the manuscripts of Anne Penfold Street [10], Keedwell [11–13] and Nicholas J. Cavenagh [14]. The set of critical sets of a given partial Latin square is known for all isotopism and main classes of Latin squares of order up to seven [15,16]. Remind in this regard that, if Sndenotes the symmetric group on the set [n], then every triple Θ = (α, β, γ)∈Sn×Sn×Snis called an isotopism from a partial Latin square P=(pi j)∈PLSnto its isotopic partial Latin square PΘ∈PLSn, where Ent(PΘ)={(α(i), β(j), γ(pi j))): (i,j,pi j)∈Ent(P)}. In other words, the partial Latin square PΘarises from Pafter permuting its rows, columns and symbols respectively by α,βand γ. Further, if π∈S3, then the partial Latin square Pπ∈PLSn, where Ent(Pπ)={(iπ(1),iπ(2),iπ(3)): (i1,i2,i3)∈Ent(P)} is said to be a conjugate of P, and the permutation πis called a parastrophism from Pto Pπ. In other words, the partial Latin square Pπarises from Pafter interchanging the role of its rows, columns and symbols. Finally, two partial Latin squares are said to be paratopic or to be in the same main class if the former is isotopic to a conjugate of the latter. To be isotopic, conjugate and paratopic are equivalence relations among partial Latin squares of the same order. The distribution of Latin squares into isotopism and main classes is known [17–19] for order up to 11, and that of partial Latin squares is known [20–24] for order up to six. Further, if PΘ=P, then the triple Θis called an autotopism of the partial Latin square P. It is known [25] that a Latin square of order nhas at most nO(log n)autotopisms. The set Atop(P) of all autotopisms of a partial Latin square Pconstitutes a group under composition of permutations, which is termed the autotopism group of P. This group acts faithfully on the set of entries of P. The study of autotopism groups of partial Latin squares is currently an active area of research [20,26–28], with special emphasis on the study of invariants that facilitate their computation [29–34], and its possible applications in cryptography and coding theory [35–38]. For a recent survey on the theory of isotopisms, we refer the reader to [39]. AIMS Mathematics Volume 6, Issue 1, 261–295. 263 In the early 2000’s, the concept of completability was generalised [40, 41] to that of F- completability, where Fis any given set of Latin square isotopisms. More specifically, a partial Latin square P∈PLSnis called F-completable if there exists a completion L∈LSnof the former such that Θ∈Atop(L), for all Θ∈F. If such a Latin square is unique, then Pis said to be uniquely F-completable. Moreover, it is called an F-critical set of Lif this last property does not hold for any partial Latin square Qsuch that Ent(Q)⊂Ent(P). As such, these concepts generalise the classical ones, which arise when the set Fis formed only by the trivial isotopism. More generally, if Fis formed by only one isotopism Θ = (α, β, γ)∈Sn×Sn×Sn, then the notion of being (uniquely) Θ-completable and that one of being a Θ-critical set arise analogously [20]. In particular, if Pis Θ-completable, then it is also Θ-compatible [42], that is, every entry (i,j,k)∈Ent(P) satisfies that, for each positive integer m, either the cell (αm(i), βm(j)) is empty, or (αm(i), βm(j), γm(k)) ∈Ent(P). Some particular cases of Θ-completability have already been considered in [43–45]. In spite of its implementations in cryptography [40] and graph colouring games [42], not much is known about this topic. This paper is organised as follows. Section 2 describes some preliminary lemmas that are later used throughout the paper. In particular, Table 4 enumerates the cases that are enough to study for determining the census of critical sets based on autotopisms of Latin squares of order up to five. Then, we introduce in Section 3 the concept of Θ-orbits of a Latin square, where Θis an isotopism in its autotopism group. We show how this notion can be used for determining the possible sizes of the corresponding Θ-critical sets. In Section 4, we introduce the notion of partial subsquares of a Latin square as a generalization of a subsquare. The latter is any of the subarray of a Latin square that within itself constitutes as a Latin square. Then, we show how the overlapping of Θ-orbits and partial subsquares within a given Latin square may be used to determine its Θ-critical sets. Finally, due to the high dependence on notation, Appendix A gives a glossary of repeatedly used notation. 2. Some preliminary lemmas In this section, we establish a series of preliminary lemmas that are later used in our study. Our first result deals with the composition of permutations and isotopisms. Lemma 1. Let us consider an isotopism Θ = (δ1, δ2, δ3)∈Sn×Sn×Snand a permutation π∈S3. Let us define the isotopism Θπ:=(δπ(1), δπ(2), δπ(3))∈Sn×Sn×Sn. Then, (Pπ)Θπ=(PΘ)π, for all partial Latin square P ∈PLSn, Proof. Suppose Θ = (δ1, δ2, δ3). The result follows from the fact that Ent (Pπ)Θπ=(δπ(1)(iπ(1)), δπ(2)(iπ(2)), δπ(3)(iπ(3))): (i1,i2,i3)∈Ent(P) ={(iπ(1),iπ(2),iπ(3)): (i1,i2,i3)∈Ent(PΘ)} =Ent (PΘ)π.  AIMS Mathematics Volume 6, Issue 1, 261–295. 264 Example 2. Let us consider the Latin square of order four L≡ 1234 2341 3412 4123 and its conjugate by the permutation π=(123) ∈S3. That is, Lπ≡ 1 4 3 2 2 1 4 3 3 2 1 4 4 3 2 1 . Now, let us consider the isotopism Θ = ((12)(34),(1234),(123)(4)) ∈S4×S4×S4. Then, LΘ≡ 2 3 1 4 4 2 3 1 1 4 2 3 3 1 4 2 and Θπ=((123)(4),(12)(34),(1234)). Hence, (Lπ)Θπ≡ 3 4 1 2 1 2 3 4 2 3 4 1 4 1 2 3 ≡(LΘ)π. Let L∈LSnand Θ∈Atop(L). From now on, let CSΘ(L) denote the set of Θ-critical sets of the Latin square L. Furthermore, let scsΘ(L) and lcsΘ(L) respectively denote the sizes of the smallest and the largest Θ-critical set of L. The following results enable us to ensure that the sizes of the smallest and largest critical sets for the whole autotopism group of any given Latin square are only dependant on the main class of the latter. Lemma 3. There is a one-to-one correspondence between the autotopism groups of any pair of paratopic partial Latin squares. Proof. Let P1,P2∈PLSnbe two paratopic partial Latin squares. Thus, there exist a permutation π∈S3 and an isotopism Θ∈Sn×Sn×Snsuch that P2=((P1)π)Θ. Then, the result follows straightforwardly from Lemma 1. More specifically, if Θ1∈Atop(P1), then ΘΘπ 1Θ−1∈Atop(P2).  Proposition 4. Let L1,L2∈LSnbe two paratopic Latin squares such that L2=((L1)π)Θ, for some permutation π∈S3and some isotopism Θ∈Sn×Sn×Sn. Let Θ1∈Atop(L1)and let Θ2= ΘΘπ 1Θ−1∈ Atop(L2). Then, there is a one-to-one correspondence between both sets CSΘ1(L1)and CSΘ2(L2)so that scsΘ1(L1)=scsΘ2(L2)and lcsΘ1(L1)=lcsΘ2(L2). AIMS Mathematics Volume 6, Issue 1, 261–295. 265 Proof. The result follows straightforwardly from the proof of Lemma 3. More specifically, if P∈ CSΘ1(L1), then (Pπ)Θ∈CSΘ2(L2).  From the previous results, our study may focus on the following representatives of main classes of Latin squares of order 2 ≤n≤5. (Notice that the case n=1 is trivial.) L2≡1 2 2 1 L3≡ 1 2 3 2 3 1 3 1 2 L4.1≡ 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 L4.2≡ 1 2 3 4 2 1 4 3 3 4 2 1 4 3 1 2 L5.1≡ 12345 23451 34512 45123 51234 L5.2≡ 12345 21453 34512 45231 53124 (2.1) In practice, it is not necessary to study the whole autotopism group of a given Latin square Lin order to compute the sizes of its Θ-critical sets, for all Θ∈Atop(L). More specifically, it is enough to focus on a representative of each conjugacy class of the autotopism group. Remind in this regard that two elements aand bof a given group Gare said to be conjugate if and only if there exists a third element c∈Gsuch that b=cac−1. To be conjugate constitutes an equivalence relation among the elements of the group. Hence, conjugacy classes determine a partition of the group under consideration. Lemma 5. Let Θ1and Θ2be two conjugate autotopisms within the autotopism group of a Latin square L∈LSn. Then, there is a one-to-one correspondence between both sets CSΘ1(L)and CSΘ2(L)so that scsΘ1(L)=scsΘ2(L)and lcsΘ1(L)=lcsΘ2(L). Proof. Let Θ = (α, β, γ)∈Atop(L) be such that Θ2= ΘΘ1Θ−1. In order to prove the result, it is enough to describe a one-to-one correspondence between both sets CSΘ1(L) and CSΘ2(L). To this end, if P∈CSΘ1(L), let us see that PΘ∈CSΘ2(L). Firstly, notice that Ent(P)⊆Ent(L), because P∈CSΘ1(L). As a consequence, Ent(PΘ)⊆Ent(LΘ)= Ent(L), because Θ∈Atop(L). Now, suppose the existence of an entry e=(i,j,k)∈Ent(P) and a Latin square L0∈LSn\ {L}such that Ent(PΘ)\ {e} ⊂ Ent(L0) and Θ2∈Atop(L0). Let PΘ {e}denote the partial Latin square of order nthat results after removing the entry efrom PΘ. Then, PΘ {e}Θ−1 is the partial Latin square of order nthat results after removing the entry Θ−1(e)=(α−1(i), β−1(j), γ−1(k)) from P. Hence, Ent(P)\ {Θ−1(e)} ⊂ Ent L0Θ−1. Moreover, Θ1∈Atop L0Θ−1, because L0Θ−1Θ1=L0Θ1Θ−1=L0Θ−1Θ2=L0Θ2Θ−1 =L0Θ−1. Furthermore, notice that L0Θ−1,L. Otherwise, it would be L0=LΘ=L, which is not possible. Thus, P<CSΘ1(L), which is a contradiction. As a consequence, PΘ∈CSΘ2(L).  AIMS Mathematics Volume 6, Issue 1, 261–295. 266 Notice also that all the autotopisms within the same conjugacy class have the same cycle structure. Remind in this regard that the cycle structure of an isotopism Θ = (α, β, γ)∈Sn×Sn×Snis defined as the triple zΘ:=(zα,zβ,zγ) formed by the respective cycle structures of the permutations α,βand γ. Remind also to this end that the cycle structure of a permutation π∈Snis the expression zπ:= nλπ n...nλπ 1, where λl(π) denotes the number of cycles of length lin the unique decomposition of πas a product of disjoint cycles. In practice, it is written only those factors for which λπ l>0. Moreover, each factor of the form l1is replaced by l. Thus, for instance, the cycle structure of the permutation (123)(45)(67)(8) ∈S8is 3221, and that one of the isotopism ((123)(4),(12)(34),(1234)) ∈S4×S4× S4is the triple (31,22,4). It is known that the number of Latin squares having a given isotopism in their autotopism group only depends on the cycle structure of such an isotopism. This number has computationally been determined [46] for all autotopisms of Latin squares of order up to seven. Furthermore, the set of cycle structures of Latin squares of order nis currently known [20, 47] for all n≤17. In this paper, we focus on the autotopisms of Tables 1–3, which constitute representatives of the conjugacy classes of each one of the autotopism groups of the Latin squares described in (2.1). To this end we have made use of the library pls.lib, which is available online on http://personales.us. es/raufalgan/LS/pls.lib, for the open computer algebra system for polynomial computations SINGULAR [48]. From here on, we denote Idnthe trivial permutation in the symmetric group Sn. Moreover, fixed points are not explicitly indicated. In addition, in order to illustrate the computation of representatives of conjugacy classes in Tables 1–3, the following example describes the case when n=3 in detail. Table 1. Representatives of conjugacy classes of the autotopism groups of L2and L3. L∈LSnΘ∈Atop(L)zΘ L2(Id2,Id2,Id2) (12,12,12) (Id2,(12),(12)) (12,2,2) ((12),Id2,(12)) (2,12,2) ((12),(12),Id2) (2,2,12) L3(Id3,Id3,Id3) (13,13,13) (Id3,(123),(123)) (13,3,3) ((123),Id3,(123)) (3,13,3) ((123),(132),Id3)) (3,3,13) ((12),(12),(13)) (21,21,21) ((123),(123),(132)) (3,3,3) AIMS Mathematics Volume 6, Issue 1, 261–295. 267 Table 2. Representatives of conjugacy classes of the autotopism groups of L4.1and L4.2. L∈LSnΘ∈Atop(L)zΘ L4.1(Id4,Id4,Id4) (14,14,14) (Id4,(12)(34),(12)(34)) (14,22,22) ((12)(34),Id4,(12)(34)) (22,14,22) ((12)(34),(12)(34),Id4) (22,22,14) ((23),(14),(14)) (212,212,212) ((24),(1234),(1234)) (212,4,4) ((1234),(24),(1234)) (4,212,4) ((1234),(1234),(24)) (4,4,212) ((243),(134),(134)) (31,31,31) ((12)(34),(13)(24),(14)(23)) (22,22,22) L4.2(Id4,Id4,Id4) (14,14,14) (Id4,(12)(34),(12)(34)) (14,22,22) ((12)(34),Id4,(12)(34)) (22,14,22) ((12)(34),(12)(34),Id4) (22,22,14) (Id4,(1324),(1324)) (14,4,4) ((1324),Id4,(1324)) (4,14,4) ((1423),(1324),Id4) (4,4,14) ((34),(14)(23),(14)(23)) (212,22,22) ((13)(24),(12),(14)(23)) (22,212,22) ((13)(24),(14)(23),(34)) (22,22,212) ((12),(12),(34)) (212,212,212) ((12)(34),(1423),(1324)) (22,4,4) ((1423),(12)(34),(1324)) (4,22,4) ((1324),(1324),(12)(34)) (4,4,22) Table 3. Representatives of conjugacy classes of the autotopism groups of L5.1and L5.2. L∈LSnΘ∈Atop(L)zΘ L5.1(Id5,Id5,Id5) (15,15,15) (Id5,(12345),(12345)) (15,5,5) ((12345),Id5,(12345)) (5,15,5) ((12345),(15432),Id5) (5,5,15) ((12)(35),(13)(45),(14)(23)) (221,221,221) ((2354),(1243),(1243)) (41,41,41) ((12345),(12345),(13524)) (5,5,5) L5.2(Id5,Id5,Id5) (15,15,15) ((345),(345),(345)) (312,312,312) ((13)(45),(25)(34),(13)(45)) (221,221,221) Example 6. The autotopism group of the Latin square L3described in (2.1) is formed by the following 18 isotopisms of the symmetric group S 3: AIMS Mathematics Volume 6, Issue 1, 261–295. 268 Θ1=(Id3,Id3,Id3)Θ7=((13)(2),(23)(1),(13)(2)) Θ13 =((123),Id3,(123)) Θ2=((12)(3),(12)(3),(13)(2)) Θ8=((23)(1),(12)(3),(12)(3)) Θ14 =((132),Id3,(132)) Θ3=((12)(3),(13)(2),(23)(1)) Θ9=((23)(1),(13)(2),(13)(2)) Θ15 =((123),(132),Id3) Θ4=((12)(3),(23)(1),(12)(3)) Θ10 =((23)(1),(23)(1),(23)(1)) Θ16 =((132),(123),Id3) Θ5=((13)(2),(12)(3),(23)(1)) Θ11 =(Id3,(123),(123)) Θ17 =((123),(123),(132)) Θ6=((13)(2),(13)(2),(12)(3)) Θ12 =((Id3,(132),(132)) Θ18 =((132),(132),(123)) It is partitioned into the following six conjugacy classes: •The trivial autotopism Θ1constitutes as a conjugacy class within itself. •The conjugacy class described by the isotopism Θ2within the autotopism group Atop(L3)is the set {Θ2,Θ3,Θ4,Θ5,Θ6,Θ7,Θ8,Θ9,Θ10}, because Θ3= Θ4Θ2Θ−1 4,Θ4= Θ3Θ2Θ−1 3,Θ5= Θ8Θ2Θ−1 8,Θ6= Θ10Θ2Θ−1 10 , Θ7= Θ9Θ2Θ−1 9,Θ8= Θ5Θ2Θ−1 5,Θ9= Θ7Θ2Θ−1 7,Θ10 = Θ6Θ2Θ−1 6. •The conjugacy class described by Θ11 is the set {Θ11,Θ12}, because Θ12 = Θ2Θ11Θ−1 2. •The conjugacy class described by Θ13 is the set {Θ13,Θ14}, because Θ14 = Θ3Θ13Θ−1 3. •The conjugacy class described by Θ15 is the set {Θ15,Θ16}, because Θ16 = Θ4Θ15Θ−1 4. •The conjugacy class described by Θ17 is the set {Θ17,Θ18}, because Θ18 = Θ2Θ17Θ−1 2. The following result shows that, in the case of dealing with a Latin square that is symmetric by means of a certain paratopism, it is not necessary to study all the representatives of the conjugacy classes of its autotopism group. More specifically, this results enables us to identify certain conjugacy classes whose cycle structures coincide up to permutation among their row, column and symbol components. Lemma 7. Let us consider a Latin square L ∈LSn, a pair of isotopisms Θ1∈Atop(L)and Θ2∈Sn× Sn×Sn, and a permutation π∈S3. If (Lπ)Θ2=L, then there is a one-to-one correspondence between both sets CS Θ1(L)and CS Θ2Θπ 1Θ−1 2(L)so that scsΘ1(L)=scsΘ2Θπ 1Θ−1 2(L)and lcsΘ1(L)=lcsΘ2Θπ 1Θ−1 2(L). Proof. Notice that Θ2Θπ 1Θ−1 2∈Atop(L), because, from Lemma 1, we have that LΘ2Θπ 1Θ−1 2=(Lπ)Θ2Θ2Θπ 1Θ−1 2=(Lπ)Θπ 1Θ2=(LΘ1)πΘ2=(Lπ)Θ2=L. Then, similarly to the proof of Lemma 5, the result follows straightforwardly from the fact that, if P∈CSΘ1(L), then (Pπ)Θ2∈CSΘ2Θπ 1Θ−1 2(L).  Example 8. Let us consider the Latin square L3that is described in (2.1), the pair of isotopisms Θ1=((123),Id3,(123)) ∈Atop(L3)and Θ2=((23),Id3,Id3)∈S3×S3×S3, and the permutation π=(23) ∈S3. In particular, the following two partial Latin squares are Θ1-critical sets of L3. P≡ 1 2 and Q ≡ 1 3 AIMS Mathematics Volume 6, Issue 1, 261–295. 275 Example 18. Let us consider the autotopism Θ = ((123),(123),(132)) of the Latin square L3∈LS3 that is described in (2.1). Notice from the Θ-colouring of L3 123 231 312 that the set OrbΘ(L3)is formed by three principal Θ-orbits. From Proposition 11, we have that lcsΘ(L3)≤3. In this case, it is straightforwardly verified that every Θ-critical set of L3is a partial Latin square formed by only one of its entries. Hence, scsΘ(L3)=lcsΘ(L3)=1. Moreover, the set CSΘ(L3)is distributed into three equivalence classes and thus, |CSΘ(L3)|=3·3=9. Example 19. Let us consider the autotopism Θ = ((12345),(12345),(13524)) of the Latin square L5.1∈LS5that is described in (2.1). Notice from the Θ-colouring of L5.1 1 2 3 4 5 2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4 that the set OrbΘ(L5.1)is formed by five principal Θ-orbits. A simple study of cases enables us to ensure that every entry in the set Ent(L5.1)is Θ-forced by any two entries of a pair of different Θ-orbits. Hence, scsΘ(L5.1)=lcsΘ(L5.1)=2. Moreover, the set CSΘ(L5.1)is distributed into ten equivalence classes and thus, |CSΘ(L5.1)|=10 ·52=250. The following result shows how the existence of exactly one trivial Θ-orbit simplifies the construction of Θ-critical sets. Lemma 20. Let L ∈LSnand let Θ = (α, β, γ)∈Atop(L)be such that λα 1=λβ 1=1. Then, no Θ-critical set of L contains the entry of its trivial Θ-orbit. Proof. Let i,j,k≤nbe the only three positive integers such that `α(i)=`β(j)=`γ(k)=1. This implies that every Latin square that contains the isotopism Θwithin its autotopism group has to contain the entry (i,j,k). Thus, the existence of such an entry in a uniquely Θ-completable partial Latin square does not provide any extra information and can be removed from the latter in order to obtain a Θ-critical set.  In the case of dealing with a non-trivial autotopism Θof a Latin square Lof order n>1, the existence of exactly one trivial Θ-orbit of Limplies the existence of principal and secondary Θ-orbits of L. Let us finish this section by illustrating this fact in the following examples, where we also show the relevance of each kind of Θ-orbit for determining the corresponding Θ-critical sets. Example 21. Let us deal with the autotopism Θ = ((12),(12),(13)) of the Latin square L3∈LS3that is described in (2.1). Notice from the Θ-colouring of L3 123 231 312 AIMS Mathematics Volume 6, Issue 1, 261–295. 276 that the set OrbΘ(L3)is formed by a principal Θ-orbit (OrbΘ((1,1,1))), a row-monotone Θ- orbit (OrbΘ((3,1,3))), a column-mononone Θ-orbit (OrbΘ((1,3,3))), a symbol-monotone Θ-orbit (OrbΘ((1,2,2))) and a trivial Θ-orbit (OrbΘ((3,3,2))). The study of these five Θ-orbits enables us to determine the set of Θ-critical sets of the Latin square L3. Thus, for instance, Lemma 20 implies that no Θ-critical set of L3contains the entry (3,3,2). A simple study of cases based on Θ-forced entries enables us to ensure that every Θ-critical set of L3contains exactly either •one entry belonging to the principal Θ-orbit; or •two entries belonging to two distinct secondary Θ-orbits. Hence, scsΘ(L3)=1<lcsΘ(L3)=2. Moreover, the set CSΘ(L3)is distributed into four equivalence classes having the following arrays as possible representatives. 1 2 3 2 3 3 3 Thus, |CSΘ(L3)|=1·2+3·22=14. Example 22. Let us consider the autotopism Θ = ((243),(134),(134)) of the Latin square L4.1∈LS4 that is described in (2.1). Notice from the Θ-colouring of L4.1 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 that the set OrbΘ(L4.1)is formed by two principal Θ-orbits (OrbΘ((2,3,4)) and OrbΘ((2,4,3))), a rowmonotone Θ-orbit (OrbΘ((1,1,1))), a column-monotone Θ-orbit (OrbΘ((2,2,1))), a symbol-monotone Θ-orbit (OrbΘ((2,1,2))) and a trivial Θ-orbit (OrbΘ((1,2,2))). From Lemma 20, no Θ-critical set of L4.1contains the entry (1,2,2). In addition, every Θ-critical set of L4.1contains exactly a pair of entries of two different non-trivial Θ-orbits. Hence, scsΘ(L4.1)=lcsΘ(L4.1)=2. Moreover, the set CSΘ(L4.1)is distributed into ten equivalence classes and thus, |CSΘ(L4.1)|=10 ·32=90. Example 23. Let us consider the autotopism Θ = ((2354),(1243),(1243)) of the Latin square L5.1∈ LS5that is described in (2.1). Notice from the Θ-colouring of L5.1 1 2 3 4 5 2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4 that the set OrbΘ(L5.1)is formed by three principal Θ-orbits (OrbΘ((2,1,2)),OrbΘ((2,2,3)) and OrbΘ((2,3,4))), a row-monotone Θ-orbit (OrbΘ((1,1,1))), a column-monotone Θ-orbit AIMS Mathematics Volume 6, Issue 1, 261–295. 277 (OrbΘ((2,5,1))), a symbol-monotone Θ-orbit (OrbΘ((2,4,5))) and a trivial Θ-orbit (OrbΘ((1,5,5))). From Lemma 20, no Θ-critical set of L5.1contains the entry (1,5,5). In addition, every Θ-critical set of L5.1must contain at least one principal Θ-orbit, because, the Latin square shown below is another Latin square whose autotopism group contains the isotopism Θand this Latin square also contains the same secondary Θ-orbits as the Latin square L5,1. In order to highlight the differences between this Latin square and the Latin square L5.1, common Θ-orbits have been assigned the same colouring as those used in the Θ-colouring of L5,1, and any differing cells have been left uncoloured. 1 2 3 4 5 3425 1 4 1 532 254 1 3 53124 Nevertheless, it is readily verified that the knowledge of only one principal Θ-orbit will not enough to recover the whole Latin square L5.1. Thus, for instance, the Latin square 3 1 4 2 5 25 3 1 4 142 5 3 5 3 14 2 42531 has Θas an autotopism, but it has in common with L5.1only one principal Θ-orbit and, of course, its trivial Θ-orbit (both of them highlighted with the corresponding colours). Further, the knowledge of only a principal Θ-orbit and other distinct non-trivial Θ-orbit is similarly not enough for determining aΘ-critical set of L5.1. Similarly to the two previous cases, this fact is illustrated by the following three Latin squares, all of them having the isotopism Θin their autotopism group, and containing the principal Θ-orbit OrbΘ((2,1,2)). 12345 2541 3 3 4 251 5 3 124 41532 3 1 4 2 5 2 3 5 4 1 5431 2 42153 1 5 2 3 4 43215 21 3 54 14 5 2 3 35 1 4 2 52 4 31 Now, a simple study of cases enables us to ensure that every Θ-critical sets of L5.1is a partial Latin square of size three, whose entries are taken from •three distinct principal Θ-orbits; •two distinct principal Θ-orbits and the symbol-monotone Θ-orbit; or •a principal Θ-orbit and two distinct secondary Θ-orbits. Hence, scsΘ(L5.1)=lcsΘ(L5.1)=3. Moreover, the set CSΘ(L5.1)is distributed into 13 equivalence classes and thus, |CSΘ(L5.1)|=13 ·43=832. AIMS Mathematics Volume 6, Issue 1, 261–295. 278 4. Overlapping orbits and partial subsquares In this section we describe a new approach for determining critical sets based on Latin square autotopisms. More specifically, we focus on Latin squares of order nthat may be partitioned into subsquares of a same order 1 <m≤ bn 2c. This is the case, for instance, for every partial Latin square of order four, which can always be partitioned into four intercalates (term introduced by Norton [50] to denote any subsquare of order two within a Latin square). Thus, in this instance, there exist exactly three different partitions of the Latin square L4.1into intercalates described in (2.1). The following three squares represent each of these parititions. In each one of the individual squares below, we have coloured the entries of each distinct intercalate in a different colour. 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 1234 2143 3412 4321 12 3 4 21 4 3 34 1 2 43 2 1 Due to their relevance in subsequent results, we designate each of the 12 intercalates its own term I4.1.i, for all i∈ {1,...,12}, so that Ent(I4.1.1)={(1,1,1),(1,2,2),(2,1,2),(2,2,1)},Ent(I4.1.2)={(1,3,3),(1,4,4),(2,3,4),(2,4,3)}, Ent(I4.1.3)={(3,1,3),(3,2,4),(4,1,4),(4,2,3)},Ent(I4.1.4)={(3,3,1),(3,4,2),(4,3,2),(4,4,1)}, Ent(I4.1.5)={(1,1,1),(1,3,3),(3,1,3),(3,3,1)},Ent(I4.1.6)={(1,2,2),(1,4,4),(3,2,4),(3,4,2)}, Ent(I4.1.7)={(2,1,2),(2,3,4),(4,1,4),(4,3,2)},Ent(I4.1.8)={(2,2,1),(2,4,3),(4,2,3),(4,4,1)}, Ent(I4.1.9)={(1,1,1),(1,4,4),(4,1,4),(4,4,1)},Ent(I4.1.10)={(1,2,2),(1,3,3),(4,2,3),(4,3,2)}, Ent(I4.1.11)={(2,1,2),(2,4,3),(3,1,3),(3,4,2)},Ent(I4.1.12)={(2,2,1),(2,3,4),(3,2,4),(3,3,1)}. Similarly, we can look at the partition of the Latin square L4,2into intercalates. The following array highlights each intercalate of the Latin square L4.2described in (2.1) in a distinct colour. 1 2 3 4 2 1 4 3 3 4 2 1 4 3 1 2 Again, due to their relevance in subsequent results, we designate these four intercalates a unique term I4.2.i, for all i∈ {1,2,3,4}, so that Ent(I4.2.1)=Ent(I4.1.1),Ent(I4.2.2)=Ent(I4.1.2), Ent(I4.2.3)=Ent(I4.1.3),Ent(I4.2.4)={(3,3,2),(3,4,1),(4,3,1),(4,4,2)}. The following two results are fundamental for the approach that is described in this section. Let us remind that the shape of a partial Latin square P=(pi j)∈PLSnis the set of cells Sh(L) :={(i,j)∈[n]×[n]: (i,j,pi j)∈Ent(P)}. Shapes of partial Latin squares play an important role in the computation of critical sets, by means of the so-called Latin trades [14,51–54]. Furthermore, us denote the set of symbols appearing in a partial Latin square P∈PLSnby the notation Sym(P). AIMS Mathematics Volume 6, Issue 1, 261–295. 279 Lemma 24. Let P ∈PLSnbe such that |Sym(P)| ≥ 2, and let Θ∈Atop(P). Then, there exists a partial Latin square P0∈PLSn\ {P}such that Sh(P0)=Sh(P),Sym(P0)=Sym(P)and Θ∈Atop(P0). Proof. Let us suppose that Θ = (α, β, γ). If γ(k)=k, for all k∈Sym(P), then it is enough to switch two distinct symbols within all the cells of Pcontaining them. Distinct from P, the resulting partial Latin square has the same shape and the same set of symbols as P, and has Θas an autotopism. Otherwise, if there exists at least one symbol k0∈Sym(P) such that γ(k0),k0, then let us define P0so that Ent(P0)={(i,j, γ−1(k)): (i,j,k)∈Ent(P)}. It can be readily verified that P0is a partial Latin square with the same shape and the same set of symbols as P, with Θas a member of its autotopism group. Moreover, since γis not the trivial permutation, there exists at least one entry of the partial Latin square P0that is not an entry of P. Hence, P0,P. The previous lemma is of particular interest when dealing with certain partial Latin squares using our proposed method. In this regard, we define a partial subsquare of a Latin square L∈LSnas a partial Latin square P∈PLSnsuch that |Sym(P)| ≥ 2 and all the symbols in the set Sym(P) appear in all the non-empty rows and all the non-empty columns of P. Thus, every subsquare of Lhaving order m≥2 is a partial subsquare. Moreover, any two parallel symbol-monotone Θ-orbits of a Latin square having Θas an autotopism is also a partial subsquare. This last case is illustrated in Example 32. The following result shows how to use of partial subsquares in order to obtain information about critical sets based on Latin square autotopisms. Here, we denote, respectively, Row(P) and Col(P) the set of rows and the set of columns of a given partial Latin square L∈PLSn. Proposition 25. Let P and Q be two partial subsquares (not necessarily distinct) of a Latin square L∈LSnsuch that one of the following three conditions hold. •Row(P)=Row(Q); •Col(P)=Col(Q); or •Sym(P)=Sym(Q). In addition, let Θ∈Atop(L)be such that PΘ=Q and QΘ=P. Then, (Ent(P)∪Ent(Q)) ∩OrbΘ(R),∅ for all Θ-critical sets, R, of the Latin square L. Proof. We prove the case Sym(P)=Sym(Q). The other two cases follow by parastrophism. Let P∈PLSnbe such that Ent(P)=Ent(P)∪Ent(Q). From the hypothesis, we have that Θ∈ Atop(P). Then, let P0∈PLSn\ {P}be the partial Latin square that results from Pafter following the constructive proof of Lemma 24. In addition, let L0∈LSn\ {L}be the Latin square that results from Lafter replacing the entries in Pby those ones in P0. It is well-defined because, again from the hypothesis, we can ensure that Ent(P0)=Ent(P0)∪Ent(Q0), where P0and Q0are two partial subsquares of L0such that Sym(P0)=Sym(Q), and whose shapes coincide, respectively, with those ones of Pand Q. The result follows readily from the fact that, if R∈PLSnis a partial Latin square Θ-completable to Lsuch that (Ent(P)∪Ent(Q)) ∩OrbΘ(R)=∅, then it is also Θ-completable to L0. AIMS Mathematics Volume 6, Issue 1, 261–295. 280 Let us illustrate with a series of examples how to make use of Proposition 25 in order to determine critical sets based on autotopisms of the Latin squares L4.1and L4.2, which are described in (2.1). In the first three examples, all the subsquares are preserved by the corresponding autotopisms. That is, the two subsquares indicated in Proposition 25 coincide. Example 26. Let Θ = ((12)(34),(12)(34),Id4)∈Atop(L4.1)∩Atop(L4.2). Respective Θ-colouring of the Latin squares L4.1and L4.2are, for instance, 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 and 1234 2143 3421 4312 . Let i ∈ {1,2}. Notice that the set OrbΘ(L4.i)is formed by eight secondary Θ-orbits. Moreover, the autotopism Θpreserves the four intercalates I4.i.1to I4.i.4. Thus, Proposition 25 implies that every Θ- critical set of the Latin square L4.icontains at least one entry of each one of these four intercalates. Hence, scsΘ(L4.i)≥4. This lower bound is indeed reached. Thus, for instance, the following two partial Latin squares are Θ-critical sets of L4.1. 1 4 3 2 1 4 1 3 In fact, a simple study of cases enables us to ensure that every Θ-critical set P of L4.iis a partial Latin square of size four satisfying the following two assertions. •It contains one entry of each one of the four intercalates I4.i.1to I4.i.4. • |Sym(P)| ≥ 3. Hence, scsΘ(L4.i)=lcsΘ(L4.i)=4. Moreover, the set CSΘ(L4.i)is distributed into 12 equivalence classes. Eight of them contain four distinct symbols, and the other four contain only three distinct symbols. Thus, |CSΘ(L4.i)|=12 ·24=192. Example 27. Let Θ = ((23),(14),(14)) ∈Atop(L4.1). Notice from the Θ-colouring of L4.1 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 that the set OrbΘ(L4.1)is formed by six secondary and four trivial Θ-orbits. Moreover, the autotopism Θpreserves the four intercalates I4.9to I4.12. Thus, Proposition 25 implies that every Θ-critical set of the Latin square L4.1contains at least one entry of each one of these four intercalates. Hence, scsΘ(L4.i)≥4. Again, this lower bound is reached. Thus, for instance, the following four partial Latin AIMS Mathematics Volume 6, Issue 1, 261–295. 281 squares are Θ-critical sets of L4.1. 1 2 2 1 1 2 1 3 1 2 3 1 1 3 4 2 In fact, every partial Latin square of order and size four having an entry of each one of the four intercalates I4.9to I4.12 constitutes a Θ-critical set of L4.1. Thus, no Θ-critical set of size five exists and hence, scsΘ(L4.1)=lcsΘ(L4.1)=4. Moreover, the set CSΘ(L4.1)is distributed into 32 equivalence classes and |CSΘ(L4.1)|=44=256. Example 28. Let Θ = ((12),(12),(34)) ∈Atop(L4.2). Notice from the Θ-colouring of L4.2 1 2 3 4 2 1 4 3 3 4 2 1 4 3 1 2 that the set OrbΘ(L4.2)is formed by six secondary and four trivial Θ-orbits. Moreover, the autotopism Θpreserves the four intercalates I4.1to I4.4. Similarly to Example 27, we can ensure that scsΘ(L4.2)= lcsΘ(L4.2)=4. Moreover, the set CSΘ(L4.2)is distributed into 32 equivalence classes and |CSΘ(L4.2)|= 44=256. Now, let us illustrate with a series of examples the case in which the two subsquares indicated in Proposition 25 are distinct. Example 29. Let us consider the autotopism Θ = ((1324),(1324),(12)(34)) of the Latin square L4.2. Notice from the Θ-colouring of L4.2 1 2 3 4 2 1 4 3 3 4 2 1 4 3 1 2 that the set OrbΘ(L4.2)is formed by four non-monotone Θ-orbits. Moreover, the autotopism Θswitches the intercalates I4.1and I4.4, as well as the intercalates I4.2and I4.3. Thus, Proposition 25 implies that every Θ-critical set of the Latin square L4.2contains at least one entry of Ent(I4.1)∪Ent(I4.4), and one entry of Ent(I4.2)∪Ent(I4.3). It is readily verified that every Θ-critical set of L4.2is indeed of this form. Hence, scsΘ(L4.2)=lcsΘ(L4.2)=2. Moreover, the set CSΘ(L4.2)is distributed into four equivalence classes and |CSΘ(L4.2)|=4·42=64. Example 30. Let us consider the autotopism Θ = ((12)(34),(13)(24),(14)(23)) of the Latin square L4.1. Notice from the Θ-colouring of L4.1 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 AIMS Mathematics Volume 6, Issue 1, 261–295. 282 that the set OrbΘ(L4.1)is formed by eight principal Θ-orbits. Moreover, the autotopism Θpreserves the partial subsquares P≡ 1 4 1 4 4 1 4 1 and Q ≡ 2 3 2 3 3 2 3 2 . Proposition 25 implies that every Θ-critical set of the Latin square L4.1contains an entry of each one of these two partial subsquares. As a consequence, scsΘ(L4.1)≥2. Moreover, there are 64 distinct candidates for Θ-critical sets of L4.1having size two. If we focus on those ones containing the entry (1,1,1) and we keep in mind that every Θ-orbit is uniquely determined by any of its entries, then we can restrict the study of all these candidates, for instance, to the four partial Latin squares 1 2 1 3 1 3 and 1 2 . According to our reasoning, each one of these four partial Latin squares represents 16 distinct candidates of the 64 mentioned ones. After applying the Θ-forcing map ΦΘto each one of these four arrays, we obtain, respectively, the partial Latin squares 1 2 3 4 2 1 4 3 1 3 2 4 1 4 2 3 and 1 3 2 4 3 1 4 2 . None of them is a Θ-critical set of the Latin square L4.1. As a consequence, scsΘ(L4.1)≥3. This lower bound is indeed reached. Thus, for instance, the following partial Latin square is a Θ-critical set of L4.1. 1 2 3 Now, in order to determine all the Θ-critical sets of L4.1, notice also that the autotopism Θswitches the six pairs of intercalates I4.1.1with I4.1.2,I4.1.3with I4.1.4,I4.1.5with I4.1.7, I4.1.6with I4.1.8,I4.1.9with I4.1.12 and I4.1.10 with I4.1.11. Both intercalates from each of these six pairs either have the same set of rows, the same set of columns or the same set of symbols. Thus, from our previous reasoning, together with Propositions 11 and 25, we may ensure that every Θ-critical set of the Latin square L4.1satisfies the following assertions. AIMS Mathematics Volume 6, Issue 1, 261–295. 283 •It contains at least three entries. •It contains at least one entry of each one of the two partial subsquares P and Q. •It contains at least one entry of each one of the six pairs of intercalates that we have previously indicated. •It does not contain two entries in the same Θ-orbit. A simple study of cases enables us to affirm that every partial Latin square Θ-completable to L4.1, having size three and satisfying the last three assertions, is indeed a Θ-critical set of L4.1. In order to illustrate this fact, we highlight with the symbol x those cells corresponding to entries in L4.1that may be considered as the third one to be added to each one of the four partial Latin squares of size two of our initial study of cases. 1 2 x x x x x x x x 1 3 x x x x 1x x x x x x x x x x3x x and 1x x x x x x x2x No other Θ-critical sets exists and hence, scsΘ(L4.1)=lcsΘ(L4.1)=3. Moreover, the set CSΘ(L4.1)is distributed into 32 equivalence classes and |CSΘ(L4.1)|=32 ·23=256. Example 31. Let us consider the autotopism Θ = ((13)(24),(14)(23),(34)) of the Latin square L4.2∈ LS4that is described in (2.1). Notice from the Θ-colouring of L4.2 1 2 3 4 2 1 4 3 3 4 2 1 4 3 1 2 that the set OrbΘ(L4.2)is formed by four principal Θ-orbits and four non-parallel symbol-monotone Θ- orbits. Moreover, the autotopism Θswitches both intercalates I4.1and I4.4, and also both intercalates I4.2and I4.3. Thus, Proposition 25 implies that every Θ-critical set of the Latin square L4.2contains at least one entry of each mentioned pair of intercalates, and hence, scsΘ(L4.2)≥2. Similarly to the reasoning followed in Example 30, the study of the 64 candidates for size 2 Θ-critical sets of L4.2may be focused on the partial Latin squares pertaining to the triple (1,1;1) (each one of them representing to 16 distinct candidates) 1 3 1 4 1 4and 1 3. After applying the Θ-forcing map ΦΘto each one of these four arrays, we obtain, respectively, the partial Latin squares 1 2 3 4 3 4 2 1 1 4 3 1 1 1 4 1 3 1 and 1 4 2 3 3 1 4 2 . AIMS Mathematics Volume 6, Issue 1, 261–295. 284 None of the above constitute a Θ-critical set of the Latin square L4.2. As a consequence, scsΘ(L4.2)≥3. This lower bound is indeed reached. One example of a size 3 Θ-critical set of L4.2is given by the following partial Latin square. 1 3 2 Let us highlight with the symbol x those cells corresponding to entries in L4.2that may be considered as a third one to be added to each one of the four partial Latin squares of size two of our study of cases in order to determine a Θ-critical set of L4.2having size three. 1 3 x x x x x x x x 1 4 x x 1x x x x4x xxx x x and 1x x x x 3 x x x x . No other Θ-critical sets exists and hence, scsΘ(L4.2)=lcsΘ(L4.2)=3. Moreover, the set CSΘ(L4.2)is distributed into 28 equivalence classes and |CSΘ(L4.2)|=28 ·23=224. In order to finish the study of cases described in Table 4, let us focus now on those autotopisms of the Latin squares L5.1and L5.2that have not still been dealt with. Example 32. Let us consider the autotopism Θ = ((345),(345),(345)) of the Latin square L5.2∈LS5. Notice from the Θ-colouring of L5.2 1 2 3 4 5 2 1 4 5 3 3 4 5 1 2 4 5 2 3 1 5 3 1 2 4 that the set OrbΘ(L5.2)is formed by •the principal Θ-orbit OrbΘ((3,3,5)); •the two parallel row-monotone Θ-orbits OrbΘ((1,3,3)) and OrbΘ((2,3,4)); •the two parallel column-monotone Θ-orbits OrbΘ((3,1,3)) and OrbΘ((3,2,4)); •the two parallel symbol-monotone Θ-orbits OrbΘ((3,4,1)) and OrbΘ((3,5,2)); AIMS Mathematics Volume 6, Issue 1, 261–295. 291 5. Conclusion and further works In this paper, we have dealt with the problem of determining Θ-critical sets of Latin squares containing a given isotopism Θin their autotopism groups. We have proved in Section 2 that the set of such Θ-critical sets only depends on both the main class of the Latin square under consideration and the cycle structure of the autotopism Θ. In Sections 3 and 4, we have respectively introduced the notions of Θ-orbit and partial subsquare, which play a relevant role in the computation of Θ-critical sets. We have made use of both notions in determining a constructive and illustrative way of finding all the critical sets based on non-trivial autotopisms of Latin squares of order up to five. In this regard, Table 4 constitutes the main contribution of this paper, together with the explicit enumeration of equivalence classes of critical sets, which is available in [49]. In order to deal with higher orders, a much deeper study (combining theoretical and computational techniques) is required. It is proposed as further work. Furthermore, let us propose some open questions for further work on this subject. Question 36. Let P ∈PLSnand Θ∈Atop(L). What is the computational complexity of deciding whether the partial Latin square P is Θ-completable? Question 37. Does a Θ-critical set of size m exist for every m such that, scsΘ(L)≤m≤lcsΘ(L), for every L ∈LSnand Θ∈Atop(L)? Question 38. Let Θ∈Sn×Sn×Sn. We denote the smallest and largest sizes of Θ-critical sets of any given Latin square of order n by scsΘ(n)and lcsΘ(n)respectively. In a similar way to the classic case, is it possible to find some lower and upper bounds values for both scsΘ(n)and lcsΘ(n)depending on the order n? Question 39. Except for Example 17, in which two non-monotone Θ-orbits appear, all secondary Θ- orbits shown in the rest of examples of this paper are row-, column- or symbol-monotone. Nevertheless, the existence of non-monotone Θ-orbits is more common amongst Latin squares of higher orders. Thus, for instance, let us consider the isotopism Θ = ((123456),(123)(456),(14)(25)(36)) ∈S6×S6×S6. It constitutes as an autotopism of the following Latin square, note the Θ-colouring associated with this autotopism is also shown in this diagram. 123456 645312 231564 456123 312645 564231 The set of entries of this Latin square under this autotopism are partitioned into six non-monotone Θ-orbits, each one of them formed by six entries that are associated to only three columns and two symbols. In this regard, they differ from the two mentioned non-monotone Θ-orbits in Example 17, whose respective entries are associated to distinct rows and columns. Thus, the question is, how many types of non-monotone orbits based on Latin square autotopisms exist and what is the role played by each one of them in the construction of the corresponding critical sets? AIMS Mathematics Volume 6, Issue 1, 261–295. 292 Question 40. In Theorem 16, we have indicated a pair of formulas concerning the values scsΘ(L), lcsΘ(L)and |CSΘ(L)|, for any autotopism Θ∈Sn×Sn×Snwith the cycle structure (n,n,1n). Is it possible to find this kind of general formula for other cycle structures? Question 41. Let P ∈PLSnbe a Θ-critical set of a given Latin square. We say that P is Θ-strong if its set of entries can be filled by making use of the Θ-forcing map ΦΘ. It generalizes the concept of strong critical set [55] described in the introductory section, which arises from our definition when Θis the trivial autotopism. An illustrative case ensuring the existence of Θ-critical sets that are not Θ-strong, for a non-trivial autotopism Θ, appears in Example 35. More specifically, it is readily verified that every Θ-critical set of size three in such an example is not Θ-strong. Thus, the question is, what about the existence of non-Θ-strong Θ-critical sets for any given autotopism Θ? Question 42. In Examples 34 and 35, we have described a procedure from which we have obtained that the smallest Θ-critical sets are formed by three entries, each one of them corresponding to a distinct candidate for Θ-critical set of size two. May this procedure (and, more specifically, this property) be generalized to some other autotopisms? Question 43. It is known [25] that every Latin square of order n has at most nO(log k)subsquares of order k. What about partial subsquares? Acknowledgments Falc´ on’s work is partially supported by the research project FQM-016 from Junta de Andaluc´ ıa. Conflict of interest The authors declare no conflict of interest. References 1. C. J. Colbourn, M. J. Colbourn, D. R. Stinson, The computational complexity of recognizing critical sets, Lect. Notes Math.,1073 (1984), 248–253. 2. C. J. Colbourn, The complexity of completing partial Latin squares, Discrete Appl. Math.,8(1984), 25–30. 3. J. Nelder, Critical sets in Latin squares. In: CSIRO Division of Math. and Stats, Newsletter, 1977. 4. J. Cooper, D. Donovan, J. Seberry, Latin squares and critical sets of minimal size, Australas. J. Combin.,4(1991), 113–120. 5. J. A. Bate, G. H. J. van Rees, The size of the smallest strong critical set in a Latin square, Ars Comb.,53 (1999), 73–83. 6. N. Cavenagh, D. Donovan, A. Khodkar, On the spectrum of critical sets in back circulant Latin squares, Ars Combin.,82 (2007), 287–319. 7. B. Smetaniuk, On the minimal critical set of a Latin square, Utilitas Math.,16 (1979), 97–100. 8. D. Curran, G. H. J. Van Rees, Critical sets in Latin squares. In: Proceedings of the Eighth Manitoba Conference on Numerical Mathematics and Computing, Congress. Numer., XXII, 1979, 165–168. AIMS Mathematics Volume 6, Issue 1, 261–295. 293 9. D. R. Stinson, G. H. J. Van Rees, Some large critical sets, Congr. Numer.,34 (1982), 441–456. 10. A. P. Street, Defining sets for t-designs and critical sets for Latin squares, New Zealand J. Math., 21 (1992), 133–144. 11. A. D. Keedwell, Critical sets for Latin squares, graphs and block designs: a survey, Congr. Numer., 113 (1996), 231–245. 12. A. D. Keedwell, Critical sets in Latin squares: An Intriguing Problem, Math. Gaz.,85 (2001), 239–244. 13. A. D. Keedwell, Critical sets in Latin squares and related matters: an update, Util. Math.,65 (2004), 97–131. 14. N. J. Cavenagh, The theory and application of Latin bitrades: a survey, Math. Slovaca,58 (2008), 691–718. 15. P. Adams, R. Bean, A. Khodkar, A census of critical sets in the Latin squares of order at most six, Ars Combin.,68 (2003), 203–223. 16. D. Donovan, A. Howse, Critical sets for Latin squares of order 7, J. Combin. Math. Combin. Comput.,28 (1998), 113–123. 17. A. Hulpke, P. Kaski, P. R. J. ¨ Ostergård, The number of Latin squares of order 11, J. Math. Comp., 80 (2011), 1197–1219. 18. G. Kolesova, C. W. H. Lam, L. Thiel, On the number of 8 ×8 Latin squares, J. Combin. Theory Ser. A,54 (1990), 143–148. 19. B. D. McKay, A. Meynert, W. Myrvold, Small Latin squares, quasigroups, and loops, J. Combin. Des.,15 (2007), 98–119. 20. R. M. Falc´ on, The set of autotopisms of partial Latin squares, Discrete Math.,313 (2013), 1150– 1161. 21. R. M. Falc´ on, Enumeration and classification of self-orthogonal partial Latin rectangles by using the polynomial method, European J. Combin.,48 (2015), 215–223. 22. R. M. Falc´ on, R. J. Stones, Classifying partial Latin rectangles, Electron. Notes Discrete Math., 49 (2015), 765–771. 23. R. M. Falc´ on, O. J. Falc´ on, J. N´ u˜ nez, Counting and enumerating partial Latin rectangles by means of computer algebra systems and CSP solvers, Math. Methods Appl. Sci.,41 (2018), 7236–7262. 24. R. M. Falc´ on, R. J. Stones, Enumerating partial Latin rectangles, Electron. J. Combin.,27 (2020), ]P2.47. 25. J. Browning, D. S. Stones, I. Wanless, Bounds on the number of autotopisms and subsquares of a Latin square, Combinatorica,33 (2013), 11–22. 26. R. M. Falc´ on, R. J. Stones, Partial Latin rectangle graphs and autoparatopism groups of partial Latin rectangles with trivial autotopism groups, Discrete Math.,340 (2017), 1242–1260. 27. D. Kotlar, Parity types, cycle structures and autotopisms of Latin squares, Electron. J. Combin.,19 (2012), 10. 28. D. S. Stones, Symmetries of partial Latin squares, European J. Combin.,34 (2013), 1092–1107. AIMS Mathematics Volume 6, Issue 1, 261–295. 294 29. R. M. Falc´ on, V. ´ Alvarez, F. Gudiel, A computational algebraic geometry approach to analyze pseudo-random sequences based on Latin squares, Adv. Comput. Math.,45 (2019), 1769–1792. 30. E. Danan, R. M. Falc´ on, D. Kotlar, T. G. Marbach, R. J. Stones, Refining invariants for computing autotopism groups of partial Latin rectangles, Discrete Math.,343 (2020), 1–21. 31. R. M. Falc´ on, Using a CAS/DGS to analyze computationally the configuration of planar bar linkage mechanisms based on partial Latin squares, Math. Comp. Sc.,14 (2020), 375–389. 32. D. Kotlar, Computing the autotopy group of a Latin square by cycle structure, Discrete Math.,331 (2014), 74–82. 33. R. Stones, R. M. Falc´ on, D. Kotlar, T. G. Marbach, Computing autotopism groups of partial Latin rectangles: a pilot study, Comput. Math. Meth., (2020), e1094. 34. R. Stones, R. M. Falc´ on, D. Kotlar, T. G. Marbach, Computing autotopism groups of partial Latin rectangles, J. Exp. Algorithmics,25 (2020), 1–39. 35. R. J. Stones, M. Su, X. Liu, G. Wang, S. Lin, A Latin square autotopism secret sharing scheme, Des. Codes Cryptogr.,35 (2015), 1–16 36. M. Yan, J. Feng, T. G. Marbach, R. J. Stones, G. Wang, X. Liu, Gecko: A resilient dispersal scheme for multi-cloud storage, IEEE Access,7(2019), 77387–77397. 37. L. Yi, R. J. Stones, G. Wang, Two-erasure codes from 3-plexes. In: Network and Parallel Computing. Springer International Publishing, Cham, 2019, 264–276. 38. R. J. Stones, K-plex 2-erasure codes and Blackburn partial Latin squares, IEEE Trans. Inf. Theory, 66 (2020), 3704–3713. 39. R. M. Falc´ on, O. J. Falc´ on, J. N´ u˜ nez, A historical perspective of the theory of isotopisms, Symmetry,10 (2018), 322. 40. R. M. Falc´ on, 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, Universit´ e J. Fourier, Grenoble, France, 2006, 213–230. 41. R. M. Falc´ on, Study of critical sets in Latin squares by using the autotopism group, Electron. Notes Discrete Math.,29 (2007), 503–507. 42. S. D. Andres, R. M. Falc´ on, Autotopism stabilized colouring games on rook’s graphs, Discrete Appl. Math.,266 (2019), 200–212. 43. N. J. Cavenagh, D. S. Stones, Near-automorphisms of Latin squares, J. Combin. Des.,19 (2011), 365–377. 44. M. Gr¨ uttm¨ uller, Completing partial Latin squares with two cyclically generated prescribed diagonals, J. Combin. Theory Ser. A,103 (2003), 349–362. 45. M. Gr¨ uttm¨ uller, Completing partial Latin squares with prescribed diagonals, Discrete Appl. Math., 138 (2004), 89–97. 46. R. M. Falc´ on, J. Mart´ ın-Morales, Gr¨ obner bases and the number of Latin squares related to autotopisms of order up to 7, J. Symb. Comput.,42 (2007), 1142–1154. 47. D. S. Stones, P. Vojtˇ echovsk´ y, I. M. Wanless, Cycle structure of autotopisms of quasigroups and Latin squares, J. Combin. Des.,20 (2012), 227–263. AIMS Mathematics Volume 6, Issue 1, 261–295. 295 48. W. Decker, G. M. Greuel, G. Pfister, et al., Singular 4-1-3 A computer algebra system for polynomial computations, 2020. Available from: http://www.singular.uni-kl.de. 49. R. M. Falc´ on, L. Johnson, S. Perkins, Equivalence classes of critical sets based on non-trivial autotopisms of Latin squares, Mendeley Data, v1, 2020. Available from: http://dx.doi.org/10.17632/fkm575299m.1. 50. H. A. Norton, The 7 ×7 squares, Ann. Eugenics,9(1939), 269–307. 51. A. Dr´ apal, T. Kepka, Exchangeable groupoids I, Acta Univ. Carolin.—Math. Phys.,24 (1983), 57–72. 52. D. Donovan, A. Howse, P. Adams, A discussion of Latin interchanges, J. Combin. Math. Combin. Comput.,23 (1997), 161–182. 53. N. Cavenagh, D. Donovan, A. Dr´ apal, Constructing and deconstructing Latin trades, Discrete Math.,284 (2004), 97–105. 54. N. Cavenagh, D. Donovan, 3-Homogeneous Latin trades, Discrete Math.,300 (2005), 57–70. 55. D. Donovan, J. A. Cooper, D. J. Nott, J. Seberry, Latin squares: Critical sets and their lower bounds, Ars Combin.,39 (1995), 33–48. A. Glossary of symbols Atop(P) Autotopism group of a partial Latin square P. CSΘ(L) Set of Θ-critical sets of a Latin square L. Ent(P) Set of entries of a partial Latin square P. ΦΘΘ-forcing map that establishes how to add Θ-forced entries to a Θ-compatible partial Latin square. lcsΘ(L) Size of the largest Θ-critical set of a Latin square L. LSnSet of Latin squares of order n. `π(i) Length of the cycle Cin the unique decomposition of a permutation πinto disjoint cycles such that π(i)=C(i). λl(π) Number of cycles of lenght lin the unique decomposition of a permutation πas a product of disjoint cycles. [n] The set {1,...,n}. PLSnSet of partial Latin squares of order n. scsΘ(L) Size of the smallest Θ-critical set of a Latin square L. SnSymmetric group on the set [n]. zπCycle structure of a permutation π. zΘCycle structure of an isotopism Θ. c 2021 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0) AIMS Mathematics Volume 6, Issue 1, 261–295. View publication statsView publication stats