"Teoría de Galois" en gráficas

Question

Sea $G = (V, E)$ un grafo. Por simplicidad, asumamos que $G$ es no dirigido y finito.

El grupo de automorfismos $\mathrm{Aut}(G)$ contiene todos los isomorfismos de grafos $\phi : G \rightarrow G$. Este grupo actúa sobre el conjunto $V$ de vértices del grafo y codifica información valiosa sobre la simetría de $G$. De hecho, $\mathrm{Aut}(G)$ también contiene automorfismos que podrían preservar una cierta clique de interés, o "acercarse" a ciertos subgrafos, o "puntos fijos" de otro tipo.

En la teoría de Galois, estamos interesados en los grupos de automorfismos de extensiones de campos. Por ejemplo, si $L$ y $F$ son campos, entonces estamos interesados en la acción de $\mathrm{Aut}(L/F)$ sobre las raíces de polinomios definidos dentro de $F[x]$ que podrían tener raíces en $L$, cómo permutan las raíces. De hecho, si $L/F$ es una extensión de Galois, tenemos una correspondencia biunívoca entre subcampos de $L/F$ y subgrupos de su grupo de automorfismos, y esto está relacionado con las propiedades de descomposición de polinomios con coeficientes en $F$, etc...

Me pregunto si hay algo en la idea de tal vez representar (o considerar) grafos mediante "polinomios" y tratar de encontrar "grafos de extensión" (las coberturas de grafos parecen ser análogas a esta idea). Las dificultades computacionales/combinatorias intrínsecas de los grafos parecerían causar problemas, pero aún así me intriga si alguien ha ideado algo al respecto.

Answer 1

En este contexto, en realidad hay un análogo exacto de la teoría de Galois, dado por la teoría de espacios de recubrimiento en topología. La teoría de espacios de recubrimiento define una versión topológica de una extensión de campo (separable) llamada espacio de recubrimiento, y especializada en grafos, los espacios de recubrimiento de un grafo son siempre grafos y se pueden definir puramente combinatoriamente: estos son grafos de recubrimiento. Se puede dar una definición de cuándo un recubrimiento es Galois y calcular los grupos Galois, y hay una correspondencia de Galois.

Todo esto se cubre en varias introducciones a la topología algebraica (que lamentablemente introducirá muchas más herramientas de las que necesitas solo para estudiar el caso especial de los grafos, que en principio es autosuficiente y puramente combinatorio). La discusión de los espacios de recubrimiento de Hatcher, por ejemplo, tiene algunas imágenes bonitas de recubrimientos de grafos, incluidos grafos infinitos.

Como ejemplo, supongamos que $X = C_n$ es el grafo cíclico con $n$ vértices, $n \ge 3$. Entonces los grafos de recubrimiento (conectados, finitos) de $X$ son exactamente los grafos cíclicos con $kn$ vértices, $k \ge 1$; los mapas de recubrimiento $C_{kn} \to C_n$ están definidos por "envolver alrededor," y tienen grupo Galois el grupo cíclico $\mathbb{Z}_k$, que controla qué recubrimientos están intermedios entre otros recubrimientos. Esto es muy similar a cómo se ve la teoría de extensiones de un campo finito, y la similitud se puede describir en términos de una similitud entre el grupo fundamental de $C_n$ (que es $\mathbb{Z}$) y el grupo de Galois absoluto de un campo finito (que son los enteros profinitos).