He hecho la siguiente pregunta en MathExchange sitio, con una recompensa, sin respuesta ni comentarios. Tal vez tendría comentarios adicionales aquí. El problema surgió mientras leía algunos artículos sobre geometría finita. Empecé a preguntarme si alguien había estudiado esto previamente.
Recordatorio sobre la Plaza Latina: Dado un conjunto $S$ de $n$ (utilizaremos $[n]$ en lo que sigue para simplificar), un cuadrado latino $L$ es una función $L : [n]\times [n] \to S$ es decir, un $n\times n$ con elementos en $S$ , de manera que cada elemento de $S$ aparece exactamente una vez en cada fila y en cada columna. Por ejemplo,
Dejemos que $L_1$ y $L_2$ sean dos cuadrados latinos sobre los conjuntos de tierra $S_1$ , $S_2$ respectivamente. Se denominan ortogonal si para cada $(x_1, x_2) \in S_1 \times S_2$ existe un único $(i,j)\in [n] \times [n]$ tal que $L_1(i,j) = x_1$ y $L_2(i,j) = x_2$ . Por ejemplo, los siguientes son dos cuadrados latinos ortogonales de orden 3.
Se sabe que como máximo hay $n-1$ cuadrados latinos mutuamente ortogonales de orden $n$ y que el límite se alcanza si y sólo existe un plano afín de orden $n$ .
La definición del gráfico: Estoy construyendo un gráfico $G_n$ con conjunto de vértices los cuadrados latinos de orden $n$ y dos vértices son adyacentes si los cuadrados latinos son ortogonales.
Quiero entender algunas propiedades de este gráfico. Para simplificar considero los cuadrados hasta la permutación de $[n]$ De ahí que todos mis cuadros tengan como primera línea $\{1,2,\ldots,n\}$ . De hecho, si llamo a $H_n$ el gráfico no hasta las permutaciones, entonces $H_n$ es el $n!$ ampliación del gráfico de $G_n$ o utilizando el producto tensorial $$ H_n = G_n \times K_{n!}$$ Como me interesa principalmente el número cromático de mi gráfico, y sabemos que $\chi(H_n)\leq \min\{\chi(G_n) ; n!\}$ , sólo estudiaré $G_n$ .
Por ejemplo $G_2=K_1$ , $G_3=K_2$ .
Sé que :
-
Es trivial que $G_n$ no está completa.
-
Si existe un plano afín de orden $n$ entonces $G_n$ contiene $K_{n-1}$ como un subgrafo, y $\chi(G_n)\geq n-1$ .
-
$G_4$ se compone de 2 elementos disjuntos $K_3$ y 18 vértices aislados, para un total de 24 cuadrados latinos.
-
$G_5$ se compone de 36 elementos disjuntos $K_4$ y 1200 vértices aislados, para un total de 1344 cuadrados latinos.
-
El caso $n=6$ sería el primer caso interesante, ya que no existen planzas afines de orden 6, por lo que no encontraremos $K_5$ en $G_6$ . Se sabe desde 1901 (por la comprobación a mano de Tarry de todos los cuadrados latinos de orden 6) que no hay dos cuadrados latinos de orden 6 que sean mutuamente ortogonales. Así que $G_6$ se compone únicamente de vértices aislados (con 1.128.960 vértices).
-
También se sabe que el caso $n=2$ y $n=6$ son los únicos con vértices aislados. (véase la teoría del diseño de Beth, Jingnickel y Lenz).
-
Del artículo "Monogamous Latin Square" de Danziger, Wanless y Webb, disponible en el sitio web de Wanless aquí . Los autores demuestran que para todos los $n > 6$ , si $n$ no es de la forma $2p$ para un primer $p \geq 11$ entonces existe un cuadrado latino de orden $n$ que posee una pareja ortogonal pero no está en ningún triple de cuadrados latinos mutuamente ortogonales. Por lo tanto, nuestro gráfico $G_n$ tendrá algunos aislados $K_2$
Me pregunto lo siguiente :
-
¿Cuál es el grado máximo de $G_n$ ? Sabemos que tenemos como máximo $n-1$ mutuamente cuadrados latinos ortogonales, pero ¿a cuántos cuadrados puede ser ortogonal un cuadrado (todavía depende de la permutación)?
-
¿Tenemos alguna otra información sobre el número cromático, que no provenga de la propiedad $\chi(G_n)\leq \Delta+1$ .
-
Puede $G_n$ contiene una inducción $k$ -ciclo con $k>3$ (es decir, ciclo sin cuerda)?
-
La afirmación más fuerte sería la siguiente conjetura
Conjetura para cualquier $n$ , $G_n$ es la unión disjunta de subgrafos completos (de diferentes tamaños).
O dicho de otro modo, la relación ortogonal es transitiva (cuando se restringe a nuestros cuadrados latinos con la primera fila fijada en $\{1,2,\ldots,n\}$ .
Agradecería cualquier intuición, dirección de algunos artículos o cualquier dato adicional conocido.
