Simetrías de un grafo

Question

Determina el número de simetrías de la siguiente gráfica:

¿Qué hay que hacer en general para encontrar tales simetrías? Normalmente las etiquetaría todas de $1...n$ y anotar su valencia mentalmente

Sin embargo, sigo sin tener claro cómo progresaría. Pensé que podía permutar el punto 1 a cualquiera de los otros puntos con valencia tres, pero me han dicho que no se puede, aunque todavía no estoy seguro de por qué.

¿Podría alguien explicarlo?

Así que tomando el hecho de que el punto 1 tiene que ser fijo, se dijo entonces que había $3!$ permutaciones de los puntos exteriores (los puntos que salen del punto 1 (2,5,8)) y para cada uno de esos puntos exteriores, $2!$ permutaciones de los puntos unidos a ellos (es decir, para el punto 2, habría $2!$ permutaciones de 3 y 4)

¿Por qué, por ejemplo, los puntos 3 y 4 sólo pueden reordenarse y el 3 no podría permutarse, por ejemplo, con el punto 10? Ambos tienen la misma valencia, sólo que no tengo muy claro por qué no se puede.

Muchas gracias.

Answer 1

No basta con mirar las valencias. Una reordenación de las etiquetas sólo es una simetría si las etiquetas que antes estaban conectadas por un borde siguen conectadas después, y las etiquetas que antes estaban desconectadas siguen sin estarlo después. Esto preservará las valencias, pero no todos los mapas que preservan las valencias son simetrías.

Por ejemplo, considere este gráfico:

Aquí hay dos simetrías: se puede tener $ABCDE\to ABCDE$ o puedes darle la vuelta a todo, $ABCDE\to EDCBA$ . $B$ y $D$ están en posiciones simétricas, y hay una simetría que toma $B\to D$ y $D\to B$ . Pero no hay simetría que lleve $C\to D$ aunque ambos tengan valencia 2. $C$ está en el centro de la línea, y $D$ no lo es. Esto debería concordar con la idea de "simetría" que tenías antes de tomar esta clase.

En tu gráfico original, el punto 3 puede ir a 10, pero si lo hace, el punto 2, al que está unido, debe ir a 8, que está unido a 10. Entonces el punto 4, que también está unido al 2, debe ir al 9.

Así que una vez que has decidido que 2 va a 8, sabes que 3 y 4, que estaban unidos a 2, deben ir a 9 y 10, que están unidos a 8. Puedes elegir si $3\to9\atop 4\to 10$ o $3\to 10\atop 4\to 9$ pero esa es la única opción adicional que tienes sobre el 3 y el 4.

Como has observado, 1 debe ir a 1. (Más adelante veremos por qué.) Luego 2, 5 y 8 deben ir a 2, 5 y 8, pero cada uno de ellos podría ir a cualquiera de los otros, así que hay 6 opciones sobre cómo ordenarlos. Digamos que tenemos $(2,5,8)\to(8,2,5)$ sólo como ejemplo. Entonces 3 y 4, que estaban unidas a 2 antes, deben estar unidas a 8 después, por lo que deben ir a 9 y 10. Puede elegir si $$\begin{align}& 3\to9, & 4\to 10,\\ \text{ or } & 3\to 10,& 4\to 9,\end{align}$$ como en el párrafo anterior. Entonces, de forma similar, puede elegir si $$\begin{align}& 6\to3, & 7\to 4,\\ \text{ or } & 6\to 4,& 7\to 3,\end{align}$$ y puede elegir si $$\begin{align}& 9\to6, & 10\to 7,\\ \text{ or } & 9\to 7,& 10\to 6.\end{align}$$

Eso significa que después de elegir una de las seis formas de mapear $2,5,8$ En el caso de las horquillas en los extremos de los brazos, puede elegir entre tres opciones independientes. Cada opción tiene dos caminos posibles, por lo que el número total de opciones es $3!\cdot2!\cdot2!\cdot2! = 48$ y esa es la respuesta.

---

Ahora usted dijo que no está seguro de por qué debemos tener $1\to 1$ . Probemos $1\to 5$ a ver qué pasa. Dado que 1 está unido a 258, y 5 está unido a 167 debemos tener cada uno de 258 va a algo en 167. Pero 258 todos tienen valencia 3 mientras que 6 y 7 tienen valencia sólo 1, por lo que no hay nada que pueda ir correctamente a 6 o 7. Así que $1\to 5$ nunca funcionará. Y 2 y 8 se parecen a 5, así que $1\to 2$ y $1\to 8$ fallará esencialmente por la misma razón.

Answer 2

Consideremos la utilización del lema del estabilizador orbital, que establece que: si $G \le Sym(V)$ es un grupo de permutaciones que actúa sobre $V$ y $v \in V$ entonces $|G|=|v^G|~|G_v|$ . Aquí $v^G$ es la órbita de $v$ bajo la acción de $G$ y el estabilizador $G_v$ es el conjunto de elementos de $G$ que arreglan $v$ .

Por lo tanto, para encontrar el tamaño del grupo de automorfismo $G$ del árbol anterior, elige un vértice $v$ , digamos $v=1$ y hallar el número de vértices a los que se puede asignar 1 mediante un automorfismo del árbol y hallar el número de automorfismos que fijan el vértice 1. En este caso, el vértice 1 es el centro de este árbol y por lo tanto debe ser fijado por cada automorfismo (los automorfismos preservan las distancias, y cada camino más largo en el árbol tiene el vértice 1 como su punto medio). Así pues, $|v^G|=1$ . Un automorfismo que fija un vértice debe permutar sus vecinos entre sí, por lo que todo automorfismo debe inducir una permutación de $\{2,5,8\}$ . Además, todos $3!$ permutaciones de estos vecinos son posibles. Obsérvese que el número de automorfismos que fijan el vértice 1 y cada uno de sus vecinos 2, 5 y 8, es $2^3=8$ . Por lo tanto, el número total de automorfismos de este grafo es el producto $3!~ 2^3=48$ .

Answer 3

Hay varios significados que se pueden dar a "simetrías de la gráfica siguiente". Se puede interpretar como automorfismos del grafo, pero también se puede pensar en las simetrías del "dibujo" del grafo en el plano. En este caso el grafo es un árbol por lo que existe un dibujo en el plano sin cruces de este grafo, tal y como se dibuja en la figura. Sin embargo, para los dibujos a menudo se tiene en cuenta que el diagrama es métrico y no combinatorio. Consideremos, por ejemplo, el grafo completo de 4 vértices. Este grafo tiene 24 simetrías o automorfismos. También tiene dos dibujos métricos "naturales" en el plano. Uno es un cuadrado con sus diagonales, que tiene 8 simetrías. Nótese que este dibujo no es un grafo plano ya que las diagonales se cruzan en un punto que no es un vértice del grafo. También se puede utilizar el dibujo formado por un triángulo equilátero y su centroide unido a los vértices. Este es un dibujo plano pero sólo tiene 6 simetrías.