Estoy trabajando con grupos de automorfismos de grafos y tengo un problema para entender el producto trenzado de dos grupos. También me gustaría ver algunos ejemplos de grafos, además de Kn,n, cuyo grupo de automorfismo incluya el producto trenzado de Sn.
Respuesta
¿Demasiados anuncios?
Jonik
Puntos
7937
Versión corta: El producto de corona tiene dos partes, el remolino local y el remolino global. Suponiendo que queremos que tanto el remolino local como el global sean grupos simétricos completos (en n y m puntos), solo hay dos posibles gráficos finales por tamaño de local y global. El local puede ser discreto y el global completo, dando el gráfico completo m-partito con n vértices por color, o el local puede ser completo y el global discreto dando la unión disjunta de m copias del gráfico completo en n vértices.
Productos de corona en general: Tienes un gráfico con m subconjuntos de n vértices, cada uno de un color diferente. Los remolinos locales no cambian de color. Los remolinos globales cambian de color, pero realmente no intentamos decidir qué hacen "localmente" ya que quién puede decir realmente qué vértice rojo corresponde a qué vértice azul. Dado que podemos cambiar de color, usualmente solo mencionamos el remolino local de un solo color. Dado que no intentamos identificar vértices de diferentes colores, usualmente solo describimos el remolino global en lo que hace a los colores (en lugar de a los vértices individuales).
Por ejemplo, un remolino local podría llevar a los vértices rojos $\color{red}{a}$ a $\color{red}{b}$ a $\color{red}{a}$ y dejar $\color{red}{c}$ quieto (y dejar todos los azules y verdes igual), mientras que un remolino global podría llevar rojos a azules a rojos y dejar verdes quietos, tal vez específicamente $\color{red}{a}$ a $\color{blue}{a}$ a $\color{red}{a}$, $\color{red}{b}$ a $\color{blue}{b}$ a $\color{red}{b}$, $\color{red}{c}$ a $\color{blue}{c}$ a $\color{red}{c}$, etc.
Especialización en grupos simétricos: Una vez que requerimos que los remolinos locales y globales sean grupos simétricos completos, las posibilidades se reducen considerablemente. Existen exactamente dos gráficos distintos cuyo grupo de automorfismos es el grupo simétrico completo: el gráfico nulo/discreto sin aristas y el gráfico completo con todas las aristas. Si tomamos uno para la estructura local, necesitamos tomar el otro para la estructura global para evitar obtener el grupo simétrico completo en lugar del producto de corona.
La primera combinación con la que ya estás familiarizado es el gráfico completo m-partito: Toma m copias del gráfico discreto como los gráficos locales, y trata cada gráfico local como un solo vértice en el gráfico global, que es un gráfico completo. En otras palabras, de los mn vértices involucrados, organízalos en m colecciones de n cada una. Dentro de cada colección no hay aristas, pero entre colecciones hay todas las aristas posibles. El remolino local es el grupo simétrico completo en los n vértices involucrados, ya que no hay nada que distinga los vértices de un solo color entre sí. El remolino global es el grupo simétrico en los m gráficos locales (eligendo cualquier isomorfismo particular entre los gráficos locales) ya que no hay nada que distinga un gráfico local de otro.
En el caso m = 2, este es el gráfico bipartito completo. Hay dos colores, rojo y azul, y los vértices rojos forman un gráfico local que es discreto (sin aristas entre vértices rojos), y los vértices azules forman un gráfico local que es discreto (sin aristas entre vértices azules), pero si imaginas todos los vértices rojos aplastados en un super-vértice rojo y todos los vértices azules aplastados en un super-vértice azul, entonces lo que queda es el gráfico completo en dos super-vértices. Los remolinos locales llevan rojos a rojos y azules a azules. Los remolinos globales intercambian colores (así que cada rojo va a un azul, y cada azul va a un rojo).
La segunda combinación es un poco tonta: la unión disjunta de gráficos completos. En este caso, los gráficos locales son m copias de los gráficos completos en n vértices, y el gráfico global es el gráfico discreto sin aristas y m super-vértices. Un vértice rojo está unido a cada vértice rojo, pero a ningún vértice azul. Si colapsas los vértices rojos a un super-vértice rojo y los vértices azules a un super-vértice azul, entonces el resultado es el gráfico discreto con un super-vértice rojo y un super-vértice azul que no están conectados en absoluto. Los remolinos locales llevan vértices rojos a vértices rojos, y vértices azules a vértices azules. Los remolinos globales cambian colores (todos los rojos van a azules, todos los azules van a rojos).
Gráficos con grupos de automorfismos más grandes:
Existen otras dos formas de combinar local con global: (1) discreto con discreto da un gráfico discreto gigante con el grupo simétrico completo en mn puntos como su grupo de automorfismos, y (2) completo con completo da un gráfico completo gigante con el grupo simétrico completo en mn puntos como su grupo de automorfismos.
Estos son los únicos cuatro gráficos cuyo grupo de automorfismos contiene el producto de corona imprimitivo de dos grupos simétricos, y solo los dos primeros "mixtos" tienen un grupo de automorfismos exactamente igual a ese producto de corona.
