Contar las coloraciones de los bordes de $K_n$ está estrechamente relacionado con el recuento de cuadrados latinos simétricos. De hecho, demostraré que si $S_n$ denota el número de simétricos $n \times n$ Los cuadrados latinos (matrices simétricas con entradas en el conjunto $\{1,2,\dots,n-1\}$ donde cada fila y cada columna incluye cada valor exactamente una vez), entonces el número de coloraciones de borde adecuadas mínimas de $K_n$ es igual a $S_{n-1}$ cuando $n$ es par y $S_n$ cuando $n$ es impar.
Este documento muestra que $S_n$ el número de simétricos $n \times n$ cuadrados latinos, satisface $$S_n \sim n! \cdot n^{\frac38 n^2}$$ para impar $n$ que da al menos una respuesta asintótica a su pregunta también.
Cuando $n$ es impar, una coloración de borde propia mínima de $K_n$ utiliza $n$ colores, cada uno de los cuales aparece en $\frac{n-1}{2}$ aristas, y por tanto en cada vértice se deja un color fuera. Definimos un mapa desde estas coloraciones de aristas a $n \times n$ cuadrados latinos simétricos de la siguiente manera:
- Asignar valores $1, 2, \dots, n$ a los colores.
- Para $1 \le i < j \le n$ , ponga el color de la arista entre $i$ y $j$ en el $(i,j)^{\text{th}}$ entrada de la plaza latina.
- Para $1 \le i \le n$ , poner el color que no aparece en el vértice $i$ en el $(i,i)^{\text{th}}$ entrada de la plaza latina.
El resultado es un cuadrado latino simétrico, y la inversión de este proceso siempre produce una coloración de aristas adecuada mínima. Así que el número de coloraciones es $S_n$ .
Incluso para $n$ podemos reducir simplemente a la $(n-1)$ -de vértices dejando fuera un vértice. La coloración resultante es siempre una coloración de aristas propia mínima de $K_{n-1}$ y siempre podemos deducir cuáles debían ser los colores de los bordes eliminados, e invertir este proceso. Así que el número de coloraciones es $S_{n-1}$ .
