¿De cuántas maneras se pueden pintar los bordes de un gráfico de Petersen en blanco o negro?

Question

¿De cuántas maneras distintas se puede pintar los bordes de un gráfico de Petersen blanco o negro?

Sé que el symmetrygroup de la Petersen gráfico es de $ [S5][1]$. Además, este parece un caso donde debo usar Burnside del lexema. Lo siento si el siguiente es demasiado detallado o usos no estándar de notación; no he estado familiarizado con la teoría de grafos.

S5 tiene 7 clases conjugacy, es decir, aquellas con el ciclo de los tipos de: (1,1,1,1,1),(1,1,1,2),(2,2,1),(2,3),(1,1,1,3),(4,1),(5). S5 tiene 15 bordes para que la identidad (1,1,1,1,1) dejaría $2^{15}$ diferentes colorantes fijos. La n-ciclo (5) es una rotación de todo el gráfico y, como tal dejaría $2^3$ colorantes fijos. El "afuera" puede ser blanco o negro, los bordes de conexión y el "interior" de los bordes de ambos podrían ser o blanco o negro. Rotación alrededor de una "conexión" borde implica la (2,2,1) ciclos. Yo no se cansará con los detalles, pero me encontré $2^9$ colorantes.

A partir de aquí yo estoy atascado sin embargo, no puedo encontrar más simetrías de estos. ¿Cómo puedo encontrar los colorantes izquierda fijado por las otras clases conjugacy?

Answer 1

Espero que pueda ser de ayuda aquí, aunque mi enfoque no es el más sofisticado. He escrito un Arce programa para el cálculo de la acción de la automorphism grupo $G$ de la Petersen gráfico en uno de sus bordes (dando el borde de permutación grupo $Q$), utilizando las propiedades que están documentadas en la Wikipedia. Mi vértices son el número de pares que pueden ser elegidos desde $\{1, 2, 3, 4, 5\}$. He utilizado un método de fuerza bruta ir a través de todos los vértices de permutaciones y de comprobar que conservan la propiedad de que dos vértices son adyacentes si los dos pares de números son distintos, es decir, el Kneser gráfico de la propiedad del gráfico de Petersen. Que los rendimientos de la automorphism grupo $G$ de los vértices. A la conclusión de aplicar cada permutación de $G$ a los bordes, con lo que la obtención de $Q$ y su ciclo de índice. En este momento es para sustituir a $x+y$ en el ciclo según el índice Polya del teorema para obtener la generación de la función de las órbitas. Hay $396$ de ellos.

Este es el ciclo de índice: $A$Z(P) = {\frac {1}{120}}\,{a_{{1}}}^{15}+{\frac {5}{24}}\,{a_{{2}}}^{6}{a_{{1}}}^ {3}+1/6\,{a_{{3}}}^{5}+1/6\,a_{{3}}{a_{{6}}}^{2}+1/4\,{a_{{4}}}^{3}a_{{2} }a_{{1}}+1/5\,{a_{{5}}}^{3}.$$

Sustituyendo $x+y$ a $Z(Q)$ rendimientos $A$Z(Q)_{x+y} = {\frac {1}{120}}\, \a la izquierda( x+y \right) ^{15}+{\frac {5}{24}}\, \a la izquierda( {x}^ {2}+{y}^{2} \right) ^{6} \left( x+y \right) ^{3}\\ +1/6\, \a la izquierda( {x}^{3}+{y} ^{3} \right) ^{5}+1/6\, \a la izquierda( {x}^{3}+{y}^{3} \right) \left( {x}^{6}+{y }^{6} \right) ^{2} \\ +1/4\, \a la izquierda( {x}^{4}+{y}^{4} \right) ^{3} \left( {x}^{ 2}+{y}^{2} \right) \left( x+y \right) +1/5\, \left( {x}^{5}+{y}^{5} \right) ^{3}.$$

La expansión nos encontramos con la generación de la función que clasifica el borde colorantes de acuerdo con los dos colores: $A$Z(Q)_{x+y} = {x}^{15}+{x}^{14}y+3\,{x}^{13}{y}^{2}+9\,{x}^{12}{y}^{3}+19\,{x}^{11} de{y}^ {4}+37\,{x}^{10}{y}^{5}+58\,{x}^{9}{y}^{6}+70\,{x}^{8}{y}^{7}\\ +70\,{x}^{7} {y}^{8}+58\,{x}^{6}{y}^{9}+37\,{x}^{5}{y}^{10}+19\,{x}^{4}{y}^{11}+9\,{x} ^{3}{y}^{12}+3\,{x}^{2}{y}^{13}+x{y}^{14}+{y}^{15}.$$

Establecimiento $x=1$ $y=1$ nos encontramos con que el número total es igual a $$396.$$

El Arce programa de la siguiente manera para todos los grupos de la teoría de los entusiastas de la que también son programadores! Si hay preguntas concretas en cuanto a lo que las funciones individuales, ¿estaré encantado de responder a ellos. También puedo enviar el programa si hay problemas con el formato. ¡A disfrutar! Los comentarios son bienvenidos.

con(grupo):
con(planta):

pet_verts := convertir(a elegir({sec(k, k=1..5)}, 2), lista);

pet_edges_set := {};

para v1 en pet_verts ¿
 para la v2 en pet_verts ¿
 si v1 cruzan v2 = {}, a continuación,
 pet_edges_set := pet_edges_set unión {{v1, v2}};
 fi; 
od;
od;

pet_edges := convert(pet_edges_set, lista);

pet_is_autom :=
proc(vperm)
 local allsubs, e, eperm, el; 

 allsubs := 
 [seq(pet_verts[pos]=vperm[pos], pos=1..nops(vperm))];

 eperm := subs(allsubs, pet_edges);

 para el correo en eperm ¿
 el := convert(e, lista);
 si el[1] se cruzan el[2] <> {} a continuación
 return false;
 fi; 
od;

 return true;
end;

pet_vautom := [];

pet_compute_vautom :=
proc()
 opción de recordar;

 global pet_vautom;

 local vperm, pos, conde;

 count := 0;
 para vperm en permutar(pet_verts) ¿
 si pet_is_autom(vperm), a continuación,
 count := contador+1; 
 printf("automorphism %d\n", cuenta);

 pet_vautom := [op(pet_vautom), vperm];
fi;
od;

pet_vautom;
end;
pet_compute_vautom();


pet_autom2cycles :=
proc(src, aut)
 numa local, numsubs;
 local de marcas, pos, cycs, cpos, clen;

 numsubs := [seq(src[k]=k, k=1..nops(src))];
 numa := subs(numsubs, aut);

 marcas := [seq(true, pos=1..nops(aut))];

 cycs := []; pos := 1;

 mientras pos <= nops(aut) 
 si las marcas[pos] 
 clen := 0; cpos := pos;

 mientras que las marcas[cpos] ¿
 marcas[cpos] := false;
 cpos := numa[cpos];
 clen := clen+1;
od;

 cycs := [op(cycs), clen];
fi;

 pos := pos+1;
od;

 volver mul(a[cycs[k]], k=1..nops(cycs));
end;

pet_vperm2eperm :=
proc(vperm)
 local allsubs, e, eperm, el; 

 allsubs := 
 [seq(pet_verts[pos]=vperm[pos], pos=1..nops(vperm))];

 retorno de subrutina(allsubs, pet_edges);
end;

pet_cycleind := 
proc()
 local vperm, eperm, s;

 s := 0;

 para vperm en pet_vautom ¿
 eperm := pet_vperm2eperm(vperm);
 s := s + pet_autom2cycles(pet_edges, eperm);
od;

s/nops(pet_vautom);
end;

pet_varinto_cind :=
proc(poli, ind)
 local subs1, subs2, polyvars, indvars, v, bote, res;

 res := ind;

 polyvars := indets(poli);
 indvars := indets(ind);

 para v en indvars ¿
 bote := op(1, v);

 subs1 := 
 [seq(polyvars[k]=polyvars[k]^olla, 
k=1..nops(polyvars))];

 subs2 := [v=subs(subs1, poli)];

 res := subs(subs2, res);
od;

res;
end;

pet_cycleind();
látex(%);

gf := pet_varinto_cind(x+y, pet_cycleind());

látex(gf);

látex(expand(gf));

subs({x=1, y=1}, gf);

Answer 2

El uso de Burnside del lexema es la idea correcta.

Cada elemento de a $S_5$ determina una permutación de los 15 a los bordes de la Petersen gráfico. Si esta permutación tiene exactamente $r$ ciclos en los bordes, a continuación, se corrige exactamente $2^r$ 2-el color del borde del conjunto. Si $a$ $b$ son conjugar elementos de $S_5$, luego las permutaciones de los bordes ellos determinan que tienen la misma estructura del ciclo. (Para esta prueba, se observa que la inducida por las permutaciones son conjugado en $S_{15}$, y por lo tanto tienen la misma estructura del ciclo.)

Tan sólo tienes que calcular $r$ para uno de los elementos en cada clase conjugacy, que es ligeramente tedioso en el peor de los casos, y, a continuación, aplicar Burnside.