grupo de permutación e índice de ciclo pregunta sobre el gráfico de peterson

Question

Una simetría del gráfico $X$ es una permutación de los vértices que resulta ser también una permutación de las aristas inducidas. En particular, las distancias entre los vértices son preservadas por una simetría. Demuestre que el conjunto de simetrías de $X$ es un grupo de permutación de $\operatorname{V}(X)$ . Calcular el índice de ciclo del grupo para el gráfico de Petersen.

Muy bien, estoy súper confundido. No tengo ni idea de cómo empezar. ¿Puede alguien indicarme la dirección correcta? ¿Cómo puedo demostrar que algo es un grupo de permutación? ¿Cómo puedo calcular el índice de ciclo de un gráfico?

Answer 1

La cuestión de cómo calcular los índices de los ciclos de los automorfismos del grafo de Petersen que actúan sobre los vértices y las aristas admite sin duda una respuesta sofisticada de la teoría de grafos en el último caso.

Sin embargo, existe una forma muy sencilla de calcular estos dos índices de ciclo que no examina todas las permutaciones posibles de los diez vértices. En su lugar, simplemente hacemos uso del hecho de que los automorfismos del Petersen se obtienen a partir de la acción del grupo simétrico $S_5$ en los subconjuntos de dos elementos del conjunto de cinco elementos cuyo intersección determina la adyacencia de dos vértices (los subconjuntos son los vértices y son adyacentes si son disjuntos). Por lo tanto sólo necesitamos iterar sobre el $120$ permutaciones en $S_5$ , que actúen sobre los vértices/aristas, factorizar el resultado en ciclos y añadir el $120$ contribuciones para obtener los índices de los ciclos.

En el primer caso obtenemos para el índice de ciclo del vértice la respuesta

$$Z(P_v) = {\frac {{a_{{1}}}^{10}}{120}}+1/12\,{a_{{1}}}^{4}{a_{{2}}}^{3}+1/ 8\,{a_{{2}}}^{4}{a_{{1}}}^{2}+1/6\,a_{{1}}{a_{{3}}}^{3}+1/6\,a_{{ 1}}a_{{6}}a_{{3}}\\+1/4\,{a_{{4}}}^{2}a_{{2}}+1/5\,{a_{{5}}}^{2}$$

Calculando las coloraciones de los vértices con un máximo de $N$ colores obtenemos el secuencia

$$1, 34, 792, 10688, 90005, 533358, 2437848, 9156288, \\ 29522961, 84293770,\ldots$$

que nos señala OEIS A063843 . Aprendemos que lo que tenemos aquí es el índice de ciclo del grupo de permutación de aristas del grafo completo $K_5,$ lo cual es perfectamente correcto, ya que las aristas de ese gráfico corresponden a los subconjuntos de dos elementos y la acción es la acción del grupo simétrico sobre los cinco vértices.

En el segundo caso obtenemos para el índice de ciclo de la arista la respuesta

$$Z(P_e) = {\frac {{a_{{1}}}^{15}}{120}}+{\frac {5\,{a_{{2}}}^{6}{a_{{1}}}^{ 3}}{24}}+1/4\,{a_{{4}}}^{3}a_{{2}}a_{{1}}+1/6\,{a_{{3}}}^{5}+1/6 \,a_{{3}}{a_{{6}}}^{2}+1/5\,{a_{{5}}}^{3}$$

conseguir para los colorantes

$$1, 396, 123786, 9002912, 254721400, 3920311044, 39571426713, \\ 293231076608, 1715840171595, 8333541708700,\ldots$$

El código de Maple para esto es el siguiente.

with(combinat);

pet\_autom2cycles :=
proc(src, aut)
local numa, numsubs;
local marks, pos, cycs, cpos, clen;

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

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

    cycs := \[\]; pos := 1;

    while pos <= nops(aut) do
        if marks\[pos\] then
            clen := 0; cpos := pos;

            while marks\[cpos\] do
                marks\[cpos\] := false;
                cpos := numa\[cpos\];
                clen := clen+1;
            od;

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

        pos := pos+1;
    od;

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

pet\_cycleind\_petersen\_verts :=
proc()
option remember;
local pet\_verts, perm, vperm, s;
    pet\_verts := convert(choose({seq(k, k=1..5)}, 2), list);

    perm := firstperm(5); s := 0;

    while type(perm, \`list\`) do
        vperm :=
        subs(\[seq(q=perm\[q\], q=1..5)\], pet\_verts);

        s := s + pet\_autom2cycles(pet\_verts, vperm);

        perm := nextperm(perm);
    od;

    s/120;
end;

pet\_cycleind\_petersen\_edges :=
proc()
option remember;
local pet\_verts, vidx1, vidx2, v1, v2, pet\_edges, perm, eperm, s;
    pet\_verts := convert(choose({seq(k, k=1..5)}, 2), list);

    pet\_edges := \[\];

    for vidx1 to 10 do
        for vidx2 from vidx1+1 to 10 do
            v1 := pet\_verts\[vidx1\]; v2 := pet\_verts\[vidx2\];

            if v1 intersect v2 = {}  then
                pet\_edges :=
                \[op(pet\_edges), {v1, v2}\];
            fi;
        od;
    od;

    perm := firstperm(5); s := 0;

    while type(perm, \`list\`) do
        eperm :=
        subs(\[seq(q=perm\[q\], q=1..5)\], pet\_edges);

        s := s + pet\_autom2cycles(pet\_edges, eperm);

        perm := nextperm(perm);
    od;

    s/120;
end;

P :=
proc(N)
    option remember;
    local idx;

    idx := pet\_cycleind\_petersen\_verts();
    subs(\[seq(x=N, x in indets(idx))\], idx);
end;

Q :=
proc(N)
    option remember;
    local idx;

    idx := pet\_cycleind\_petersen\_edges();
    subs(\[seq(x=N, x in indets(idx))\], idx);
end;

Observación. El índice de ciclo de la acción sobre los vértices a través de la acción sobre las aristas de $K_5$ del grupo simétrico aparece a través del complemento del gráfico de Petersen.