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

1.   Introduction

A partial Latin square of order $n$ is an $n\times n$ array whose cells are either empty or filled by one element of a set of $n$ distinct 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 $n^2$ (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 $\mathrm{PLS}_n$ and $\mathrm{LS}_n$ respectively denote the set of partial Latin squares of order $n$ and its subset of Latin squares of the same order, both of them having the set $[n]: = \{1, \ldots, n\}$ as sets of symbols. Every partial Latin square $P = (p_{ij})\in \mathrm{PLS}_n$ is uniquely determined by its set of entries

A completion of $P$ is any Latin square $L\in\mathrm{LS}_n$ such that $\mathrm{Ent}(P)\subseteq \mathrm{Ent}(L)$. Then, it is said that $P$ is completable to $L$. If there exists precisely one such a Latin square $L$, then $P$ is 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].

In 1977, John Ashworth Nelder ^[3] termed critical set of a Latin square $L\in\mathrm{LS}_n$ to any partial Latin square $P\in\mathrm{PLS}_n$ that is uniquely completable to $L$ and such that, for every $P'\in \mathrm{PLS}_n$ satisfying that $\mathrm{Ent}(P')\subset \mathrm{Ent}(P)$, there exists a distinct Latin square $L'\in\mathrm{LS}_n\setminus\{L\}$ such that $\mathrm{Ent}(P')\subset \mathrm{Ent}(L')$. It is said to be minimal if there does not exist any critical set of $L$ of 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\in\mathrm{PLS}_n$ is a triple $(i, j, k)\in [n]\times [n]\times [n]$ such that the cell $(i, j)$ is the only empty one either in the $i^{\mathrm{th}}$ row or the $j^{\mathrm{th}}$ 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, $\mathrm{scs}(n)$ and $\mathrm{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 $\mathrm{scs}(2n)\leq \lfloor n^2/4\rfloor$, 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 $\mathrm{scs}(n)$, for all $n\leq 5$, together with some bounds for both sizes $\mathrm{scs}(n)$ and $\mathrm{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,12,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 $S_n$ denotes the symmetric group on the set $[n]$, then every triple $\Theta = (\alpha, \beta, \gamma)\in S_ n\times S_n\times S_n$ is called an isotopism from a partial Latin square $P = (p_{ij})\in\mathrm{PLS}_n$ to its isotopic partial Latin square $P^{\Theta}\in\mathrm{PLS}_n$, where

In other words, the partial Latin square $P^{\Theta}$ arises from $P$ after permuting its rows, columns and symbols respectively by $\alpha$, $\beta$ and $\gamma$. Further, if $\pi\in S_3$, then the partial Latin square $P^{\pi}\in\mathrm{PLS}_n$, where

is said to be a conjugate of $P$, and the permutation $\pi$ is called a parastrophism from $P$ to $P^{\pi}$. In other words, the partial Latin square $P^{\pi}$ arises from $P$ after 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,18,19] for order up to $11$, and that of partial Latin squares is known ^{[20,21,22,23,24]} for order up to six. Further, if $P^{\Theta} = P$, then the triple $\Theta$ is called an autotopism of the partial Latin square $P$. It is known ^[25] that a Latin square of order $n$ has at most $n^{O(\log n)}$ autotopisms.

The set $\mathrm{Atop}(P)$ of all autotopisms of a partial Latin square $P$ constitutes 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,27,28]}, with special emphasis on the study of invariants that facilitate their computation ^{[29,30,31,32,33,34]}, and its possible applications in cryptography and coding theory ^{[35,36,37,38]}. For a recent survey on the theory of isotopisms, we refer the reader to ^[39].

In the early 2000's, the concept of completability was generalised ^[40,41] to that of $\mathfrak{F}$-completability, where $\mathfrak{F}$ is any given set of Latin square isotopisms. More specifically, a partial Latin square $P\in\mathrm{PLS}_n$ is called $\mathfrak{F}$-completable if there exists a completion $L\in\mathrm{LS}_n$ of the former such that $\Theta\in\mathrm{Atop}(L)$, for all $\Theta\in\mathfrak{F}$. If such a Latin square is unique, then $P$ is said to be uniquely $\mathfrak{F}$-completable. Moreover, it is called an $\mathfrak{F}$-critical set of $L$ if this last property does not hold for any partial Latin square $Q$ such that $\mathrm{Ent}(Q)\subset \mathrm{Ent}(P)$. As such, these concepts generalise the classical ones, which arise when the set $\mathfrak{F}$ is formed only by the trivial isotopism. More generally, if $\mathfrak{F}$ is formed by only one isotopism $\Theta = (\alpha, \beta, \gamma)\in S_n\times S_n\times S_n$, then the notion of being (uniquely) $\Theta$-completable and that one of being a $\Theta$-critical set arise analogously ^[20]. In particular, if $P$ is $\Theta$-completable, then it is also $\Theta$-compatible ^[42], that is, every entry $(i, j, k)\in\mathrm{Ent}(P)$ satisfies that, for each positive integer $m$, either the cell $(\alpha^m(i), \beta^m(j))$ is empty, or $(\alpha^m(i), \beta^m(j), \gamma^m(k))\in\mathrm{Ent}(P)$. Some particular cases of $\Theta$-completability have already been considered in ^[43,44,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 $\Theta$-orbits of a Latin square, where $\Theta$ is an isotopism in its autotopism group. We show how this notion can be used for determining the possible sizes of the corresponding $\Theta$-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 $\Theta$-orbits and partial subsquares within a given Latin square may be used to determine its $\Theta$-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 $\Theta = (\delta_1, \delta_2, \delta_3)\in S_n\times S_n\times S_n$ and a permutation $\pi\in S_3$. Let us define the isotopism

Then, $(P^{\pi})^{\Theta^{\pi}} = (P^{\Theta})^{\pi}$, for all partial Latin square $P\in\mathrm{PLS}_n$,

Proof. Suppose $\Theta = (\delta_1, \delta_2, \delta_3)$. The result follows from the fact that

Example 2. Let us consider the Latin square of order four

and its conjugate by the permutation $\pi = (123)\in S_3$. That is,

Now, let us consider the isotopism $\Theta = ((12)(34), (1234), (123)(4))\in S_4\times S_4\times S_4$. Then,

and

Hence,

Let $L\in\mathrm{LS}_n$ and $\Theta\in\mathrm{Atop}(L)$. From now on, let $\mathrm{CS}_{\Theta}(L)$ denote the set of $\Theta$-critical sets of the Latin square $L$. Furthermore, let $\mathrm{scs}_{\Theta}(L)$ and $\mathrm{lcs}_{\Theta}(L)$ respectively denote the sizes of the smallest and the largest $\Theta$-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 $P_1, P_2\in\mathrm{PLS}_n$ be two paratopic partial Latin squares. Thus, there exist a permutation $\pi\in S_3$ and an isotopism $\Theta\in S_n\times S_n\times S_n$ such that $P_2 = \left((P_1)^{\pi}\right)^{\Theta}$. Then, the result follows straightforwardly from Lemma 1. More specifically, if $\Theta_1\in \mathrm{Atop}(P_1)$, then $\Theta\Theta_1^{\pi}\Theta^{-1}\in\mathrm{Atop}(P_2)$.

Proposition 4. Let $L_1, L_2\in\mathrm{LS}_n$ be two paratopic Latin squares such that $L_2 = \left((L_1)^{\pi}\right)^{\Theta}$, for some permutation $\pi\in S_3$ and some isotopism $\Theta\in S_n\times S_n\times S_n$. Let $\Theta_1\in\mathrm{Atop}(L_1)$ and let $\Theta_2 = \Theta\Theta_1^{\pi}\Theta^{-1}\in\mathrm{Atop}(L_2)$. Then, there is a one-to-one correspondence between both sets $\mathrm{CS}_{\Theta_1}(L_1)$ and $\mathrm{CS}_{\Theta_2}(L_2)$ so that $\mathrm{scs}_{\Theta_1}(L_1) = \mathrm{scs}_{\Theta_2}(L_2)$ and $\mathrm{lcs}_{\Theta_1}(L_1) = \mathrm{lcs}_{\Theta_2}(L_2)$.

Proof. The result follows straightforwardly from the proof of Lemma 3. More specifically, if $P\in\mathrm{CS}_{\Theta_1}(L_1)$, then $(P^{\pi})^{\Theta}\in\mathrm{CS}_{\Theta_2}(L_2)$.

From the previous results, our study may focus on the following representatives of main classes of Latin squares of order $2\leq n\leq 5$. (Notice that the case $n = 1$ is trivial.)

In practice, it is not necessary to study the whole autotopism group of a given Latin square $L$ in order to compute the sizes of its $\Theta$-critical sets, for all $\Theta\in\mathrm{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 $a$ and $b$ of a given group $G$ are said to be conjugate if and only if there exists a third element $c\in G$ such 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 $\Theta_1$ and $\Theta_2$ be two conjugate autotopisms within the autotopism group of a Latin square $L\in\mathrm{LS}_n$. Then, there is a one-to-one correspondence between both sets $\mathrm{CS}_{\Theta_1}(L)$ and $\mathrm{CS}_{\Theta_2}(L)$ so that $\mathrm{scs}_{\Theta_1}(L) = \mathrm{scs}_{\Theta_2}(L)$ and $\mathrm{lcs}_{\Theta_1}(L) = \mathrm{lcs}_{\Theta_2}(L)$.

Proof. Let $\Theta = (\alpha, \beta, \gamma)\in \mathrm{Atop}(L)$ be such that $\Theta_2 = \Theta\Theta_1\Theta^{-1}$. In order to prove the result, it is enough to describe a one-to-one correspondence between both sets $\mathrm{CS}_{\Theta_1}(L)$ and $\mathrm{CS}_{\Theta_2}(L)$. To this end, if $P\in\mathrm{CS}_{\Theta_1}(L)$, let us see that $P^{\Theta}\in\mathrm{CS}_{\Theta_2}(L)$.

Firstly, notice that $\mathrm{Ent}(P)\subseteq \mathrm{Ent}(L)$, because $P\in\mathrm{CS}_{\Theta_1}(L)$. As a consequence, $\mathrm{Ent}(P^{\Theta})\subseteq \mathrm{Ent}(L^{\Theta}) = \mathrm{Ent}(L)$, because $\Theta\in\mathrm{Atop}(L)$.

Now, suppose the existence of an entry $e = (i, j, k)\in\mathrm{Ent}(P)$ and a Latin square $L'\in \mathrm{LS}_n\setminus\{L\}$ such that $\mathrm{Ent}(P^{\Theta})\setminus\{e\}\subset\mathrm{Ent}(L')$ and $\Theta_2\in\mathrm{Atop}(L')$. Let $P^{\Theta}_{\{e\}}$ denote the partial Latin square of order $n$ that results after removing the entry $e$ from $P^{\Theta}$. Then, $\left(P^{\Theta}_{\{e\}}\right)^{\Theta^{-1}}$ is the partial Latin square of order $n$ that results after removing the entry $\Theta^{-1}(e) = (\alpha^{-1}(i), \beta^{-1}(j), \gamma^{-1}(k))$ from $P$. Hence, $\mathrm{Ent}(P)\setminus\{\Theta^{-1}(e)\}\subset \mathrm{Ent}\left({L'}^{\Theta^{-1}}\right)$. Moreover, $\Theta_1\in\mathrm{Atop}\left({L'}^{\Theta^{-1}}\right)$, because

Furthermore, notice that ${L'}^{\Theta^{-1}}\neq L$. Otherwise, it would be $L' = L^{\Theta} = L$, which is not possible. Thus, $P\not\in \mathrm{CS}_{\Theta_1}(L)$, which is a contradiction. As a consequence, $P^{\Theta}\in\mathrm{CS}_{\Theta_2}(L)$.

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 $\Theta = (\alpha, \beta, \gamma)\in S_n\times S_n\times S_n$ is defined as the triple $z_{\Theta}: = (z_{\alpha}, z_{\beta}, z_{\gamma})$ formed by the respective cycle structures of the permutations $\alpha$, $\beta$ and $\gamma$. Remind also to this end that the cycle structure of a permutation $\pi\in S_n$ is the expression $z_{\pi}: = n^{\lambda_n^{\pi}}\ldots n^{\lambda_1^{\pi}}$, where $\lambda_l(\pi)$ denotes the number of cycles of length $l$ in the unique decomposition of $\pi$ as a product of disjoint cycles. In practice, it is written only those factors for which $\lambda_l^{\pi} > 0$. Moreover, each factor of the form $l^1$ is replaced by $l$. Thus, for instance, the cycle structure of the permutation $(123)(45)(67)(8)\in S_8$ is $32^21$, and that one of the isotopism $((123)(4), (12)(34), (1234))\in S_4\times S_4\times S_4$ is the triple $(31, 2^2, 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 $n$ is currently known ^[20,47] for all $n\leq 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 $\mathrm{Id}_n$ the trivial permutation in the symmetric group $S_n$. 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.

Example 6. The autotopism group of the Latin square $L_3$ described in (2.1) is formed by the following 18 isotopisms of the symmetric group $S_3$:

$\begin{array}{l} \Theta_1 = (\mathrm{Id}_3, \mathrm{Id}_3, \mathrm{Id}_3) && \Theta_7 = ((13)(2), (23)(1), (13)(2)) && \Theta_{13} = ((123), \mathrm{Id}_3, (123)) \\ \Theta_2 = ((12)(3), (12)(3), (13)(2)) && \Theta_8 = ((23)(1), (12)(3), (12)(3)) && \Theta_{14} = ((132), \mathrm{Id}_3, (132)) \\ \Theta_3 = ((12)(3), (13)(2), (23)(1)) && \Theta_9 = ((23)(1), (13)(2), (13)(2)) && \Theta_{15} = ((123), (132), \mathrm{Id}_3) \\ \Theta_4 = ((12)(3), (23)(1), (12)(3)) && \Theta_{10} = ((23)(1), (23)(1), (23)(1)) && \Theta_{16} = ((132), (123), \mathrm{Id}_3) \\ \Theta_5 = ((13)(2), (12)(3), (23)(1)) && \Theta_{11} = (\mathrm{Id}_3, (123), (123)) && \Theta_{17} = ((123), (123), (132)) \\ \Theta_6 = ((13)(2), (13)(2), (12)(3)) && \Theta_{12} = ((\mathrm{Id}_3, (132), (132)) && \Theta_{18} = ((132), (132), (123)) \end{array}$

It is partitioned into the following six conjugacy classes:

● The trivial autotopism $\Theta_1$ constitutes as a conjugacy class within itself.

● The conjugacy class described by the isotopism $\Theta_2$ within the autotopism group $\mathrm{Atop}(L_3)$ is the set $\{\Theta_2, \Theta_3, \Theta_4, \Theta_5, \Theta_6, \Theta_7, \Theta_8, \Theta_9, \Theta_{10}\}$, because

● The conjugacy class described by $\Theta_{11}$ is the set $\{\Theta_{11}, \Theta_{12}\}$, because $\Theta_{12} = \Theta_2\Theta_{11}\Theta_2^{-1}$.

● The conjugacy class described by $\Theta_{13}$ is the set $\{\Theta_{13}, \Theta_{14}\}$, because $\Theta_{14} = \Theta_3\Theta_{13}\Theta_3^{-1}$.

● The conjugacy class described by $\Theta_{15}$ is the set $\{\Theta_{15}, \Theta_{16}\}$, because $\Theta_{16} = \Theta_4\Theta_{15}\Theta_4^{-1}$.

● The conjugacy class described by $\Theta_{17}$ is the set $\{\Theta_{17}, \Theta_{18}\}$, because $\Theta_{18} = \Theta_2\Theta_{17}\Theta_2^{-1}$.

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\in\mathrm{LS}_n$, a pair of isotopisms $\Theta_1\in\mathrm{Atop}(L)$ and $\Theta_2\in S_n\times S_n\times S_n$, and a permutation $\pi\in S_3$. If $(L^{\pi})^{\Theta_2} = L$, then there is a one-to-one correspondence between both sets $CS_{\Theta_1}(L)$ and $CS_{\Theta_2\Theta_1^{\pi}\Theta_2^{-1}}(L)$ so that $\mathrm{scs}_{\Theta_1}(L) = \mathrm{scs}_{\Theta_2\Theta_1^{\pi}\Theta_2^{-1}}(L)$ and $\mathrm{lcs}_{\Theta_1}(L) = \mathrm{lcs}_{\Theta_2\Theta_1^{\pi}\Theta_2^{-1}}(L)$.

Proof. Notice that $\Theta_2\Theta_1^{\pi}\Theta_2^{-1}\in\mathrm{Atop}(L)$, because, from Lemma 1, we have that

Then, similarly to the proof of Lemma 5, the result follows straightforwardly from the fact that, if $P\in\mathrm{CS}_{\Theta_1}(L)$, then $(P^{\pi})^{\Theta_2}\in\mathrm{CS}_{\Theta_2\Theta_1^{\pi}\Theta_2^{-1}}(L)$.

Example 8. Let us consider the Latin square $L_3$ that is described in (2.1), the pair of isotopisms $\Theta_1 = ((123), \mathrm{Id}_3, (123))\in\mathrm{Atop}(L_3)$ and $\Theta_2 = ((23), \mathrm{Id}_3, \mathrm{Id}_3)\in S_3\times S_3\times S_3$, and the permutation $\pi = (23)\in S_3$. In particular, the following two partial Latin squares are $\Theta_1$-critical sets of $L_3$.

Furthermore, since $(L_3^{\pi})^{\Theta_2} = L_3$, the proof of Lemma 7 enables one to ensure that the following two partial Latin squares are $\Theta_2\Theta_1^{\pi}\Theta_2^{-1}$-critical sets of $L_3$. Notice in this regard that $\Theta_2\Theta_1^{\pi}\Theta_2^{-1} = ((132), (132), \mathrm{Id}_3)\in \mathrm{Atop}(L_3)$.

In a similar way to Example 8, since those Latin squares described in (2.1) satisfy that

Lemma 7 enables us to focus on those autotopisms that are listed in Table 4, where, for each one of these autotopisms $\Theta\in \mathrm{Atop}(L)$, with $L\in\{L_2, L_3, L_{4.1}, L_{4.2}, L_{5.1}, L_{5.2}\}$, the number of $\Theta$-critical sets of $L$ is also indicated, together with both values $\mathrm{scs}_{\Theta}(L)$ and $\mathrm{lcs}_{\Theta}(L)$. The values associated with the trivial autotopism $(\mathrm{Id}_n, \mathrm{Id}_n, \mathrm{Id}_n)\in S_n\times S_n\times S_n$ corresponding to the already known ^[15] values $\mathrm{scs}(L)$ and $\mathrm{lcs}(L)$, which denote the respective sizes of the smallest and largest critical sets of a Latin square $L$ are also given. In the following two sections, we will establish the methodology and procedures that we have used in order to determine the rest of the values in Table 4. The corresponding results or references from which the values have been derived are shown in the last column of the table.

Notice that the data shown in Table 4 satisfies in particular the following result about the relationship amongst critical sets based on distinct powers of the same Latin square autotopism.

Lemma 9. Let $L\in\mathrm{LS}^n$ and $\Theta\in\mathrm{Atop}(L)$. If $P\in\mathrm{PLS}_n$ is $\Theta^t$-completable to $L$, for some positive integer $t$, then $P$ is also $\Theta$-completable to $L$. As a consequence,

for every positive integer $t$. In particular,

Proof. The result follows straightforwardly from the definition of being $\Theta$-completable, together with the fact that $\Theta\in\mathrm{Atop}(L)$.

3.   Orbits based on Latin square autotopisms

We have already mentioned in the introductory section that the autotopism group of any partial Latin square acts faithfully on its set of entries. Based on this fact, in this section we show how this action constitutes a good approach for determining the possible sizes of those critical sets based on a given Latin square autotopism.

Let $L\in\mathrm{LS}_n$. Keeping in mind that every autotopism $\Theta = (\alpha, \beta, \gamma)\in\mathrm{Atop}(L)$ generates a subetaoup of $\mathrm{Atop}(L)$ that also acts faithfully on the set of entries $\mathrm{Ent}(L)$, we define the $\Theta$-orbit of an entry $(i, j, k)\in\mathrm{Ent}(L)$ as the set

In addition, if $P\in\mathrm{PLS}_n$ is $\Theta$-compatible, then we define the set

Moreover, $\mathrm{Orb}_{\Theta}(L)$ is the set formed by all the $\Theta$-orbits of the Latin square $L$. The following result establishes that the size of any such $\Theta$-orbit and also the size of the set $\mathrm{Orb}_{\Theta}(L)$ only depend on the cycle decomposition of the permutations $\alpha$ and $\beta$. Notice that, for each positive integer $i\leq n$, we use the notation $\ell_{\pi}(i)$ to denote the length of the cycle $C$ in the unique decomposition of a permutation $\pi\in S_n$ into disjoint cycles such that $\pi(i) = C(i)$.

Lemma 10. Let $L\in\mathrm{LS}_n$ and $\Theta = (\alpha, \beta, \gamma)\in\mathrm{Atop}(L)$. For each entry $(i, j, k)\in\mathrm{Ent}(L)$, we have that

As a consequence,

Proof. The result holds because $\Theta^{\mathrm{lcm}(\ell_{\alpha}(i), \ell_{\beta}(j))}$ preserves the entry $(i, j, k)$, and $\Theta^m((i, j, k))\neq \Theta^{m'}((i, j, k))$, for every pair of distinct non-negative integers $m, \, m' < \mathrm{lcm}(\ell_{\alpha}(i), \ell_{\beta}(j))$.

Let us show now how $\Theta$-orbits can be used for determining an upper bound for the size of any $\Theta$-critical set. Recall to this end that $\lambda_l(\pi)$ denotes the number of cycles of length $l$ in the unique decomposition of a permutation $\pi$ as a product of disjoint cycles.

Proposition 11. Let $L\in\mathrm{LS}_n$ and $\Theta = (\alpha, \beta, \gamma)\in\mathrm{Atop}(L)$. Then, no $\Theta$-critical set of the Latin square $L$ has more than one entry in the same $\Theta$-orbit. As a consequence,

Proof. By definition, it must be $0 < \mathrm{scs}_{\Theta}(L)\leq \mathrm{lcs}_{\Theta}(L)$. The upper bound follows from Lemma 10, together with the fact that every $\Theta$-orbit of the Latin square $L$ is uniquely determined by any of its elements.

As it has been indicated in the proof of the previous result, every entry in a partial Latin square with the isotopism $\Theta$ in its autotopism group uniquely determines its corresponding $\Theta$-orbit. Based on this fact, we may generalize the concept of forced entry described in the introductory section. More specifically, we define a $\Theta$-forced entry of a $\Theta$-completable partial Latin square $P\in\mathrm{PLS}_n$ as an entry of the $\Theta$-completable partial Latin square $\Phi_{\Theta}(P)\in\mathrm{PLS}_n$ that arises recursively from $P$ as follows.

1. We initialise the partial Latin square as $\Phi_{\Theta}(P): = P$.

2. Then, we perform $\mathrm{Ent}(\Phi_{\Theta}(P)): = \mathrm{Ent}(\Phi_{\Theta}(P))\cup \bigcup_{e\in\mathrm{Ent}(P)}\mathrm{Orb}_{\Theta}(e)$.

3. If the resulting partial Latin square does not have any forced entry, then the procedure finishes. Otherwise, we add its forced entries, together with all the subsequent ones, to the set $\mathrm{Ent}(\Phi_{\Theta}(P))$. Then, we go back to the second step.

Notice in particular that, if $\Theta$ is the trivial isotopism, then this definition of $\Theta$-forced entry coincides with the usual one of forced entry. Furthermore, $\Phi_{\Theta}$ may be considered as a function that maps any $\Theta$-completable partial Latin square $P$ to the $\Theta$-completable partial Latin square $\Phi_{\Theta}(P)$. We term it the $\Theta$-forcing map.

Example 12. Let us consider the isotopism $\Theta = ((12)(34), (13)(24), (14)(23))\in S_4\times S_4\times S_4$ and the $\Theta$-completable partial Latin square

In particular,

The inclusion of both entries $(2, 3, 4)$ and $(2, 4, 3)$ into the set $\mathrm{Ent}(P)$ gives rise to the partial Latin square

whose forced entries give rise in turn to the partial Latin square

Belonging to the same $\Theta$-orbit is an equivalence relation among the entries in the set $\mathrm{Ent}(L)$ and hence, the set $\mathrm{Orb}_{\Theta}(L)$ formed by all the $\Theta$-orbits of the Latin square $L$ constitutes a partition of its entry set. In order to visualise this partition in an easier way, we will colour the cells of $L$ that are associated to the same $\Theta$-orbit in the same colour. We will term the $\Theta$-colouring of $L$ any such colouring of its cells. The following example illustrates all the previous concepts and results.

Example 13. Let us consider the autotopism $\Theta = ((12), (12), \mathrm{Id}_2)$ of the Latin square $L_2\in\mathrm{LS}_2$ that is described in (2.1). The set $\mathrm{Orb}_{\Theta}(L_2)$ constitutes a partition of the set of entries $\mathrm{Ent}(L_2)$, which is formed by the two $\Theta$-orbits

A $\Theta$-colouring of the Latin square $L_2$ is, therefore,

From Proposition 11, it is known that $\mathrm{lcs}_{\Theta}(L_2)\leq 2$. Indeed, it is readily verified that every entry in the set $\mathrm{Ent}(L_2)$ is $\Theta$-forced by any other given entry. So, $\mathrm{scs}_{\Theta}(L_2) = \mathrm{lcs}_{\Theta}(L_2) = 1$ and $|\mathrm{CS}_{\Theta}(L_2)| = 4$.

Based on Proposition 11, we say that two $\Theta$-critical sets $P$ and $Q$ of a given Latin square with the isotopism $\Theta$ as an autotopism are equivalent if they have the same size and $\mathrm{Orb}_{\Theta}(P) = \mathrm{Orb}_{\Theta}(Q)$. To be equivalent is an equivalence relation among critical sets based on a Latin square isotopism. Thus, for instance, the $\Theta$-critical sets

of the Latin square $L_2$ in Example 13 are equivalent. Moreover, the corresponding set $\mathrm{CS}_{\Theta}(L_2)$ is distributed into two equivalence classes. They can be represented, for instance, by the $\Theta$-critical sets

The number of distinct equivalence classes associated to each case in Table 4 is indicated therein in the column labeled $\mathrm{EC}$. Exhaustive lists of representatives of each one of these equivalence classes are available online in ^[49].

Furthermore, both $\Theta$-orbits in Example 13 play the same role in determining $\Theta$-critical sets. Nevertheless, this is not generally the case. In order to see it, let $L\in\mathrm{LS}_n$ and $\Theta\in\mathrm{Atop}(L)$. Then, we say that a $\Theta$-orbit of $L$ is trivial, if it contains exactly one entry. Otherwise, we say that it is

● principal, if every pair of entries $(i, j, k)$ and $(i', j', k')$ verifies that $i\neq i'$, $j\neq j'$ and $k\neq k'$; or

● secondary, if it contains two distinct entries with one common component.

In addition, we say that a secondary $\Theta$-orbit is row-monotone (respectively, column-monotone) if all its entries are in the same row (respectively, column). Moreover, two row-monotone (respectively, column-monotone) $\Theta$-orbits are parallel if both the set of columns and the set of symbols (respectively, the set of rows and the set of symbols) of all their respective entries coincide. Further, a secondary $\Theta$-orbit is said to be symbol-monotone if the symbols of all its entries coincide. Two symbol-monotone $\Theta$-orbits are parallel if both the set of rows and the set of columns of their respective entries coincide. If a secondary $\Theta$-orbit is not row-monotone, column-monotone or symbol-monotone, it is said to be non-monotone. As an example, both $\Theta$-critical sets in Example 13 are secondary, symbol-monotone and parallel.

Proposition 14. Let $L\in\mathrm{LS}_n$ and $\Theta\in\mathrm{Atop}(L)$. If there exist $m$ secondary parallel $\Theta$-orbits of the same type (that is, row-, column- or symbol-monotone), then every $\Theta$-critical set of $L$ contains at least $m-1$ entries. Hence,

Proof. Let $P\in\mathrm{PLS}_n$ be a $\Theta$-critical set of $L$, whose size is less than $m-1$. Then, there exist at least two parallel secondary $\Theta$-orbits of the same type in $L$ such that none of their entries belong to the set $\mathrm{Ent}(P)$. The parallelism of these two $\Theta$-orbits implies the existence of a one-to-one correspondence among their sets of entries so that two entries are uniquely associated if and only if one the following two assertions hold.

● Either both $\Theta$-orbits are row-monotone or both of them are symbol-monotone. In any case, the pair of uniquely associated entries share the same column.

● Both $\Theta$-orbits are column-monotone and the pair of uniquely associated entries share the same row.

Let $L'$ be the Latin square resulting after switching the symbols of each pair of such associated entries. Then, it is readily verified that $P$ is also $\Theta$-completable to $L'$, which is a contradiction with the fact that $P$ is a $\Theta$-critical set of $L$.

Example 15. Let us consider the autotopism $\Theta = ((123), (132), \mathrm{Id}_3)$ of the Latin square $L_3\in\mathrm{LS}_3$ that is described in (2.1). Notice from the $\Theta$-colouring of $L_3$

that the set $\mathrm{Orb}_{\Theta}(L_3)$ is formed by three parallel symbol-monotone $\Theta$-orbits. Then, Propositions 11 and 14 imply that $2\leq \mathrm{scs}_{\Theta}(L_3)\leq \mathrm{lcs}_{\Theta}(L_3)\leq 3$. Indeed, it is easily verified that every entry in the set $\mathrm{Ent}(L_3)$ is $\Theta$-forced by any two entries belonging to two distinct secondary $\Theta$-orbits. Hence, $\mathrm{scs}_{\Theta}(L_3) = \mathrm{lcs}_{\Theta}(L_3) = 2$. Moreover, the set $\mathrm{CS}_{\Theta}(L_3)$ is distributed into three equivalence classes and thus, $|\mathrm{CS}_{\Theta}(L_3)| = 3\cdot 3^2 = 27$.

Notice that both autotopisms appearing in Examples 13 and 15 are formed by singular length $n$ row- and column-permutations, and a trivial symbol-permutation. The following result characterises the critical sets based on this kind of autotopism.

Theorem 16. Let $L\in\mathrm{LS}_n$ and $\Theta = (\alpha, \beta, \mathrm{Id}_n)\in \mathrm{Atop}(L)$. If $z_{\alpha} = z_{\beta} = n$, then the following assertions hold.

a) $\mathrm{scs}_{\Theta}(L) = \mathrm{lcs}_{\Theta}(L) = n-1$.

b) $|CS_{\Theta}(L)| = n^n$.

Proof. As $\gamma$ = $\mathrm{Id}_n$, it follows that the set $\mathrm{Orb}_{\Theta}(L)$ is formed by $n$ secondary $\Theta$-orbits, with each orbit consisting of the $n$ occurrences of each of the $n$ symbols of $L$. It is then straightforwardly verified from Proposition 11 that every $\Theta$-critical set of $L$ is formed by exactly $n-1$ entries, each one of them associated to a different symbol. Hence, assertion (a) holds. The second assertion follows from the number of possible choices of these $n-1$ entries.

Now, let us illustrate the case of a Latin square containing different types of secondary $\Theta$-orbits.

Example 17. Let us consider the autotopism $\Theta = ((1234), (1234), (24))$ of the Latin square $L_{4.1}$. Notice from the $\Theta$-colouring of $L_{4.1}$

that the set $\mathrm{Orb}_{\Theta}(L_{4.1})$ is formed by two parallel symbol-monotone and two non-monotone $\Theta$-orbits. Proposition 14 implies that every $\Theta$-critical set of $L_{4.1}$ contains one entry of a symbol-monotone $\Theta$-orbit. It is easily verified that such a $\Theta$-critical set is indeed a partial Latin square of order two containing also an entry of a non-monotone $\Theta$-orbit. Hence, $\mathrm{scs}_{\Theta}(L_{4.1}) = \mathrm{lcs}_{\Theta}(L_{4.1}) = 2$. Moreover, the set $\mathrm{CS}_{\Theta}(L_{4.1})$ is distributed into four equivalence classes and thus, $|\mathrm{CS}_{\Theta}(L_{4.1})| = 4\cdot 4^2 = 64$.

Let us show now a pair of cases in which all the corresponding $\Theta$-orbits are principal. In both cases, $\Theta = (\alpha, \beta, \gamma)$ is an isotopism such that $z_{\alpha} = z_{\beta} = z_{\gamma} = n$.

Example 18. Let us consider the autotopism $\Theta = ((123), (123), (132))$ of the Latin square $L_3\in\mathrm{LS}_3$ that is described in (2.1). Notice from the $\Theta$-colouring of $L_3$

that the set $\mathrm{Orb}_{\Theta}(L_3)$ is formed by three principal $\Theta$-orbits. From Proposition 11, we have that $\mathrm{lcs}_{\Theta}(L_3)\leq 3$. In this case, it is straightforwardly verified that every $\Theta$-critical set of $L_3$ is a partial Latin square formed by only one of its entries. Hence, $\mathrm{scs}_{\Theta}(L_3) = \mathrm{lcs}_{\Theta}(L_3) = 1$. Moreover, the set $\mathrm{CS}_{\Theta}(L_3)$ is distributed into three equivalence classes and thus, $|\mathrm{CS}_{\Theta}(L_3)| = 3\cdot 3 = 9$.

Example 19. Let us consider the autotopism $\Theta = ((12345), (12345), (13524))$ of the Latin square $L_{5.1}\in\mathrm{LS}_5$ that is described in (2.1). Notice from the $\Theta$-colouring of $L_{5.1}$

that the set $\mathrm{Orb}_{\Theta}(L_{5.1})$ is formed by five principal $\Theta$-orbits. A simple study of cases enables us to ensure that every entry in the set $\mathrm{Ent}(L_{5.1})$ is $\Theta$-forced by any two entries of a pair of different $\Theta$-orbits. Hence, $\mathrm{scs}_{\Theta}(L_{5.1}) = \mathrm{lcs}_{\Theta}(L_{5.1}) = 2$. Moreover, the set $\mathrm{CS}_{\Theta}(L_{5.1})$ is distributed into ten equivalence classes and thus, $|\mathrm{CS}_{\Theta}(L_{5.1})| = 10\cdot 5^2 = 250$.

The following result shows how the existence of exactly one trivial $\Theta$-orbit simplifies the construction of $\Theta$-critical sets.

Lemma 20. Let $L\in\mathrm{LS}_n$ and let $\Theta = (\alpha, \beta, \gamma)\in\mathrm{Atop}(L)$ be such that $\lambda_1^{\alpha} = \lambda_1^{\beta} = 1$. Then, no $\Theta$-critical set of $L$ contains the entry of its trivial $\Theta$-orbit.

Proof. Let $i, j, k\leq n$ be the only three positive integers such that $\ell_{\alpha}(i) = \ell_{\beta}(j) = \ell_{\gamma}(k) = 1$. This implies that every Latin square that contains the isotopism $\Theta$ within its autotopism group has to contain the entry $(i, j, k)$. Thus, the existence of such an entry in a uniquely $\Theta$-completable partial Latin square does not provide any extra information and can be removed from the latter in order to obtain a $\Theta$-critical set.

In the case of dealing with a non-trivial autotopism $\Theta$ of a Latin square $L$ of order $n > 1$, the existence of exactly one trivial $\Theta$-orbit of $L$ implies the existence of principal and secondary $\Theta$-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 $\Theta$-orbit for determining the corresponding $\Theta$-critical sets.

Example 21. Let us deal with the autotopism $\Theta = ((12), (12), (13))$ of the Latin square $L_3\in\mathrm{LS}_3$ that is described in (2.1). Notice from the $\Theta$-colouring of $L_3$

that the set $\mathrm{Orb}_{\Theta}(L_3)$ is formed by a principal $\Theta$-orbit ($\mathrm{Orb}_{\Theta}((1, 1, 1))$), a row-monotone $\Theta$-orbit ($\mathrm{Orb}_{\Theta}((3, 1, 3))$), a column-mononone $\Theta$-orbit ($\mathrm{Orb}_{\Theta}((1, 3, 3))$), a symbol-monotone $\Theta$-orbit ($\mathrm{Orb}_{\Theta}((1, 2, 2))$) and a trivial $\Theta$-orbit ($\mathrm{Orb}_{\Theta}((3, 3, 2))$). The study of these five $\Theta$-orbits enables us to determine the set of $\Theta$-critical sets of the Latin square $L_3$. Thus, for instance, Lemma 20 implies that no $\Theta$-critical set of $L_3$ contains the entry $(3, 3, 2)$. A simple study of cases based on $\Theta$-forced entries enables us to ensure that every $\Theta$-critical set of $L_3$ contains exactly either

● one entry belonging to the principal $\Theta$-orbit; or

● two entries belonging to two distinct secondary $\Theta$-orbits.

Hence, $\mathrm{scs}_{\Theta}(L_3) = 1 < \mathrm{lcs}_{\Theta}(L_3) = 2$. Moreover, the set $\mathrm{CS}_{\Theta}(L_3)$ is distributed into four equivalence classes having the following arrays as possible representatives.

Thus, $|\mathrm{CS}_{\Theta}(L_3)| = 1\cdot 2 + 3\cdot 2^2 = 14$.

Example 22. Let us consider the autotopism $\Theta = ((243), (134), (134))$ of the Latin square $L_{4.1}\in\mathrm{LS}_4$ that is described in (2.1). Notice from the $\Theta$-colouring of $L_{4.1}$

that the set $\mathrm{Orb}_{\Theta}(L_{4.1})$ is formed by two principal $\Theta$-orbits ($\mathrm{Orb}_{\Theta}((2, 3, 4))$ and $\mathrm{Orb}_{\Theta}((2, 4, 3))$), a row-monotone $\Theta$-orbit ($\mathrm{Orb}_{\Theta}((1, 1, 1))$), a column-monotone $\Theta$-orbit ($\mathrm{Orb}_{\Theta}((2, 2, 1))$), a symbol-monotone $\Theta$-orbit ($\mathrm{Orb}_{\Theta}((2, 1, 2))$) and a trivial $\Theta$-orbit ($\mathrm{Orb}_{\Theta}((1, 2, 2))$). From Lemma 20, no $\Theta$-critical set of $L_{4.1}$ contains the entry $(1, 2, 2)$. In addition, every $\Theta$-critical set of $L_{4.1}$ contains exactly a pair of entries of two different non-trivial $\Theta$-orbits. Hence, $\mathrm{scs}_{\Theta}(L_{4.1}) = \mathrm{lcs}_{\Theta}(L_{4.1}) = 2$. Moreover, the set $\mathrm{CS}_{\Theta}(L_{4.1})$ is distributed into ten equivalence classes and thus, $|\mathrm{CS}_{\Theta}(L_{4.1})| = 10\cdot 3^2 = 90$.

Example 23. Let us consider the autotopism $\Theta = ((2354), (1243), (1243))$ of the Latin square $L_{5.1}\in\mathrm{LS}_5$ that is described in (2.1). Notice from the $\Theta$-colouring of $L_{5.1}$

that the set $\mathrm{Orb}_{\Theta}(L_{5.1})$ is formed by three principal $\Theta$-orbits ($\mathrm{Orb}_{\Theta}((2, 1, 2))$, $\mathrm{Orb}_{\Theta}((2, 2, 3))$ and $\mathrm{Orb}_{\Theta}((2, 3, 4))$), a row-monotone $\Theta$-orbit ($\mathrm{Orb}_{\Theta}((1, 1, 1))$), a column-monotone $\Theta$-orbit ($\mathrm{Orb}_{\Theta}((2, 5, 1))$), a symbol-monotone $\Theta$-orbit ($\mathrm{Orb}_{\Theta}((2, 4, 5))$) and a trivial $\Theta$-orbit ($\mathrm{Orb}_{\Theta}((1, 5, 5))$). From Lemma 20, no $\Theta$-critical set of $L_{5.1}$ contains the entry $(1, 5, 5)$. In addition, every $\Theta$-critical set of $L_{5.1}$ must contain at least one principal $\Theta$-orbit, because, the Latin square shown below is another Latin square whose autotopism group contains the isotopism $\Theta$ and this Latin square also contains the same secondary $\Theta$-orbits as the Latin square $L_{5, 1}$. In order to highlight the differences between this Latin square and the Latin square $L_{5.1}$, common $\Theta$-orbits have been assigned the same colouring as those used in the $\Theta$-colouring of $L_{5, 1}$, and any differing cells have been left uncoloured.

Nevertheless, it is readily verified that the knowledge of only one principal $\Theta$-orbit will not enough to recover the whole Latin square $L_{5.1}$. Thus, for instance, the Latin square

has $\Theta$ as an autotopism, but it has in common with $L_{5.1}$ only one principal $\Theta$-orbit and, of course, its trivial $\Theta$-orbit (both of them highlighted with the corresponding colours). Further, the knowledge of only a principal $\Theta$-orbit and other distinct non-trivial $\Theta$-orbit is similarly not enough for determining a $\Theta$-critical set of $L_{5.1}$. Similarly to the two previous cases, this fact is illustrated by the following three Latin squares, all of them having the isotopism $\Theta$ in their autotopism group, and containing the principal $\Theta$-orbit $\mathrm{Orb}_{\Theta}((2, 1, 2))$.

Now, a simple study of cases enables us to ensure that every $\Theta$-critical sets of $L_{5.1}$ is a partial Latin square of size three, whose entries are taken from

● three distinct principal $\Theta$-orbits;

● two distinct principal $\Theta$-orbits and the symbol-monotone $\Theta$-orbit; or

● a principal $\Theta$-orbit and two distinct secondary $\Theta$-orbits.

Hence, $\mathrm{scs}_{\Theta}(L_{5.1}) = \mathrm{lcs}_{\Theta}(L_{5.1}) = 3$. Moreover, the set $\mathrm{CS}_{\Theta}(L_{5.1})$ is distributed into $13$ equivalence classes and thus, $|\mathrm{CS}_{\Theta}(L_{5.1})| = 13\cdot 4^3 = 832$.

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 $n$ that may be partitioned into subsquares of a same order $1 < m\leq \lfloor\frac n2\rfloor$. 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 $L_{4.1}$ into 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.

Due to their relevance in subsequent results, we designate each of the 12 intercalates its own term $I_{4.1.i}$, for all $i\in\{1, \ldots, 12\}$, so that

Similarly, we can look at the partition of the Latin square $L_{4, 2}$ into intercalates. The following array highlights each intercalate of the Latin square $L_{4.2}$ described in (2.1) in a distinct colour.

Again, due to their relevance in subsequent results, we designate these four intercalates a unique term $I_{4.2.i}$, for all $i\in\{1, 2, 3, 4\}$, so that

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 = (p_{ij})\in\mathrm{PLS}_n$ is the set of cells

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,52,53,54]}. Furthermore, us denote the set of symbols appearing in a partial Latin square $P\in\mathrm{PLS}_n$ by the notation $\mathrm{Sym}(P)$.

Lemma 24. Let $P\in \mathrm{PLS}_n$ be such that $|\mathrm{Sym}(P)|\geq 2$, and let $\Theta\in\mathrm{Atop}(P)$. Then, there exists a partial Latin square $P'\in\mathrm{PLS}_n\setminus\{P\}$ such that $\mathrm{Sh}(P') = \mathrm{Sh}(P)$, $\mathrm{Sym}(P') = \mathrm{Sym}(P)$ and $\Theta\in\mathrm{Atop}(P')$.

Proof. Let us suppose that $\Theta = (\alpha, \beta, \gamma)$. If $\gamma(k) = k$, for all $k\in\mathrm{Sym}(P)$, then it is enough to switch two distinct symbols within all the cells of $P$ containing them. Distinct from $P$, the resulting partial Latin square has the same shape and the same set of symbols as $P$, and has $\Theta$ as an autotopism. Otherwise, if there exists at least one symbol $k_0\in\mathrm{Sym}(P)$ such that $\gamma(k_0)\neq k_0$, then let us define $P'$ so that

It can be readily verified that $P'$ is a partial Latin square with the same shape and the same set of symbols as $P$, with $\Theta$ as a member of its autotopism group. Moreover, since $\gamma$ is not the trivial permutation, there exists at least one entry of the partial Latin square $P'$ that is not an entry of $P$. Hence, $P'\neq 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\in\mathrm{LS}_n$ as a partial Latin square $P\in\mathrm{PLS}_n$ such that $|\mathrm{Sym}(P)|\geq 2$ and all the symbols in the set $\mathrm{Sym}(P)$ appear in all the non-empty rows and all the non-empty columns of $P$. Thus, every subsquare of $L$ having order $m\geq 2$ is a partial subsquare. Moreover, any two parallel symbol-monotone $\Theta$-orbits of a Latin square having $\Theta$ 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, $\mathrm{Row}(P)$ and $\mathrm{Col}(P)$ the set of rows and the set of columns of a given partial Latin square $L\in\mathrm{PLS}_n$.

Proposition 25. Let $P$ and $Q$ be two partial subsquares (not necessarily distinct) of a Latin square $L\in\mathrm{LS}_n$ such that one of the following three conditions hold.

● $\mathrm{Row}(P) = \mathrm{Row}(Q)$;

● $\mathrm{Col}(P) = \mathrm{Col}(Q)$; or

● $\mathrm{Sym}(P) = \mathrm{Sym}(Q)$.

In addition, let $\Theta\in\mathrm{Atop}(L)$ be such that $P^{\Theta} = Q$ and $Q^{\Theta} = P$. Then,

for all $\Theta$-critical sets, $R$, of the Latin square $L$.

Proof. We prove the case $\mathrm{Sym}(P) = \mathrm{Sym}(Q)$. The other two cases follow by parastrophism.

Let $\overline{P}\in\mathrm{PLS}_n$ be such that $\mathrm{Ent}(\overline{P}) = \mathrm{Ent}(P)\cup\mathrm{Ent}(Q)$. From the hypothesis, we have that $\Theta\in\mathrm{Atop}(\overline{P})$. Then, let $\overline{P}'\in\mathrm{PLS}_n\setminus\{\overline{P}\}$ be the partial Latin square that results from $\overline{P}$ after following the constructive proof of Lemma 24. In addition, let $L'\in\mathrm{LS}_n\setminus\{L\}$ be the Latin square that results from $L$ after replacing the entries in $\overline{P}$ by those ones in $\overline{P}'$. It is well-defined because, again from the hypothesis, we can ensure that $\mathrm{Ent}(\overline{P}') = \mathrm{Ent}(P')\cup\mathrm{Ent}(Q')$, where $P'$ and $Q'$ are two partial subsquares of $L'$ such that $\mathrm{Sym}(P') = \mathrm{Sym}(Q)$, and whose shapes coincide, respectively, with those ones of $P$ and $Q$. The result follows readily from the fact that, if $R\in\mathrm{PLS}_n$ is a partial Latin square $\Theta$-completable to $L$ such that $(\mathrm{Ent}(P)\cup\mathrm{Ent}(Q))\cap\mathrm{Orb}_{\Theta}(R) = \emptyset$, then it is also $\Theta$-completable to $L'$.

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 $L_{4.1}$ and $L_{4.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 $\Theta = ((12)(34), (12)(34), \mathrm{Id}_4)\in\mathrm{Atop}(L_{4.1})\cap\mathrm{Atop}(L_{4.2})$. Respective $\Theta$-colouring of the Latin squares $L_{4.1}$ and $L_{4.2}$ are, for instance,

Let $i\in\{1, 2\}$. Notice that the set $\mathrm{Orb}_{\Theta}(L_{4.i})$ is formed by eight secondary $\Theta$-orbits. Moreover, the autotopism $\Theta$ preserves the four intercalates $I_{4.i.1}$ to $I_{4.i.4}$. Thus, Proposition 25 implies that every $\Theta$-critical set of the Latin square $L_{4.i}$ contains at least one entry of each one of these four intercalates. Hence, $\mathrm{scs}_{\Theta}(L_{4.i})\geq 4$. This lower bound is indeed reached. Thus, for instance, the following two partial Latin squares are $\Theta$-critical sets of $L_{4.1}$.

In fact, a simple study of cases enables us to ensure that every $\Theta$-critical set $P$ of $L_{4.i}$ is a partial Latin square of size four satisfying the following two assertions.

● It contains one entry of each one of the four intercalates $I_{4.i.1}$ to $I_{4.i.4}$.

● $|\mathrm{Sym}(P)|\geq 3$.

Hence, $\mathrm{scs}_{\Theta}(L_{4.i}) = \mathrm{lcs}_{\Theta}(L_{4.i}) = 4$. Moreover, the set $\mathrm{CS}_{\Theta}(L_{4.i})$ is distributed into 12 equivalence classes. Eight of them contain four distinct symbols, and the other four contain only three distinct symbols. Thus, $|\mathrm{CS}_{\Theta}(L_{4.i})| = 12\cdot 2^4 = 192$.

Example 27. Let $\Theta = ((23), (14), (14))\in\mathrm{Atop}(L_{4.1})$. Notice from the $\Theta$-colouring of $L_{4.1}$

that the set $\mathrm{Orb}_{\Theta}(L_{4.1})$ is formed by six secondary and four trivial $\Theta$-orbits. Moreover, the autotopism $\Theta$ preserves the four intercalates $I_{4.9}$ to $I_{4.12}$. Thus, Proposition 25 implies that every $\Theta$-critical set of the Latin square $L_{4.1}$ contains at least one entry of each one of these four intercalates. Hence, $\mathrm{scs}_{\Theta}(L_{4.i})\geq 4$. Again, this lower bound is reached. Thus, for instance, the following four partial Latin squares are $\Theta$-critical sets of $L_{4.1}$.

In fact, every partial Latin square of order and size four having an entry of each one of the four intercalates $I_{4.9}$ to $I_{4.12}$ constitutes a $\Theta$-critical set of $L_{4.1}$. Thus, no $\Theta$-critical set of size five exists and hence, $\mathrm{scs}_{\Theta}(L_{4.1}) = \mathrm{lcs}_{\Theta}(L_{4.1}) = 4$. Moreover, the set $\mathrm{CS}_{\Theta}(L_{4.1})$ is distributed into $32$ equivalence classes and $|\mathrm{CS}_{\Theta}(L_{4.1})| = 4^4 = 256$.

Example 28. Let $\Theta = ((12), (12), (34))\in\mathrm{Atop}(L_{4.2})$. Notice from the $\Theta$-colouring of $L_{4.2}$

that the set $\mathrm{Orb}_{\Theta}(L_{4.2})$ is formed by six secondary and four trivial $\Theta$-orbits. Moreover, the autotopism $\Theta$ preserves the four intercalates $I_{4.1}$ to $I_{4.4}$. Similarly to Example 27, we can ensure that $\mathrm{scs}_{\Theta}(L_{4.2}) = \mathrm{lcs}_{\Theta}(L_{4.2}) = 4$. Moreover, the set $\mathrm{CS}_{\Theta}(L_{4.2})$ is distributed into $32$ equivalence classes and $|\mathrm{CS}_{\Theta}(L_{4.2})| = 4^4 = 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 $\Theta = ((1324), (1324), (12)(34))$ of the Latin square $L_{4.2}$. Notice from the $\Theta$-colouring of $L_{4.2}$

that the set $\mathrm{Orb}_{\Theta}(L_{4.2})$ is formed by four non-monotone $\Theta$-orbits. Moreover, the autotopism $\Theta$ switches the intercalates $I_{4.1}$ and $I_{4.4}$, as well as the intercalates $I_{4.2}$ and $I_{4.3}$. Thus, Proposition 25 implies that every $\Theta$-critical set of the Latin square $L_{4.2}$ contains at least one entry of $\mathrm{Ent}(I_{4.1})\cup \mathrm{Ent}(I_{4.4})$, and one entry of $\mathrm{Ent}(I_{4.2})\cup \mathrm{Ent}(I_{4.3})$. It is readily verified that every $\Theta$-critical set of $L_{4.2}$ is indeed of this form. Hence, $\mathrm{scs}_{\Theta}(L_{4.2}) = \mathrm{lcs}_{\Theta}(L_{4.2}) = 2$. Moreover, the set $\mathrm{CS}_{\Theta}(L_{4.2})$ is distributed into four equivalence classes and $|\mathrm{CS}_{\Theta}(L_{4.2})| = 4\cdot 4^2 = 64$.

Example 30. Let us consider the autotopism $\Theta = ((12)(34), (13)(24), (14)(23))$ of the Latin square $L_{4.1}$. Notice from the $\Theta$-colouring of $L_{4.1}$

that the set $\mathrm{Orb}_{\Theta}(L_{4.1})$ is formed by eight principal $\Theta$-orbits. Moreover, the autotopism $\Theta$ preserves the partial subsquares

Proposition 25 implies that every $\Theta$-critical set of the Latin square $L_{4.1}$ contains an entry of each one of these two partial subsquares. As a consequence, $\mathrm{scs}_{\Theta}(L_{4.1})\geq 2$. Moreover, there are $64$ distinct candidates for $\Theta$-critical sets of $L_{4.1}$ having size two. If we focus on those ones containing the entry $(1, 1, 1)$ and we keep in mind that every $\Theta$-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

According to our reasoning, each one of these four partial Latin squares represents $16$ distinct candidates of the $64$ mentioned ones. After applying the $\Theta$-forcing map $\Phi_{\Theta}$ to each one of these four arrays, we obtain, respectively, the partial Latin squares

None of them is a $\Theta$-critical set of the Latin square $L_{4.1}$. As a consequence, $\mathrm{scs}_{\Theta}(L_{4.1})\geq 3$. This lower bound is indeed reached. Thus, for instance, the following partial Latin square is a $\Theta$-critical set of $L_{4.1}$.

Now, in order to determine all the $\Theta$-critical sets of $L_{4.1}$, notice also that the autotopism $\Theta$ switches the six pairs of intercalates

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 $\Theta$-critical set of the Latin square $L_{4.1}$ satisfies the following assertions.

● 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 $\Theta$-orbit.

A simple study of cases enables us to affirm that every partial Latin square $\Theta$-completable to $L_{4.1}$, having size three and satisfying the last three assertions, is indeed a $\Theta$-critical set of $L_{4.1}$. In order to illustrate this fact, we highlight with the symbol $x$ those cells corresponding to entries in $\mathrm{L}_{4.1}$ that 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.

No other $\Theta$-critical sets exists and hence, $\mathrm{scs}_{\Theta}(L_{4.1}) = \mathrm{lcs}_{\Theta}(L_{4.1}) = 3$. Moreover, the set $\mathrm{CS}_{\Theta}(L_{4.1})$ is distributed into $32$ equivalence classes and $|\mathrm{CS}_{\Theta}(L_{4.1})| = 32\cdot 2^3 = 256$.

Example 31. Let us consider the autotopism $\Theta = ((13)(24), (14)(23), (34))$ of the Latin square $L_{4.2}\in\mathrm{LS}_4$ that is described in (2.1). Notice from the $\Theta$-colouring of $L_{4.2}$

that the set $\mathrm{Orb}_{\Theta}(L_{4.2})$ is formed by four principal $\Theta$-orbits and four non-parallel symbol-monotone $\Theta$-orbits. Moreover, the autotopism $\Theta$ switches both intercalates $I_{4.1}$ and $I_{4.4}$, and also both intercalates $I_{4.2}$ and $I_{4.3}$. Thus, Proposition 25 implies that every $\Theta$-critical set of the Latin square $L_{4.2}$ contains at least one entry of each mentioned pair of intercalates, and hence, $\mathrm{scs}_{\Theta}(L_{4.2})\geq 2$. Similarly to the reasoning followed in Example 30, the study of the $64$ candidates for size 2 $\Theta$-critical sets of $L_{4.2}$ may be focused on the partial Latin squares pertaining to the triple (1, 1;1) (each one of them representing to $16$ distinct candidates)

After applying the $\Theta$-forcing map $\Phi_{\Theta}$ to each one of these four arrays, we obtain, respectively, the partial Latin squares

None of the above constitute a $\Theta$-critical set of the Latin square $L_{4.2}$. As a consequence, $\mathrm{scs}_{\Theta}(L_{4.2})\geq 3$. This lower bound is indeed reached. One example of a size 3 $\Theta$-critical set of $L_{4.2}$ is given by the following partial Latin square.

Let us highlight with the symbol $x$ those cells corresponding to entries in $\mathrm{L}_{4.2}$ that 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 $\Theta$-critical set of $\mathrm{L}_{4.2}$ having size three.

No other $\Theta$-critical sets exists and hence, $\mathrm{scs}_{\Theta}(L_{4.2}) = \mathrm{lcs}_{\Theta}(L_{4.2}) = 3$. Moreover, the set $\mathrm{CS}_{\Theta}(L_{4.2})$ is distributed into $28$ equivalence classes and $|\mathrm{CS}_{\Theta}(L_{4.2})| = 28\cdot 2^3 = 224$.

In order to finish the study of cases described in Table 4, let us focus now on those autotopisms of the Latin squares $L_{5.1}$ and $L_{5.2}$ that have not still been dealt with.

Example 32. Let us consider the autotopism $\Theta = ((345), (345), (345))$ of the Latin square $L_{5.2}\in\mathrm{LS}_5$. Notice from the $\Theta$-colouring of $L_{5.2}$

that the set $\mathrm{Orb}_{\Theta}(L_{5.2})$ is formed by

● the principal $\Theta$-orbit

● the two parallel row-monotone $\Theta$-orbits

● the two parallel column-monotone $\Theta$-orbits

● the two parallel symbol-monotone $\Theta$-orbits

● and the four trivial $\Theta$-orbits

Moreover, the autotopism $\Theta$ preserves the two partial subsquares

Thus, Proposition 25 implies that every $\Theta$-critical set of the Latin square $L_{5.2}$ contains at least one entry of each one of the two previous partial subsquares. In addition, Proposition 14 implies that such a $\Theta$-critical set also contains one entry of a row-monotone $\Theta$-orbit and one entry of a column-monotone $\Theta$-orbit. Nevertheless, it is readily verified that these four entries do not constitute by themselves a $\Theta$-critical set of $L_{5.2}$. We illustrate this fact with the following three Latin squares. All of them have the isotopism $\Theta$ in their corresponding autotopism group. We highlight in each case the common $\Theta$-orbits with $L_{5.2}$.

A simple study of cases enables us to ensure that every $\Theta$-critical set of $L_{5.2}$ is

● a partial Latin square of size five containing exactly one entry of each one of the five types of $\Theta$-orbits; or

● a partial Latin square of size six containing a trivial $\Theta$-orbit, an entry of a given pair of secondary $\Theta$-orbits of the same type, and four entries belonging to distinct secondary $\Theta$-orbits of the remaining two types.

Hence, $\mathrm{scs}_{\Theta}(L_{5.2}) = 5 < 6 = \mathrm{lcs}_{\Theta}(L_{5.2})$. Moreover, the set $\mathrm{CS}_{\Theta}(L_{5.2})$ is distributed into $56$ equivalence classes, from which $32$ are $\Theta$-critical sets of size five and $24$ are $\Theta$-critical sets of size six. Thus, $|\mathrm{CS}_{\Theta}(L_{5.2})| = 32\cdot 3^4 + 24\cdot 3^5 = 8424$.

The last two examples focus on autotopisms having the cycle structure $(2^21, 2^21, 2^21)$. The following lemma is useful to deal with this cycle structure.

Lemma 33. Let $L\in\mathrm{LS}_n$ and $\Theta, \Theta'\in S_n\times S_n\times S_n$ be such that $\Theta\in \mathrm{Atop}(L)\cap\mathrm{Atop}(L^{\Theta'})$ and $\Theta'\not\in\mathrm{Atop}(L)$. Then, every $\Theta$-critical set of $L$ contains at least one entry of the set $\mathrm{Ent}(L)\setminus\mathrm{Ent}(L^{\Theta'})$.

Proof. The result follows naturally from the fact that every partial Latin square $P\in\mathrm{PLS}_n$ such that $\mathrm{Ent}(P)\subseteq \mathrm{Ent}(L)\cap \mathrm{Ent}(L^{\Theta'})$ is $\Theta$-completable to both Latin squares $L$ and $L^{\Theta'}$.

Example 34. Let us consider the autotopism $\Theta = ((12)(35), (13)(45), (14)(23))$ of the Latin square $L_{5.1}\in\mathrm{LS}_5$. Notice from the $\Theta$-colouring of $L_{5.1}$

that the set $\mathrm{Orb}_{\Theta}(L_{5.1})$ is formed by $13$ $\Theta$-orbits (six principal, two row-monotone, two column-monotone, two symbol-monotone and one trivial). In order to determine all the $\Theta$-critical sets of $L_{5.1}$, it is enough to focus on an entry of each one of the $12$ non-trivial $\Theta$-orbits. Thus, we can focus on the entries of the partial Latin square

Further, since the Latin square $L_{5.1}$ satisfies the hypothesis of Lemma 33 for each one of the isotopisms

Lemma 33 implies that every $\Theta$-critical set of $L_{5.1}$ contains at least one entry of each one of the following six partial Latin squares.

Thus, those $\Theta$-critical sets of $L_{5.1}$ having only entries in the set $\mathrm{Ent}(P)$ must contain at least one entry of each one of the following six partial Latin squares.

Hence, $\mathrm{scs}_{\Theta}(L_{5.1})\geq 2$. Up to distinct choice in the same $\Theta$-orbit, the candidates for $\Theta$-critical sets of $L_{5.1}$ having size two and entries in $\mathrm{Ent}(P)$ are the following three arrays.

Nevertheless, none of these three arrays is a $\Theta$-critical set of the Latin square $L_{5.1}$. As a consequence, $\mathrm{scs}_{\Theta}(L_{5.1})\geq 3$. This lower bound is reached. Thus, for instance, the following two partial Latin squares are $\Theta$-critical sets of $L_{5.1}$.

They are indeed the only ones of size three containing all their entries in the set $\mathrm{Ent}(P)$. Notice also that each one of them is associated to three distinct principal $\Theta$-orbits of $L_{5.1}$.

Now, let us determine the $\Theta$-critical sets of $L_{5.1}$ having size four and entries in the set $\mathrm{Ent}(P)$. To this end, we enumerate by brute force all the partial Latin squares of size four and entries in $\mathrm{Ent}(P)$, which are uniquely $\Theta$-completable to $L_{5.1}$. From the resulting list, we remove those partial Latin squares containing all the entries of $\mathrm{Ent}(Q_1)$ or $\mathrm{Ent}(Q_2)$. By definition, none of the removed partial Latin squares is a $\Theta$-critical set of $L_{5.1}$. The resulting list is formed by $36$ partial Latin squares, whose entries are taken from

● three distinct principal $\Theta$-orbits and one secondary-$\Theta$-orbit ($12$ arrays); or

● two distinct principal $\Theta$-orbits and two distinct secondary $\Theta$-orbits ($24$ arrays).

They are indeed all the $\Theta$-critical sets of $L_{5.1}$ having size four and entries in $\mathrm{Ent}(P)$. Let us illustrate them separately with the following two arrays.

A similar procedure may be done in order to compute all the $\Theta$-critical sets of $L_{5.1}$ having size five and entries in the set $\mathrm{Ent}(P)$. There are $78$ such partial Latin squares, whose entries are taken from

● three distinct principal $\Theta$-orbits and two secondary-$\Theta$-orbits of distinct types ($12$ arrays);

● two distinct principal $\Theta$-orbits and three distinct secondary $\Theta$-orbits of pairwise distinct types ($12$ arrays);

● two distinct principal $\Theta$-orbits and three distinct secondary $\Theta$-orbits, from which exactly two of them are of the same type ($24$ arrays);

● one principal $\Theta$-orbit and four distinct secondary $\Theta$-orbits, from which exactly two of them are of the same type ($24$ arrays); or

● one principal $\Theta$-orbit and four distinct secondary $\Theta$-orbits of exactly two distinct types ($6$ arrays).

Let us illustrate them separately with the following five arrays.

The same procedure enables us to ensure that no $\Theta$-critical set of higher size exists. Hence, $\mathrm{scs}_{\Theta}(L_{5.1}) = 3 < 5 = \mathrm{lcs}_{\Theta}(L_{5.1})$. Moreover, the set $\mathrm{CS}_{\Theta}(L_{5.1})$ is distributed into $116$ equivalence clases, from which two of them have size three, $36$ of them have size four and $78$ of them have size five. Thus,

Example 35. Let us consider the autotopism $\Theta = ((13)(45), (25)(34), (13)(45))$ of the Latin square $L_{5.2}\in\mathrm{LS}_5$. Notice from the $\Theta$-colouring of $L_{5.2}$

that the set $\mathrm{Orb}_{\Theta}(L_{5.2})$ is formed by $13$ $\Theta$-orbits (six principal, two row-monotone, two column-monotone, two symbol-monotone and one trivial). In order to determine all the $\Theta$-critical sets of $L_{5.2}$, it is enough to focus on an entry of each one of the $12$ non-trivial $\Theta$-orbits. Thus, we can focus on the entries of the partial Latin square

Further, since the Latin square $L_{5.2}$ satisfies the hypothesis of Lemma 33 for each one of the isotopisms

Lemma 33 implies that every $\Theta$-critical set of $L_{5.2}$ contains at least one entry of each one of the following six partial Latin squares.

Thus, those $\Theta$-critical sets of $L_{5.2}$ having only entries in the set $\mathrm{Ent}(P)$ must contain at least one entry of each one of the following six partial Latin squares.

Hence, $\mathrm{scs}_{\Theta}(L_{5.2})\geq 2$. Up to distinct choice in the same $\Theta$-orbit, the candidates for $\Theta$-critical sets of $L_{5.2}$ having size two and entries in $\mathrm{Ent}(P)$ are the following three arrays.

None of them is a $\Theta$-critical set of the Latin square $L_{5.2}$. As a consequence, $\mathrm{scs}_{\Theta}(L_{5.2})\geq 3$. This lower bound is reached. Thus, for instance, the following two partial Latin squares are $\Theta$-critical sets of $L_{5.2}$. They are the only $\Theta$-critical sets of size three containing all their entries in the set $\mathrm{Ent}(P)$.

By following a similar procedure to that one shown in Example 34, we have that, under the assumption of having all their entries in the set $\mathrm{Ent}(P)$, there are

● $48$ $\Theta$-critical sets of $L_{5.2}$ having size four, whose entries are taken from

- three distinct principal $\Theta$-orbits and one secondary-$\Theta$-orbit ($24$ arrays); or

- two distinct principal $\Theta$-orbits and two distinct secondary $\Theta$-orbits ($24$ arrays); and

● $66$ $\Theta$-critical sets of $L_{5.2}$ having size five, whose entries are taken from

- two distinct principal $\Theta$-orbits and three distinct secondary $\Theta$-orbits of pairwise distinct types ($12$ arrays);

- two distinct principal $\Theta$-orbits and three distinct secondary $\Theta$-orbits, from which exactly two of them are of the same type ($24$ arrays);

- one principal $\Theta$-orbit and four distinct secondary $\Theta$-orbits, from which exactly two of them are of the same type ($24$ arrays); or

- one principal $\Theta$-orbit and four distinct secondary $\Theta$-orbits of exactly two distinct types ($6$ arrays).

Let us illustrate them separately with the following six arrays.

The same procedure enables us to ensure that no $\Theta$-critical set of higher size exists and hence, $\mathrm{scs}_{\Theta}(L_{5.2}) = 3 < 5 = \mathrm{lcs}_{\Theta}(L_{5.2})$. Moreover, the set $\mathrm{CS}_{\Theta}(L_{5.2})$ is distributed into $116$ equivalence clases, from which two of them have size three, $48$ of them have size four and $66$ of them have size five. Thus,

5.   Conclusion and further works

In this paper, we have dealt with the problem of determining $\Theta$-critical sets of Latin squares containing a given isotopism $\Theta$ in their autotopism groups. We have proved in Section 2 that the set of such $\Theta$-critical sets only depends on both the main class of the Latin square under consideration and the cycle structure of the autotopism $\Theta$. In Sections 3 and 4, we have respectively introduced the notions of $\Theta$-orbit and partial subsquare, which play a relevant role in the computation of $\Theta$-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\in\mathrm{PLS}_n$ and $\Theta\in \mathrm{Atop}(L)$. What is the computational complexity of deciding whether the partial Latin square $P$ is $\Theta$-completable?

Question 37. Does a $\Theta$-critical set of size $m$ exist for every $m$ such that, $scs_{\Theta}(L)$ $\leq$ $m$ $\leq$ $lcs_{\Theta}(L)$, for every $L\in\mathrm{LS}_n$ and $\Theta\in\mathrm{Atop}(L)$?

Question 38. Let $\Theta\in S_n\times S_n\times S_n$. We denote the smallest and largest sizes of $\Theta$-critical sets of any given Latin square of order $n$ by $\mathrm{scs}_{\Theta}(n)$ and $\mathrm{lcs}_{\Theta}(n)$ respectively. In a similar way to the classic case, is it possible to find some lower and upper bounds values for both $\mathrm{scs}_{\Theta}(n)$ and $\mathrm{lcs}_{\Theta}(n)$ depending on the order $n$?

Question 39. Except for Example 17, in which two non-monotone $\Theta$-orbits appear, all secondary $\Theta$-orbits shown in the rest of examples of this paper are row-, column- or symbol-monotone. Nevertheless, the existence of non-monotone $\Theta$-orbits is more common amongst Latin squares of higher orders. Thus, for instance, let us consider the isotopism $\Theta = ((123456), (123)(456), (14)(25)(36))\in S_6\times S_6\times S_6$. It constitutes as an autotopism of the following Latin square, note the $\Theta$-colouring associated with this autotopism is also shown in this diagram.

The set of entries of this Latin square under this autotopism are partitioned into six non-monotone $\Theta$-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 $\Theta$-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?

Question 40. In Theorem 16, we have indicated a pair of formulas concerning the values $\mathrm{scs}_{\Theta}(L)$, $\mathrm{lcs}_{\Theta}(L)$ and $|\mathrm{CS}_{\Theta}(L)|$, for any autotopism $\Theta\in S_n\times S_n\times S_n$ with the cycle structure $(n, n, 1^n)$. Is it possible to find this kind of general formula for other cycle structures?

Question 41. Let $P\in\mathrm{PLS}_n$ be a $\Theta$-critical set of a given Latin square. We say that $P$ is $\Theta$-strong if its set of entries can be filled by making use of the $\Theta$-forcing map $\Phi_{\Theta}$. It generalizes the concept of strong critical set ^[55] described in the introductory section, which arises from our definition when $\Theta$ is the trivial autotopism. An illustrative case ensuring the existence of $\Theta$-critical sets that are not $\Theta$-strong, for a non-trivial autotopism $\Theta$, appears in Example 35. More specifically, it is readily verified that every $\Theta$-critical set of size three in such an example is not $\Theta$-strong. Thus, the question is, what about the existence of non-$\Theta$-strong $\Theta$-critical sets for any given autotopism $\Theta$?

Question 42. In Examples 34 and 35, we have described a procedure from which we have obtained that the smallest $\Theta$-critical sets are formed by three entries, each one of them corresponding to a distinct candidate for $\Theta$-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 $n^{O(\log k)}$ subsquares of order $k$. What about partial subsquares?

Acknowledgments

Falcón'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.

A.   Glossary of symbols