La pregunta (3) se refiere a "cuál es el número máximo de equivalente a un pedido ¿Cuadros latinos?"
El caso más sencillo de equivalencia de orden es el de 2 cuadrados latinos que sólo se diferencian por una intercalación (en posiciones mutuamente no adyacentes) que implica (pero no se limita a) valores de símbolos consecutivos. Por ejemplo:
$$\begin{bmatrix} 1 & 2 & 5 & 3 & 4 \\ 3 & 5 & \color{red}1 & 4 & \color{red}2 \\ 5 & 1 & 4 & 2 & 3 \\ 2 & 4 & 3 & 1 & 5 \\ 4 & 3 & \color{red}2 & 5 & \color{red}1 \end{bmatrix} \equiv \begin{bmatrix} 1 & 2 & 5 & 3 & 4 \\ 3 & 5 & \color{red}2 & 4 & \color{red}1 \\ 5 & 1 & 4 & 2 & 3 \\ 2 & 4 & 3 & 1 & 5 \\ 4 & 3 & \color{red}1 & 5 & \color{red}2 \end{bmatrix}$$
Llamamos a esto un ciclo que preserva el orden (OPC). En realidad, ésta es otra forma de definir la equivalencia de orden, ya que ser equivalente implica necesariamente un OPC de alguna descripción, sin embargo, éstos pueden ser más complicados que simples intercambios de ciclos en dos símbolos. A menudo se trata de múltiples ciclos entrelazados. Por ejemplo:
$$\begin{bmatrix} 4 & 3 & 5 & 1 & 6 & 2 \\ \color{blue}2 & 5 & \color{blue}1 & 4 & \color{blue}3 & 6 \\ 6 & 1 & \color{blue}4 & 2 & 5 & \color{blue}3 \\ \color{blue}1 & 4 & \color{blue}3 & 6 & \color{blue}2 & 5 \\ 5 & 2 & 6 & 3 & 4 & 1 \\ \color{blue}3 & 6 & \color{blue}2 & 5 & \color{blue}1 & \color{blue}4 \end{bmatrix} \equiv \begin{bmatrix} 4 & 3 & 5 & 1 & 6 & 2 \\ \color{blue}3 & 5 & \color{blue}2 & 4 & \color{blue}1 & 6 \\ 6 & 1 & \color{blue}3 & 2 & 5 & \color{blue}4 \\ \color{blue}2 & 4 & \color{blue}1 & 6 & \color{blue}3 & 5 \\ 5 & 2 & 6 & 3 & 4 & 1 \\ \color{blue}1 & 6 & \color{blue}4 & 5 & \color{blue}2 & \color{blue}3 \end{bmatrix}$$
También podemos distinguir ordenamientos débiles de órdenes fuertes .
Ordenado fuertemente cuadrados tienen cadenas más largas (caminos dirigidos en el $LDAG$ ) que ordenado débilmente los. Cadenas de longitud $N$ (tiene sentido definir la longitud de la cadena para las LS en términos de vértices, en lugar de aristas) aumentan en gran medida la probabilidad de ordenamientos únicos.
Por tanto, tiene sentido considerar la ordenación más débil posible y conjeturar que ésta corresponderá a clases de orden-equivalencia con cardinalidad máxima.
Incluso para $N$ es fácil construir un cuadrado en el que cada La célula es un fuente o un fregadero , lo que da lugar a un cuadrado sin cadenas de longitud superior a 2 (los sumideros se muestran en rojo):
$$\begin{bmatrix} 1 & \color{darkred}6 & 3 & \color{darkred}4 & 2 & \color{darkred}5 \\ \color{darkred}5 & 1 & \color{darkred}6 & 3 & \color{darkred}4 & 2 \\ 2 & \color{darkred}5 & 1 & \color{darkred}6 & 3 & \color{darkred}4 \\ \color{darkred}4 & 2 & \color{darkred}5 & 1 & \color{darkred}6 & 3 \\ 3 & \color{darkred}4 & 2 & \color{darkred}5 & 1 & \color{darkred}6 \\ \color{darkred}6 & 3 & \color{darkred}4 & 2 & \color{darkred}5 & 1 \end{bmatrix}$$
Incluso para $N$ el número de formas, $C_n$ para fijar la mitad de los símbolos en la mitad de las filas es $C_n=\prod\limits_{k=1}^{n/2} k!$ , por lo que hay $C{_n}^4$ cuadrados latinos que coinciden con este patrón. En este caso $C{_6}=24$ por lo que esperamos que al menos $24^4=20,736$ LS sea equivalente a éste.
Para impar $N$ podemos tener todas las celdas, aparte de una diagonal principal, como fuente o sumidero. Para $N=5$ Esta construcción sería (los sumideros en rojo, las fuentes en azul):
$$\begin{bmatrix} 3 & \color{darkred}4 & \color{darkblue}1 & \color{darkred}5 & \color{darkblue}2 \\ \color{darkblue}2 & 3 & \color{darkred}4 & \color{darkblue}1 & \color{darkred}5 \\ \color{darkred}5 & \color{darkblue}2 & 3 & \color{darkred}4 & \color{darkblue}1 \\ \color{darkblue}1 & \color{darkred}5 & \color{darkblue}2 & 3 & \color{darkred}4 \\ \color{darkred}4 & \color{darkblue}1 & \color{darkred}5 & \color{darkblue}2 & 3 \end{bmatrix}$$
Esto da $N(N-1)$ sumideros/fuentes, y esta LS tiene 8 miembros en su clase de orden-equivalencia. Pero en realidad podemos aumentar estos números con la siguiente disposición:
$$\begin{bmatrix} \color{darkblue}1 & \color{darkred}3 & \color{darkblue}2 & \color{darkred}5 & \color{darkblue}4 \\ \color{darkred}4 & \color{darkblue}1 & 3 & \color{darkblue}2 & \color{darkred}5 \\ \color{darkblue}2 & 4 & \color{darkred}5 & 3 & \color{darkblue}1 \\ \color{darkred}5 & \color{darkblue}2 & 4 & \color{darkblue}1 & \color{darkred}3 \\ \color{darkblue}3 & \color{darkred}5 & \color{darkblue}1 & \color{darkred}4 & \color{darkblue}2 \end{bmatrix}$$
Esta LS tiene 16 miembros en su clase de orden-equivalencia, que es el máximo para $N=5$ .
Para $N=7$ el patrón es similar a $N=5$ excepto que el patrón de 4 celdas sin fregadero/fuente se se encuentra en cualquiera de las 4 posiciones descentradas: $$\begin{bmatrix} \color{darkblue}6 & \color{darkred}7 & \color{darkblue}3 & \color{darkred}5 & \color{darkblue}2 & \color{darkred}4 & \color{darkblue}1 \\ \color{darkred}7 & \color{darkblue}1 & \color{darkred}5 & \color{darkblue}3 & \color{darkred}6 & \color{darkblue}2 & \color{darkred}4 \\ \color{darkblue}2 & \color{darkred}5 & \color{darkblue}4 & \color{darkred}7 & \color{darkblue}1 & \color{darkred}6 & \color{darkblue}3 \\ \color{darkred}4 & \color{darkblue}3 & \color{darkred}7 & \color{darkblue}2 & 5 & \color{darkblue}1 & \color{darkred}6 \\ \color{darkblue}3 & \color{darkred}6 & \color{darkblue}1 & 4 & \color{darkred}7 & 5 & \color{darkblue}2 \\ \color{darkred}5 & \color{darkblue}2 & \color{darkred}6 & \color{darkblue}1 & 4 & \color{darkblue}3 & \color{darkred}7 \\ \color{darkblue}1 & \color{darkred}4 & \color{darkblue}2 & \color{darkred}6 & \color{darkblue}3 & \color{darkred}7 & \color{darkblue}5 \end{bmatrix}$$
Esta LS tiene 156.252 miembros en su clase de orden-equivalencia, y es probablemente el caso máximo. Curiosamente, hemos encontrado LS de 7 x 7 con más sumideros/fuentes (por ejemplo, 47), pero cuya clase de orden-equivalencia es menor.
Si denotamos la cardinalidad máxima de las clases de equivalencia como $M_N$ entonces tenemos..:
- $M_4 \ge 2^4 = 16$ (el máximo real es 17)
- $M_5 = 16$
- $M_6 \ge 12^4 = 20,736$ (máximo real 25.498)
- $M_7 \ge 156,152$ (el más alto encontrado hasta ahora)
- $M_8 \ge 288^4$
Incluso para $N$ el valor $C_n^{4}$ es sólo un límite inferior para $M_n$ ya que no son las únicas equivalencias de orden posibles. Por ejemplo, $M_4 = 2^4 + 1$ , la 17ª LS se obtiene a partir de la siguiente equivalencia:
$$\begin{bmatrix} \color{blue}3 & 1 & 4 & \color{blue}2 \\ 1 & 3 & 2 & 4 \\ 4 & 2 & 3 & 1 \\ \color{blue}2 & 4 & 1 & \color{blue}3 \end{bmatrix} \equiv \begin{bmatrix} \color{blue}2 & 1 & 4 & \color{blue}3 \\ 1 & 3 & 2 & 4 \\ 4 & 2 & 3 & 1 \\ \color{blue}3 & 4 & 1 & \color{blue}2 \end{bmatrix}$$
