Fin (teoría de grafos)

En las matemáticas de grafos infinitos , un extremo de un grafo representa, intuitivamente, una dirección en la que el grafo se extiende hasta el infinito. Los extremos pueden formalizarse matemáticamente como clases de equivalencia de caminos infinitos , como refugios que describen estrategias para juegos de persecución-evasión en el grafo o (en el caso de grafos localmente finitos) como extremos topológicos de espacios topológicos asociados con el grafo.

Los extremos de los grafos se pueden utilizar (a través de los grafos de Cayley ) para definir los extremos de grupos finitamente generados . Los grupos infinitos finitamente generados tienen uno, dos o infinitos extremos, y el teorema de Stallings sobre los extremos de los grupos proporciona una descomposición para grupos con más de un extremo.

Definición y caracterización

Los extremos de los grafos fueron definidos por Rudolf Halin  (1964) en términos de clases de equivalencia de caminos infinitos. ^[1]Un rayo en un grafo infinito es uncamino simple; es decir, es una secuencia infinita de vérticesen la que cada vértice aparece como máximo una vez en la secuencia y cada dos vértices consecutivos en la secuencia son los dos puntos finales de una arista en el grafo. Según la definición de Halin, dos rayosyson equivalentes si hay un rayo(que puede ser igual a uno de los dos rayos dados) que contiene infinitos vértices en cada uno dey. Esta es unarelación de equivalencia: cada rayo es equivalente a sí mismo, la definición es simétrica con respecto al ordenamiento de los dos rayos y se puede demostrar que estransitiva. Por lo tanto, divide el conjunto de todos los rayos enclases de equivalencia, y Halin definió un extremo como una de estas clases de equivalencia.^[2] ${\displaystyle v_{0},v_{1},v_{2},\dots }$ ${\displaystyle r_{0}}$ ${\displaystyle r_{1}}$ ${\displaystyle r_{2}}$ ${\displaystyle r_{0}}$ ${\displaystyle r_{1}}$

También se ha utilizado una definición alternativa de la misma relación de equivalencia: dos rayos y son equivalentes si no hay un conjunto finito de vértices que separe infinitos vértices de de infinitos vértices de . ^[3] Esto es equivalente a la definición de Halin: si el rayo de la definición de Halin existe, entonces cualquier separador debe contener infinitos puntos de y por lo tanto no puede ser finito, y a la inversa, si no existe, entonces un camino que alterna entre y hasta que no sean posibles más alternancias debe formar el separador finito deseado. ${\displaystyle r_{0}}$ ${\displaystyle r_{1}}$ ${\displaystyle X}$ ${\displaystyle r_{0}}$ ${\displaystyle r_{1}}$ ${\displaystyle r_{2}}$ ${\displaystyle r_{2}}$ ${\displaystyle r_{2}}$ ${\displaystyle r_{0}}$ ${\displaystyle r_{1}}$

Los extremos también tienen una caracterización más concreta en términos de refugios , funciones que describen estrategias de evasión para juegos de persecución-evasión en un grafo . ^[4] En el juego en cuestión, un ladrón está tratando de evadir a un conjunto de policías moviéndose de vértice a vértice a lo largo de los bordes de . La policía tiene helicópteros y, por lo tanto, no necesita seguir los bordes; sin embargo, el ladrón puede ver venir a la policía y puede elegir dónde moverse a continuación antes de que los helicópteros aterricen. Un refugio es una función que asigna cada conjunto de ubicaciones de la policía a uno de los componentes conectados del subgrafo formado al eliminar ; un ladrón puede evadir a la policía moviéndose en cada ronda del juego a un vértice dentro de este componente. Los refugios deben satisfacer una propiedad de consistencia (que corresponde al requisito de que el ladrón no puede moverse a través de vértices en los que la policía ya ha aterrizado): si es un subconjunto de , y ambos y son conjuntos válidos de ubicaciones para el conjunto dado de policías, entonces debe ser un superconjunto de . Un refugio tiene orden si la colección de posiciones policiales para las que proporciona una estrategia de escape incluye todos los subconjuntos de menos de vértices en el grafo; en particular, tiene orden (el número aleph más pequeño ) si asigna cada subconjunto finito de vértices a un componente de . Cada rayo en corresponde a un refugio de orden , es decir, la función ; que asigna cada conjunto finito al componente único de que contiene infinitos vértices del rayo. A la inversa, cada refugio de orden puede definirse de esta manera por un rayo. ^[5] Dos rayos son equivalentes si y solo si definen el mismo refugio, por lo que los extremos de un grafo están en correspondencia biunívoca con sus refugios de orden . ^[4] ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle \beta }$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle \beta (X)}$ ${\displaystyle \beta (Y)}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle \aleph _{0}}$ ${\displaystyle X}$ ${\displaystyle G\setminus X}$ ${\displaystyle G}$ ${\displaystyle \aleph _{0}}$ ${\displaystyle \beta }$ ${\displaystyle X}$ ${\displaystyle G\setminus X}$ ${\displaystyle \aleph _{0}}$ ${\displaystyle \aleph _{0}}$

Ejemplos

Parte de un grafo de cuadrícula infinita , con vértices en los puntos donde se encuentran dos líneas de cuadrícula. A pesar de tener muchos rayos diferentes, solo tiene un extremo.

Si el grafo infinito es en sí mismo un rayo, entonces tiene infinitos subgrafos de rayos, uno que comienza en cada vértice de . Sin embargo, todos estos rayos son equivalentes entre sí, por lo que solo tiene un extremo. ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$

Si es un bosque (es decir, un grafo sin ciclos finitos), entonces la intersección de dos rayos cualesquiera es un camino o un rayo; dos rayos son equivalentes si su intersección es un rayo. Si se elige un vértice base en cada componente conexo de , entonces cada extremo de contiene un rayo único que comienza en uno de los vértices base, por lo que los extremos pueden colocarse en correspondencia uno a uno con estos rayos canónicos. Todo grafo contable tiene un bosque de expansión con el mismo conjunto de extremos que . ^[6] Sin embargo, existen grafos incontablemente infinitos con un solo extremo en los que cada árbol de expansión tiene infinitos extremos. ^[7] ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$

Si es un grafo de cuadrícula infinita , entonces tiene muchos rayos y conjuntos arbitrariamente grandes de rayos disjuntos en sus vértices. Sin embargo, tiene un solo extremo. Esto se puede ver más fácilmente utilizando la caracterización de los extremos en términos de refugios: la eliminación de cualquier conjunto finito de vértices deja exactamente un componente infinito conectado, por lo que solo hay un refugio (el que asigna cada conjunto finito al único componente infinito conectado). ${\displaystyle G}$

Relación con los fines topológicos

En la topología de conjuntos puntuales , existe un concepto de extremo que es similar, pero no exactamente igual, al concepto de extremo en la teoría de grafos, que se remonta a mucho antes, a Freudenthal (1931). Si un espacio topológico puede ser cubierto por una secuencia anidada de conjuntos compactos , entonces un extremo del espacio es una secuencia de componentes de los complementos de los conjuntos compactos. Esta definición no depende de la elección de los conjuntos compactos: los extremos definidos por una de esas elecciones pueden colocarse en correspondencia biunívoca con los extremos definidos por cualquier otra elección. ${\displaystyle \kappa _{0}\subset \kappa _{1}\subset \kappa _{2}\dots }$ ${\displaystyle U_{0}\supset U_{1}\supset U_{2}\dots }$

Un gráfico infinito puede convertirse en un espacio topológico de dos maneras diferentes pero relacionadas: ${\displaystyle G}$

• Reemplazar cada vértice del gráfico por un punto y cada borde del gráfico por un intervalo unitario abierto produce un espacio de Hausdorff a partir del gráfico en el que un conjunto se define como abierto siempre que cada intersección de con un borde del gráfico sea un subconjunto abierto del intervalo unitario. ${\displaystyle S}$ ${\displaystyle S}$
• Reemplazar cada vértice del gráfico por un punto y cada arista del gráfico por un punto produce un espacio no Hausdorff en el que los conjuntos abiertos son los conjuntos con la propiedad de que, si un vértice de pertenece a , entonces también lo hace cada arista que tiene como uno de sus puntos finales. ${\displaystyle S}$ ${\displaystyle v}$ ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle v}$

En cualquier caso, cada subgrafo finito de corresponde a un subespacio compacto del espacio topológico, y cada subespacio compacto corresponde a un subgrafo finito junto con, en el caso de Hausdorff, un número finito de subconjuntos compactos propios de aristas. Por lo tanto, un grafo puede estar cubierto por una secuencia anidada de conjuntos compactos si y solo si es localmente finito, con un número finito de aristas en cada vértice. ${\displaystyle G}$

Si un grafo es conexo y localmente finito, entonces tiene una cubierta compacta en la que el conjunto es el conjunto de vértices a distancia como máximo de algún vértice inicial elegido arbitrariamente. En este caso cualquier refugio define un extremo del espacio topológico en el que . Y a la inversa, si es un extremo del espacio topológico definido a partir de , define un refugio en el que es el componente que contiene a , donde es cualquier número lo suficientemente grande como para contener a . Por lo tanto, para grafos conexos y localmente finitos, los extremos topológicos están en correspondencia biunívoca con los extremos de la teoría de grafos. ^[8] ${\displaystyle G}$ ${\displaystyle \kappa _{i}}$ ${\displaystyle i}$ ${\displaystyle \beta }$ ${\displaystyle U_{i}=\beta (\kappa _{i})}$ ${\displaystyle U_{0}\supset U_{1}\supset U_{2}\dots }$ ${\displaystyle G}$ ${\displaystyle \beta (X)}$ ${\displaystyle U_{i}}$ ${\displaystyle i}$ ${\displaystyle \kappa _{i}}$ ${\displaystyle X}$

Para los grafos que no sean localmente finitos, todavía es posible definir un espacio topológico a partir del grafo y sus extremos. Este espacio puede representarse como un espacio métrico si y solo si el grafo tiene un árbol de expansión normal , un árbol de expansión con raíz tal que cada arista del grafo conecta un par ancestro-descendiente. Si existe un árbol de expansión normal, tiene el mismo conjunto de extremos que el grafo dado: cada extremo del grafo debe contener exactamente un camino infinito en el árbol. ^[9]

Tipos especiales de extremos

Extremos libres

Un extremo de un grafo se define como un extremo libre si existe un conjunto finito de vértices con la propiedad de que se separa de todos los demás extremos del grafo. (Es decir, en términos de refugios, es disjunto de para cada otro extremo .) En un grafo con un número finito de extremos, cada extremo debe ser libre. Halin (1964) demuestra que, si tiene un número infinito de extremos, entonces o bien existe un extremo que no es libre, o bien existe una familia infinita de rayos que comparten un vértice inicial común y que, por lo demás, son disjuntos entre sí. ${\displaystyle E}$ ${\displaystyle G}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle E}$ ${\displaystyle \beta _{E}(X)}$ ${\displaystyle \beta _{D}(X)}$ ${\displaystyle D}$ ${\displaystyle G}$

Extremos gruesos

Un extremo grueso de un grafo es un extremo que contiene una cantidad infinita de rayos disjuntos por pares . El teorema de la cuadrícula de Halin caracteriza a los grafos que contienen extremos gruesos: son exactamente los grafos que tienen una subdivisión del mosaico hexagonal como subgrafo. ^[10] ${\displaystyle G}$

Tipos especiales de gráficos

Grafos simétricos y casi simétricos

Mohar (1991) define un grafo localmente finito conexo como "casi simétrico" si existe un vértice y un número tales que, para cada otro vértice , hay un automorfismo del grafo para el cual la imagen de está dentro de la distancia de ; equivalentemente, un grafo localmente finito conexo es casi simétrico si su grupo de automorfismos tiene un número finito de órbitas. Como muestra, para cada grafo localmente finito conexo casi simétrico, el número de extremos es como máximo dos o incontable; si es incontable, los extremos tienen la topología de un conjunto de Cantor . Además, Mohar muestra que el número de extremos controla la constante de Cheeger donde abarca todos los conjuntos finitos no vacíos de vértices del grafo y donde denota el conjunto de aristas con un punto final en . Para grafos casi simétricos con un número incontable de extremos, ; sin embargo, para grafos casi simétricos con solo dos extremos, . ${\displaystyle v}$ ${\displaystyle D}$ ${\displaystyle w}$ ${\displaystyle v}$ ${\displaystyle D}$ ${\displaystyle w}$ $${\displaystyle h=\inf \left\{{\frac {|\partial V|}{|V|}}\right\},}$$ ${\displaystyle V}$ ${\displaystyle \partial V}$ ${\displaystyle V}$ ${\displaystyle h>0}$ ${\displaystyle h=0}$

Gráficas de Cayley

El gráfico de Cayley del grupo libre sobre dos generadores y . Los extremos del grupo están en correspondencia biunívoca con los rayos (caminos infinitos) desde el elemento identidad hasta las franjas del dibujo. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle e}$

Cada grupo y un conjunto de generadores para el grupo determinan un grafo de Cayley , un grafo cuyos vértices son los elementos del grupo y las aristas son pares de elementos donde es uno de los generadores. En el caso de un grupo finitamente generado , los extremos del grupo se definen como los extremos del grafo de Cayley para el conjunto finito de generadores; esta definición es invariante bajo la elección de generadores, en el sentido de que si se eligen dos conjuntos finitos diferentes de generadores, los extremos de los dos grafos de Cayley están en correspondencia uno a uno entre sí. ${\displaystyle (x,gx)}$ ${\displaystyle g}$

Por ejemplo, cada grupo libre tiene un gráfico de Cayley (para sus generadores libres) que es un árbol. El grupo libre de un generador tiene un camino doblemente infinito como su gráfico de Cayley, con dos extremos. Todos los demás grupos libres tienen infinitos extremos.

Todo grupo infinito finitamente generado tiene 1, 2 o infinitos extremos, y el teorema de Stallings sobre los extremos de los grupos proporciona una descomposición de los grupos con más de un extremo. ^[11] En particular:

1. Un grupo infinito generado finitamente tiene 2 extremos si y sólo si tiene un subgrupo cíclico de índice finito .
2. Un grupo infinito finitamente generado tiene infinitos extremos si y sólo si es un producto libre no trivial con amalgama o una extensión HNN con amalgama finita.
3. Todos los demás grupos infinitos generados finitamente tienen exactamente un extremo.

Notas

1. Sin embargo, como señalan Krön y Möller (2008), los extremos de los grafos ya fueron considerados por Freudenthal (1945).
2. Halín (1964).
3. Por ejemplo, esta es la forma de la relación de equivalencia utilizada por Diestel y Kühn (2003).
4. La nomenclatura de los puertos, y el hecho de que dos rayos definan el mismo puerto si y sólo si son equivalentes, se debe a Robertson, Seymour y Thomas (1991). Diestel y Kühn (2003) demostraron que cada puerto proviene de un extremo, completando la biyección entre extremos y puertos, utilizando una nomenclatura diferente en la que denominaron a los puertos "direcciones".
5. La prueba de Diestel y Kühn (2003) de que cada refugio puede definirse por un rayo no es trivial e implica dos casos. Si el conjunto (donde abarca todos los conjuntos finitos de vértices) es infinito, entonces existe un rayo que pasa por infinitos vértices de , lo que necesariamente determina . Por otro lado, si es finito, entonces Diestel y Kühn (2003) muestran que en este caso existe una secuencia de conjuntos finitos que separan el final de todos los puntos cuya distancia desde un punto de partida elegido arbitrariamente en es . En este caso, el refugio está definido por cualquier rayo que es seguido por un ladrón que usa el refugio para escapar de la policía que aterriza en el set en la ronda del juego de persecución-evasión. $${\displaystyle S=\bigcap _{X}\left(\beta (X)\cup X\right)}$$ ${\displaystyle X}$ ${\displaystyle S}$ ${\displaystyle \beta }$ ${\displaystyle S}$ ${\displaystyle X_{i}}$ ${\displaystyle G\setminus S}$ ${\displaystyle i}$ ${\displaystyle X_{i}}$ ${\displaystyle i}$
6. Más precisamente, en la formulación original de este resultado por Halin (1964) en la que los extremos se definen como clases de equivalencia de rayos, cada clase de equivalencia de rayos de contiene una única clase de equivalencia no vacía de rayos del bosque de expansión. En términos de refugios, hay una correspondencia biunívoca de refugios de orden entre y su árbol de expansión para el cual para cada conjunto finito y cada par correspondiente de refugios y . ${\displaystyle G}$ ${\displaystyle \aleph _{0}}$ ${\displaystyle G}$ ${\displaystyle T}$ ${\displaystyle \beta _{T}(X)\subset \beta _{G}(X)}$ ${\displaystyle X}$ ${\displaystyle \beta _{T}}$ ${\displaystyle \beta _{G}}$
7. Seymour y Thomas (1991);Thomassen (1992);Diestel (1992).
8. Diestel y Kühn (2003).
9. Diestel (2006).
10. Halin (1965); Diestel (2004).
11. Estados Unidos (1968, 1971).

Referencias

• Diestel, Reinhard (1992), "La estructura final de un gráfico: resultados recientes y problemas abiertos", Discrete Mathematics , 100 (1–3): 313–327, doi :10.1016/0012-365X(92)90650-5, MR  1172358
• Diestel, Reinhard (2004), "Una breve prueba del teorema de la cuadrícula de Halin", Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg , 74 : 237–242, doi :10.1007/BF02941538, MR  2112834, S2CID  124603912
• Diestel, Reinhard (2006), "Espacios finales y árboles de expansión", Journal of Combinatorial Theory , Serie B, 96 (6): 846–854, doi : 10.1016/j.jctb.2006.02.010 , MR  2274079
• Diestel, Reinhard; Kühn, Daniela (2003), "Extremos topológicos y teóricos de grafos", Journal of Combinatorial Theory , Serie B, 87 (1): 197–206, doi : 10.1016/S0095-8956(02)00034-5 , MR  1967888
• Freudenthal, Hans (1931), "Über die Enden topologischer Räume und Gruppen", Mathematische Zeitschrift , 33 : 692–713, doi :10.1007/BF01174375, S2CID  120965216
• Freudenthal, Hans (1945), "Über die Enden diskreter Räume und Gruppen", Commentarii Mathematici Helvetici , 17 : 1–38, doi :10.1007/bf02566233, MR  0012214, S2CID  125014683
• Halin, Rudolf (1964), "Über unendliche Wege in Graphen", Mathematische Annalen , 157 (2): 125–137, doi :10.1007/bf01362670, hdl : 10338.dmlcz/102294 , MR  0170340, S2CID  122125458
• Halin, Rudolf (1965), "Über die Maximalzahl fremder unendlicher Wege in Graphen", Mathematische Nachrichten , 30 (1–2): 63–85, doi :10.1002/mana.19650300106, SEÑOR  0190031
• Krön, Bernhard; Möller, Rögnvaldur G. (2008), "Extremos métricos, fibras y automorfismos de gráficos" (PDF) , Mathematische Nachrichten , 281 (1): 62–74, doi :10.1002/mana.200510587, MR  2376468, S2CID  18378856
• Mohar, Bojan (1991), "Algunas relaciones entre propiedades analíticas y geométricas de grafos infinitos" (PDF) , Discrete Mathematics , 95 (1–3): 193–219, doi : 10.1016/0012-365X(91)90337-2 , MR  1141939
• Robertson, Neil ; Seymour, Paul ; Thomas, Robin (1991), "Excluyendo menores infinitos", Discrete Mathematics , 95 (1–3): 303–319, doi : 10.1016/0012-365X(91)90343-Z , MR  1141945
• Seymour, Paul ; Thomas, Robin (1991), "Un contraejemplo de árbol de expansión fiel al final", Actas de la American Mathematical Society , 113 (4): 1163–1171, doi : 10.2307/2048796 , JSTOR  2048796, MR  1045600
• Stallings, John R. (1968), "Sobre grupos libres de torsión con infinitos extremos", Annals of Mathematics , Segunda serie, 88 (2): 312–334, doi :10.2307/1970577, JSTOR  1970577, MR  0228573
• Stallings, John R. (1971), Teoría de grupos y variedades tridimensionales: una conferencia de James K. Whittemore sobre matemáticas dictada en la Universidad de Yale, 1969 , Yale Mathematical Monographs, vol. 4, New Haven, Connecticut: Yale University Press, MR  0415622
• Thomassen, Carsten (1992), "Grafos conexos infinitos sin árboles de expansión que preserven los extremos", Journal of Combinatorial Theory , Serie B, 54 (2): 322–324, doi :10.1016/0095-8956(92)90059-7, hdl : 10338.dmlcz/127625 , MR  1152455