Aplicaciones de la teoría de los grafos infinitos

Question

La teoría de grafos finitos abunda en aplicaciones dentro de las propias matemáticas, en la informática y en la ingeniería. Por lo tanto, me resulta natural investigar en teoría de grafos y también veo claramente la necesidad.

Ahora me pregunto sobre la teoría de los grafos infinitos. Parece que se ha investigado bastante sobre ella y, por supuesto, son una generalización natural de un concepto útil. Pero nunca he visto un ejemplo en el que realmente Necesito de ellos.

Entiendo que aparecen como grafos infinitos de Cayley en la teoría de grupos, que los grupos de automorfismo de grafos infinitos pero localmente finitos son grupos topológicos, que juegan algún papel en la topología general, etc. Pero a mí me parece que "sólo están ahí" y no son esenciales en el sentido de que un teorema sobre ellos demuestre algo sobre los grupos o la topología que no podríamos haber hecho fácilmente sin utilizarlos.

Formulada polémicamente mi pregunta es

¿Por qué deberíamos preocuparnos por los gráficos infinitos?

Answer 1

El primer libro sobre teoría de grafos fue el de König Teoría de los grafismos finales y no finales unendlichen Graphen (Teoría de grafos finitos e infinitos) de 1936. Así pues, los grafos infinitos formaron parte de la teoría de grafos desde el principio. El resultado más importante de König sobre los grafos infinitos fue el llamado lema del infinito de König que afirma que en un árbol infinito, de ramas finitas, hay una rama infinita. Este lema encierra muchos argumentos, desde el teorema de Bolzano-Weierstrass, el teorema de completitud de la lógica, la la prueba de varios teoremas de Ramsey en forma de teoría de grafos. El propio König lo utilizó para demostrar que la forma infinita del teorema de van der Waerden sobre las progresiones aritméticas implica la versión finita, y Erdos y Szekeres (que eran estudiantes de König) retomaron la idea en su trabajo pionero de 1935 sobre la teoría de Ramsey de Ramsey.

Como han mencionado otros comentaristas, los gráficos infinitos también son importantes como diagramas de grupo en la teoría combinatoria de grupos y topología de baja dimensión.

Answer 2

Aquí tienes una bonita demostración del teorema de Cantor-Bernstein en el lenguaje de los grafos infinitos.

Teorema. Dejemos que $G$ sea un grafo infinito con bipartición $(A,B)$ . Si $G$ tiene una saturación correspondiente $A$ y una saturación correspondiente $B$ entonces $G$ tiene una correspondencia perfecta.

Prueba. Dejemos que $M_A$ y $M_B$ ser emparejamientos saturando $A$ y $B$ respectivamente. Sea $H$ sea el gráfico con el conjunto de vértices $A \cup B$ y el conjunto de bordes la unión (disjunta) de $M_A$ y $M_B$ . Por lo tanto, $H$ puede ser un multigrafo. Es fácil comprobar que cada componente de $H$ es un camino infinito o un ciclo par. Por lo tanto, tomando una de cada dos aristas de cada componente de $H$ produce una coincidencia perfecta de $G$ .

Answer 3

La teoría de Bass--Serre traduce la noción algebraica de "división" de un grupo $G$ en una acción de $G$ en un árbol (normalmente infinito). Véase el clásico de Serre Arbres, Amalgamas, $SL_2$ .

Answer 4

El grafo de Rado (o grafo aleatorio contable) es la respuesta de la teoría de grafos a la distribución normal. Parece que casi cualquier definición sensata de dibujar aristas en un grafo contable de forma "aleatoria" o incluso "pseudo-aleatoria" producirá casi con seguridad el grafo de Rado. El estudio de este gráfico específico (y de entidades "universales" similares) podría justificarse simplemente por su ubicuidad. Dicho esto, no sé si ha tenido alguna aplicación clara a otras áreas.

Answer 5

Recientemente ha habido bastante actividad en la teoría descriptiva de conjuntos en relación con los grafos definibles. Benjamin Miller derivó varios resultados resultados clásicos, como el teorema de Silver (que afirma que toda relación de equivalencia (que afirma que toda relación de equivalencia suficientemente agradable (aquí coanalítica) en un espacio métrico completo separable tiene o bien tiene un número contable de clases de equivalencia o bien existe un espacio de Cantor de puntos puntos) a partir de resultados sobre grafos incontables mediante pruebas relativamente elementales. La prueba original del teorema de Silver utilizaba una pesada maquinaria teórica de conjuntos.

El resultado sobre grafos incontables que lo inició todo es el $\mathcal G_0$ -dichotomía de Kechris, Solecki y Todorcevic:

Existe un gráfico cerrado $\mathcal G_0$ en el espacio de Cantor tal que para todo gráfico analítico $G$ en un espacio polaco, ya sea $G$ tiene una coloración medible por Borel con un número contable de colores o existe un homomorfismo del grafo desde $\mathcal G_0$ a $G$ .

Así que en cierto sentido, $\mathcal G_0$ es el gráfico analítico mínimo cuyo número Borel-cromático es incontable.