Clique y número cromático del gráfico de ciclo de las permutaciones

Question

Dejemos que $n>1$ sea un número entero y que $[n] = \{1,\ldots,n\}$ . Sea $S_n$ denotan el conjunto de todas las permutaciones (biyecciones) $\pi:[n]\to[n]$ . Decimos que $\psi\neq\pi\in S_n$ son un ciclo de distancia entre sí si hay un número entero $k\in[n]$ y $k$ números enteros distintos $n_1,\ldots n_k\in[n]$ tal que $$\psi = \pi \circ (n_1 \; n_2\;\cdots\; n_k) \text{ or } \psi = (n_1 \; n_2\;\cdots\; n_k) \circ \pi.$$

Dejemos que $E = \big\{\{\pi,\psi\}: \pi \neq \psi \in S_n\text{, and} \psi,\pi \text{ are a cycle away from each other}\big\}$ . Esto hace que $(S_n,E)$ en un grafo finito, simple y no dirigido.

¿Cuál es el tamaño máximo de una camarilla en $(S_n, E)$ ¿Qué es? $\chi(S_n, E)$ ¿Y estos números son iguales?

Answer 1

Resulta que para el $S_5$ gráfico el número de camarilla es $7$ pero el número cromático es $30.$ Detalles al final.

El número de ciclos es $c_n=\sum_{k=2}^{n}\binom{n}{k}(k-1)!$ Los primeros términos $(n-1)!+\frac{n(n-2)!}{2}+\frac{n(n-1)(n-3)!}3$ para ciclos de longitud $n,n-1,n-2$ son los más grandes. Esto es en realidad el grado de cada vértice en su gráfico. El problema también puede reducirse a uno sobre este número de vértices, pero con grados variables. Eso seguiría siendo una ventaja.

Sólo hay que considerar la multiplicación por un lado: Si $\pi$ es una permutación y $\sigma$ es un ciclo Entonces $\sigma'=\pi \circ \sigma \circ \pi^{-1}$ es otro ciclo del mismo tipo y $\sigma' \circ \pi = \pi \circ \sigma.$

Si $C$ es una camarilla por lo que es $\{\alpha\circ\pi \mid \pi \in C\}$ donde $\alpha$ es una permutación fija arbitraria. Así que podríamos suponer que el elemento de identidad $i$ es un miembro. Esto a su vez significa que cada elemento es un ciclo.

Aquí hay una camarilla de tamaño $13$ para $S_5$

$$ (12345)\ (12354)\ (12534)\ (13245)\ (13254)\ (14235)\ (15243)$$ $$ (132)\ (142)\ (145)\ (253)\ (345) $$ $$i$$

Los ciclos que crean aristas son exactamente los $44$ ciclos de tipo $(abc)$ y $(abcde).$ Sin embargo, algunos se utilizan $7$ veces, algunos $3$ y otros sólo una vez.

Tenga en cuenta que podríamos hacer las mismas preguntas para grupos alternativos. Este ejemplo en particular vive enteramente en $A_5.$ Tal vez haya una generalización.

Encuentro un ejemplo de tamaño $6$ en $S_4.$ Uno es $$i\ (12)\ (13)\ (14)\ (234)\ (243)$$

Dado que podemos limitarnos a la $c_n$ vértices de los ciclos, sólo hay que ver el gráfico inducido en éstos. Tal vez primero busque camarillas máximas entre los $n$ -ciclos, entonces el $n-1$ -ciclos entonces el $n-2$ -ciclos. Estos tres gráficos son regulares y tienen una alta simetría. A continuación, mira cómo se pueden combinar.

MÁS TARDE El gráfico de $S_3$ es $K_6$ por lo que el número de camarilla y el número cromático son los mismos $6.$

Di un grupo de tamaño $6$ en el $S_4$ gráfico. Para ese gráfico (regular de grado $21$ ) para tener el número cromático $6$ requeriría $6$ conjuntos independientes de tamaño $4$ . Esto ocurre. El conjunto independiente de $\pi$ es $\{\pi,\pi(12)(34),\pi(13)(24),\pi(14)(23)\}.$

Dejo el número cromático del $S_5$ gráfico a otros. Dado que este gráfico en $120$ vértices es regular de grado $84,$ Podría ser más fácil buscar camarillas en el complemento que tiene grado $35$ que conjuntos independientes en el gráfico.

Es curioso que los tamaños de las camarillas vayan $1,2,6,6,7$ para $n=1,2,3,4,5.$

ACTUALIZACIÓN Dejo que Maple busque el número cromático del $S_5$ gráfico ( $120$ vértices y $5040$ bordes) pero lo dejó después de varios días. Sin embargo, encontró un conjunto máximo independiente en un abrir y cerrar de ojos. $$i\ \ (12)(34)\ \ (13)(24)\ \ (14)(23).$$ Así que al menos $30$ se necesitan colores. Como estos cuatro elementos constituyen un subgrupo, los cosets de la izquierda de este grupo proporcionan un $30$ -Coloración.