Usando el teorema de órbita-estabilizador contar gráficos

Question

La revisión de un curso en grupo y la teoría de la representación, me he encontrado con el siguiente problema interesante:

El uso de la órbita-estabilizador teorema para calcular el número de clases de isomorfismo de simple (es decir, sin dirección, sin múltiples aristas, sin bucles cortos) gráficos con $n$ vértices.

He intentado durante un tiempo, pero no he encontrado el grupo correcto para hacer acto en el $n$-gráficos de $\Gamma_n$. Mi única conclusión a la que hasta ahora es que la acción correcta de un misterioso grupo de $G$ debe conmutar con la acción de la $S_n$ haciendo los vértices conmutar (ya que los dos gráficos que se encuentran en la misma clase de equivalencia si están en la misma órbita de acción).

Cualquier sugerencias/ideas?

Answer 1

Deje $G$ ser un grupo que actúa sobre un conjunto $X$. Burnside del Lema dice que $$ |X/G| \;=\; \frac{1}{|C|} \sum_{g\in G} |X^g|, $$ donde $X/G$ es el conjunto de órbitas en $X$ bajo $G$, e $X^g$ denota el conjunto de elementos de $X$ fijado por el elemento $g$. Este lema de la siguiente manera bastante inmediato de la Órbita-Estabilizador Teorema (ver el corto de la prueba en el artículo de la Wikipedia).

El uso de Burnside del lema, no es demasiado difícil para contar las clases de isomorfismo de grafos con $n$ vértices. Deje $E$ el conjunto de $\binom{n}{2}$ aristas de un grafo completo con $n$ vértices. Entonces cualquier gráfico de $\Gamma$ $n$ vértices corresponde a un subconjunto de a $E$, es decir, una función de $f_\Gamma\colon E\to \{0,1\}$.

Dado cualquier permutación $\sigma \in S_n$ de la $n$ vértices, vamos a $\sigma_E$ la correspondiente permutación de los elementos de $E$. A continuación, un gráfico de $\Gamma$ es estabilizado por $\sigma$ si y sólo si $f_\Gamma$ es constante en los bordes de cada ciclo de $\sigma_E$. Por lo tanto, el número de gráficos estabilizado por $\Gamma$ $2^{N(\sigma_E)}$ donde $N(\sigma_E)$ indica el número de ciclos en $\sigma_E$. Por Burnside del Lema, se sigue que el número de clases de isomorfismo es $$ \frac{1}{|S_n|}\sum_{\sigma\en S_n} 2^{N(\sigma_E)} $$

Ejemplo: Vamos a calcular el número de gráficos con cuatro vértices. El grupo $S_4$ tiene cinco tipos diferentes de elementos:

1. El elemento de identidad,
2. Seis de dos ciclos,
3. Ocho de tres ciclos,
4. Seis de cuatro ciclos, y
5. Tres elementos de la forma $(*\;\;*)(*\;\;*)$

Obviamente $N(\sigma_E) = |E| = 6$ si $\sigma$ es el elemento de identidad. Si $\sigma=(1\;2)$, $\sigma_E$ tiene cuatro ciclos: $$ \sigma_E \;=\; \bigl(\{1,2\}\bigr)\;\bigl(\{1,3\}\;\;\{2,3\}\bigr)\;\bigl(\{1,4\}\;\;\{2,4\}\bigr)\;\bigl(\{3,4\}\bigr). $$ Si $\sigma = (1\;2\;3)$, $\sigma_E$ tiene dos ciclos: $$ \sigma_E \;=\; \bigl(\{1,2\}\;\;\{2,3\}\;\;\{1,3\}\bigr)\;\bigl(\{1,4\}\;\;\{2,4\}\;\;\{3,4\}\bigr). $$ Si $\sigma = (1\;2\;3\;4)$, $\sigma_E$ tiene dos ciclos: $$ \sigma_E \;=\; \bigl(\{1,2\}\;\;\{2,3\}\;\;\{3,4\}\;\;\{1,4\}\bigr)\;\bigl(\{1,3\}\;\;\{2,4\}\bigr). $$ Por último, si $\sigma=(1\;2)(3\;4)$, $\sigma_E$ tiene cuatro ciclos: $$ \sigma_E \;=\; \bigl(\{1,2\}\bigr)\;\bigl(\{3,4\}\bigr)\;\bigl(\{1,3\}\;\;\{2,4\}\bigr)\;\bigl(\{1,4\}\;\;\{2,3\}\bigr). $$ Por lo tanto, el número de clases de isomorfismo de grafos con $4$ vértices es $$ \frac{1}{|S_n|}\sum_{\sigma\en S_n} 2^{N(\sigma_E)} \;=\; \frac{2^6 + 6(2^4) + 8(2^2) + 6(2^2)+3(2^4)}{24} \;=\; 11. $$ Wikipedia tiene una buena foto de estos once clases:

Mejora: en Realidad, no es demasiado difícil encontrar una fórmula general para $N(\sigma_E)$. En particular:

• Cada una de las $k$-ciclo de $\sigma$ da lugar a $\lfloor k/2\rfloor$ órbitas de los bordes entre los vértices de la $k$-ciclo, y

• Cada una de las $\{j$-ciclo, $k$ciclo$\}$ par da lugar a $\gcd(j,k)$ órbitas de los bordes entre los vértices de los dos ciclos.

Por lo tanto, si $\sigma$ tiene ciclos de longitud $k_1,\ldots,k_m$ (incluyendo los ciclos de longitud $1$), luego $$ N(\sigma_E) \;=\; \sum_{i=1}^m \left\lfloor\frac{k_i}{2}\right\rfloor \,+\, \sum_{i<j} \gcd(k_i,k_j). $$ Por ejemplo, si $\sigma$ es el producto de $6$-ciclo, $4$- ciclo, y un $1$-ciclo, entonces $$ N(\sigma_E) \;=\; \left\lfloor\frac{6}{2}\right\rfloor + \left\lfloor\frac{4}{2}\right\rfloor + \left\lfloor\frac{1}{2}\right\rfloor + \gcd(6,4) + \gcd(6,1) + \gcd(4,1) \;=\; 9. $$

Ejemplo: Vamos a calcular el número de isomorphim clases de gráficos con la $5$ vértices. Aquí está el posible ciclo de estructuras por elementos de la $S_5$:

• $\sigma=(*)(*)(*)(*)(*)$, $1$ elemento, $N(\sigma_E) = 10$
• $\sigma=(*\;*)(*)(*)(*)$, $10$ elementos, $N(\sigma_E) = 7$
• $\sigma=(*\;*\;*)(*)(*)$, $20$ elementos, $N(\sigma_E) = 4$
• $\sigma=(*\;*\;*\;*)(*)$, $30$ elementos, $N(\sigma_E) = 3$
• $\sigma = (*\;*\;*\;*\;*)$, $24$ elementos, $N(\sigma_E) = 2$
• $\sigma = (*\;*)(*\;*)(*)$, $15$ elementos, $N(\sigma_E) = 6$
• $\sigma = (*\;*\;*)(*\;*)$, $20$ elementos, $N(\sigma_E) = 3$

Por lo tanto, el número de tipos de isomorfismo de grafos con cinco vértices es: $$ \frac{1(2^{10}) + 10(2^7) + 20(2^4) + 30(2^3) + 24(2^2) + 15(2^6) + 20(2^3)}{120} \;=\; 34. $$

Answer 2

Desea $G=S_n$ que actúa sobre las aristas del grafo completo, creo. En lugar de simplemente Órbita-Estabilizador, esta versión es generalmente llamado Pólya la enumeración teorema. Es sólo una versión de lujo de la órbita estabilizador, pero muy elegantes, en mi opinión.

El número de gráficas simples se tabularon en OEIS:A000088.

Los casos de $n=3$ $n=4$ son trabajadas en detalle en la wikipedia (página 1) y wikipedia (página 2).

En la BRECHA de álgebra computacional de software, puede utilizar el código siguiente. Para $n\leq 1$ la falta de bordes parece confundir. Hay 1 gráficos para $n=0$, 1 $n=1$. Usted puede utilizar genfunc a ordenar los gráficos por la cantidad de bordes que tienen, o sólo count a la suma de ellos. El Value función sólo sustituye los valores para cada una de las variables, $t_i =a_i \mapsto 1+t^i$ genfunc y, a continuación, $t\mapsto 1$ count.

gap> t := X(Racionales,"t":de edad);;
gap> genfunc := n -> Valor(
> CycleIndex( SymmetricGroup(n), Combinaciones([1..n],2), Inicios ),
> Lista([1..Binomial(n,2)],i->X(Racionales,i)),
> Lista([1..Binomial(n,2)],i->(1+t^i)));;
gap> count := n -> Valor( genfunc(n), [t], [1] );;
gap> Lista([2..11],count);
[ 2, 4, 11, 34, 156, 1044, 12346, 274668, 12005168, 1018997864 ]

En caso de querer utilizar Jim método, se puede calcular a a $n=20$ en el mismo tiempo, el por-la-definicion-de-PET método va a $n=11$:

gap> CountBelk := n -> Sum( Particiones(n), p ->
> 2^( Sum(p,ki->Int(ki/2)) + 
> Sum(Combinaciones([1..Tamaño(p)],2),ij->Gcd(p{ij})) )
> / Producto( Recogida(p), i_ci -> Factorial(i_ci[2]) * i_ci[1]^i_ci[2] )
> );;
gap> Lista( [2..20], CountBelk );

La extraña división de la cosa en realidad es multiplicar por el tamaño de la clase conjugacy, y toda la cosa se divide por el orden de $S_n$. Me acaba de salir el de multiplicar y dividir por Factorial(n).