Fin (teoría de grafos)

En las matemáticas de gráficas infinitas , el final de una gráfica representa, intuitivamente, una dirección en la que la gráfica se extiende hasta el infinito. Extremos pueden formalizarse matemáticamente como clases de equivalencia de infinitos caminos , como refugios que describe las estrategias para la búsqueda de evasión de juegos en el gráfico, o (en el caso de los gráficos localmente finitos) como extremos topológicos de espacios topológicos asociados con la gráfica.

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

Definición y caracterización

Los extremos de los gráficos fueron definidos por Rudolf Halin  ( 1964 ) en términos de clases de equivalencia de caminos infinitos. ^[1] Un rayo en un gráfico infinito es un camino simple semi-infinito ; es decir, es una secuencia infinita de vértices v ₀ , v ₁ , v ₂ , ... en 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 extremos de una arista en el grafico. Según la definición de Halin, dos rayos r ₀ y r ₁ son equivalentes si hay otro rayo r ₂(no necesariamente diferente de ninguno de los dos primeros rayos) que contiene infinitos vértices en cada r ₀ y r ₁ . Se trata de una relación de equivalencia : cada rayo es equivalente a sí mismo, la definición es simétrica con respecto al orden de los dos rayos y se puede demostrar que es transitiva . Por lo tanto, divide el conjunto de todos los rayos en clases de equivalencia , y Halin definió un final como una de estas clases de equivalencia.

También se ha utilizado una definición alternativa de la misma relación de equivalencia: ^[2] dos rayos r ₀ y r ₁ son equivalentes si no hay un conjunto finito X de vértices que separe infinitos vértices de r ₀ de infinitos vértices de r ₁ . Esto es equivalente a la definición de Halin: si el rayo r ₂ de la definición de Halin existe, entonces cualquier separador debe contener un número infinito de puntos de r ₂ y por lo tanto no puede ser finito, y viceversa si r ₂no existe entonces un camino que alterne tantas veces como sea posible entre r ₀ y r ₁ debe formar el separador finito deseado.

Extremos también tienen una caracterización más concreto en términos de refugios , las funciones que describen las estrategias de evasión para la búsqueda de evasión de juegos en un gráfico G . ^[3] En el juego en cuestión, un ladrón está tratando de evadir un conjunto de policías al pasar de vértice a vértice a lo largo de los bordes de G . La policía tiene helicópteros y, por lo tanto, no necesita seguir los bordes; sin embargo, el ladrón puede ver que se acerca la policía y puede elegir dónde moverse antes de que aterricen los helicópteros. Un refugio es una función β que asigna cada conjunto X de ubicaciones policiales a uno de los componentes conectados del subgrafo formado al eliminar X; 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 coherencia (correspondiente al requisito de que el ladrón no puede moverse a través de los vértices en los que la policía ya ha aterrizado): si X es un subconjunto de Y , y tanto X como Y son conjuntos de ubicaciones válidos para el conjunto de policías dado. , entonces β ( X ) debe ser un superconjunto de β ( Y ). Un refugio tiene orden k si la colección de ubicaciones policiales para las que proporciona una estrategia de escape incluye todos los subconjuntos de menos de k vértices en el gráfico; en particular, tiene orden ℵ ₀si los mapas de cada subconjunto finito X de los vértices de un componente de G  \  X . Cada rayo en G corresponde a un refugio de orden ℵ ₀ , es decir, la función β que mapea cada conjunto finito X a la componente única de G  \  X que contiene infinitos vértices del rayo. A la inversa, todo refugio de orden ℵ ₀ puede definirse de esta manera mediante un rayo. ^[4] Dos rayos son equivalentes si y solo si definen el mismo refugio, por lo que los extremos de un gráfico están en correspondencia uno a uno con sus paraísos de orden ℵ ₀ .

Ejemplos

Parte de un gráfico de cuadrícula infinito , 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 final.

Si el gráfico infinito G es en sí mismo un rayo, entonces se tiene un número infinito subgraphs ray, uno de partida desde cada vértice de G . Sin embargo, todos estos rayos son equivalentes entre sí, por lo que G solo tiene un extremo.

Si G es un bosque (es decir, un gráfico 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 de base en cada componente conectado de G , entonces cada extremo de G contiene un rayo único que comienza desde uno de los vértices de la base, por lo que los extremos pueden colocarse en correspondencia uno a uno con estos rayos canónicos. Cada gráfico contable G tiene un bosque que abarca con el mismo conjunto de extremos como G . ^[5] Sin embargo, existen incontables gráficos infinitos con un solo extremo en el que cada árbol de expansión tiene infinitos extremos. ^[6]

Si G es un gráfico de cuadrícula infinito , entonces tiene muchos rayos y conjuntos arbitrariamente grandes de rayos disjuntos de vértice. Sin embargo, solo tiene un final. Esto se puede ver más fácilmente usando 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 infinito conectado componente).

Relación con los fines topológicos

En la topología de conjuntos de puntos , existe un concepto de fin que es similar, pero no exactamente igual, al concepto de fin en la teoría de grafos, que se remonta mucho antes a Freudenthal (1931) . Si un espacio topológico puede ser cubierto por una secuencia anidada de conjuntos compactos , entonces un final 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 tales opciones pueden colocarse en correspondencia biunívoca con los extremos definidos por cualquier otra opción.${\displaystyle \kappa _{0}\subset \kappa _{1}\subset \kappa _{2}\dots }$${\displaystyle U_{0}\supset U_{1}\supset U_{2}\dots }$

Un grafo infinito G se puede convertir en un espacio topológico de dos formas diferentes pero relacionadas:

• 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 S se define como abierto siempre que cada intersección de S con un borde del gráfico sea un subconjunto abierto del intervalo unitario.
• Reemplazar cada vértice del gráfico por un punto y cada borde del gráfico por un punto produce un espacio que no es de Hausdorff en el que los conjuntos abiertos son los conjuntos S con la propiedad de que, si un vértice v de G pertenece a S , entonces entonces hace cada borde que tiene v como uno de sus puntos finales.

En cualquier caso, cada subgrafo finito de G 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 de aristas propios compactos. Por lo tanto, un gráfico puede estar cubierto por una secuencia anidada de conjuntos compactos si y solo si es localmente finito, y tiene un número finito de aristas en cada vértice.

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

Para los gráficos que pueden no ser localmente finitos, aún es posible definir un espacio topológico a partir del gráfico y sus extremos. Este espacio se puede representar como un espacio métrico si y solo si el gráfico tiene un árbol de expansión normal , un árbol de expansión enraizado de modo que cada borde del gráfico conecte un par ancestro-descendiente. Si existe un árbol de expansión normal, tiene el mismo conjunto de extremos que el gráfico dado: cada extremo del gráfico debe contener exactamente una ruta infinita en el árbol. ^[8]

Tipos especiales de fines

Extremos libres

Un extremo E de un gráfico G se define como un extremo libre si hay un conjunto finito X de vértices con la propiedad de que X separa E de todos los demás extremos del gráfico. (Es decir, en términos de paraísos, β _E ( X ) es disjunto de β _D ( X ) para todos los demás extremos D ). En una gráfica con un número finito de extremos, todos los extremos deben ser libres. Halin (1964) demuestra que, si G tiene infinitos extremos, entonces, o existe un fin que no es libre, o existe una familia infinita de rayos que comparten un vértice inicial común y, por lo demás, están separados entre sí.

Extremos gruesos

Un extremo grueso de una gráfica G es un extremo que contiene infinitos rayos separados por pares . El teorema de la cuadrícula de Halin caracteriza los gráficos que contienen extremos gruesos: son exactamente los gráficos que tienen una subdivisión del mosaico hexagonal como un subgráfico. ^[9]

Tipos especiales de gráficos

Gráficos simétricos y casi simétricos

Mohar (1991) define un grafo finito localmente conectado como "casi simétrico" si existe un vértice vy un número D tal que, para cada otro vértice w , hay un automorfismo del grafo para el cual la imagen de v está dentro de distancia D de w ; de manera equivalente, un grafo finito localmente conectado es casi simétrico si su grupo de automorfismos tiene un número finito de órbitas. Como muestra, para cada grafo casi simétrico finito localmente conectado, 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 elConstante Cheeger

${\displaystyle h=\inf \left\{{\frac {|\partial V|}{|V|}}\right\},}$

donde V rangos de más de todos los conjuntos no vacíos finitos de vértices del grafo y donde denota el conjunto de bordes con un punto final en V . Para gráficos casi simétricos con incontables extremos, h  > 0; sin embargo, para gráficos casi simétricos con solo dos extremos, h  = 0.${\displaystyle \partial V}$

Gráficos de Cayley

El gráfico de Cayley del grupo libre en dos generadores de una y b . Los extremos del grupo están en correspondencia uno a uno con los rayos (caminos infinitos) desde el elemento de identidad e hasta los bordes del dibujo.

Cada grupo y un conjunto de generadores para el grupo determinan un gráfico de Cayley , un gráfico cuyos vértices son los elementos del grupo y las aristas son pares de elementos ( x , gx ) donde g es uno de los generadores. En el caso de un grupo generado finitamente , los extremos del grupo se definen como los extremos del gráfico 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 gráficos de Cayley están en correspondencia uno a uno entre sí.

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

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

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

Notas

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

Referencias

• Diestel, Reinhard (1992), "La estructura final de un gráfico: resultados recientes y problemas abiertos", Matemáticas discretas , 100 (1-3): 313-327, doi : 10.1016 / 0012-365X (92) 90650-5 , Señor  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.
• 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), "Grafos teóricos versus extremos topológicos de gráficos", 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 .
• Freudenthal, Hans (1945), "Über die Enden diskreter Räume und Gruppen", Commentarii Mathematici Helvetici , 17 : 1–38, doi : 10.1007 / bf02566233 , MR  0012214 .
• Halin, Rudolf (1964), "Über unendliche Wege in Graphen", Mathematische Annalen , 157 (2): 125-137, doi : 10.1007 / bf01362670 , hdl : 10338.dmlcz / 102294 , MR  0170340 .
• Halin, Rudolf (1965), "Über die Maximalzahl fremder unendlicher Wege in Graphen", Mathematische Nachrichten , 30 (1–2): 63–85, doi : 10.1002 / mana.19650300106 , MR  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.
• Mohar, Bojan (1991), "Algunas relaciones entre propiedades analíticas y geométricas de gráficos infinitos" (PDF) , Matemáticas discretas , 95 (1-3): 193-219, doi : 10.1016 / 0012-365X (91) 90337-2 , Señor  1141939 .
• Robertson, Neil ; Seymour, Paul ; Thomas, Robin (1991), "Excluyendo a los menores infinitos", Matemáticas discretas , 95 (1–3): 303–319, doi : 10.1016 / 0012-365X (91) 90343-Z , MR  1141945.
• Seymour, Paul ; Thomas, Robin (1991), "An end-fiel spanning tree contraejemplo", Proceedings of the American Mathematical Society , 113 (4): 1163-1171, doi : 10.2307 / 2048796 , JSTOR  2048796 , MR  1045600.
• Stallings, John R. (1968), "Sobre grupos sin torsión con infinitos extremos", Annals of Mathematics , Second Series, 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 impartida en la Universidad de Yale, 1969 , Monografías de matemáticas de Yale, 4 , New Haven, Connecticut: Yale University Press, MR  0415622 .
• Thomassen, Carsten (1992), "Gráficos conectados infinitos sin árboles de expansión que conserven los extremos", Journal of Combinatorial Theory , Serie B, 54 (2): 322–324, doi : 10.1016 / 0095-8956 (92) 90059-7 , HDL : 10338.dmlcz / 127.625 , MR  1152455 .