¿Por qué la homología no puede distinguir entre gráficos planos y no planos?

Intuitivamente, uno puede pensar que los gráficos no planos tienen un "agujero bidimensional" ( Editar: esto no está claro y no es del todo correcto, si es que es correcto, vea los comentarios debajo de la pregunta ), por lo que es necesario que estén incrustados en el espacio representarse sin autointersecciones.

La teoría de la homología a menudo se describe intuitivamente como una caracterización de los agujeros de un espacio. Sin embargo (ver más abajo) se puede demostrar rigurosamente que solo es posible formular las condiciones necesarias para la no planaridad en términos de los grupos de homología de un gráfico, pero no las condiciones suficientes.

Intuitivamente, esto podría entenderse como un reflejo del hecho de que los gráficos no planos se caracterizan por "agujeros bidimensionales", mientras que los grupos de homología de cualquier complejo CW unidimensional son triviales (por lo tanto, no brindan información) excepto por el 0 grupos de homología th y first.

Pregunta: ¿Es posible interpretar las condiciones combinatorias para la no planaridad dadas por el teorema de Kuratowski en condiciones topológicas que pueden verificarse usando homología, digamos adjuntando 2 -cells/simples al gráfico de una manera estándar? ¿Por qué o por qué no?

(Por ejemplo, formando el complejo de independencia o complejo de camarilla, es decir, alguna forma de unir 2 -cells que no es arbitrario, por lo que no proporciona información superflua sobre el gráfico. Esta pregunta de MO podría ser relevante).

Antecedentes: sin pérdida de generalidad, considere solo grafos conexos. Luego, la homología de un gráfico (finito) está completamente determinada por su primer número de Betti (el número de ciclos en el gráfico), que es el rango del primer grupo de homología. El rango del grupo de homología cero es uno, y todos los demás grupos de homología son triviales. (Esto es implícitamente considerar gráficos como complejos CW unidimensionales, por lo tanto, por homología me refiero a cualquier teoría que satisfaga los axiomas de Eilenberg-Steenrod).

Por el teorema de Kuratowski, un gráfico no es plano si y solo si contiene subgrafos homeomorfos a cualquiera k 5 , el grafo completo en cinco vértices, o k 3 , 3 , el grafo bipartito completo en seis vértices.

k 5 tiene 5 ( 4 ) 2 = 10 bordes, cualquier árbol de expansión máxima tiene 4 bordes, por lo que debe tener un número de Betti de 10 − 4 = 6 . Asimismo, k 3 , 3 tiene 3 ( 3 ) = 9 bordes, y cualquier árbol de expansión máxima debe tener 5 bordes, por lo que debe tener un número de Betti de 9 − 5 = 4 .

Editar: todo lo que está más allá de aquí está mal: estaba asumiendo una propiedad de aditividad inexistente para los ciclos de un gráfico en función del número de ciclos de subgráficos. Es decir, simplificar demasiado la realidad.

Por lo tanto, cualquier gráfico no plano debe tener:

4 metro + 6 norte = min { 4 , 6 } + mcd { 4 , 6 } pag = 2 + 2 r , máximo { metro , norte } ≥ 1 , min { metro , norte } ≥ 0 , pag ≥ 0 , r ≥ 1 ,
por su número de Betti, es decir, número de ciclos.

Por otro lado, podemos construir claramente un gráfico plano con cualquier número arbitrario (integral no negativo) de ciclos. Así podemos concluir que los grafos no planos no se caracterizan únicamente por sus grupos de homología, aunque podemos establecer como condición necesaria que todo grafo no plano debe tener como primer número de Betti un número par mayor que dos.

No hay 2 agujeros dimensionales en un 1 -objeto dimensional. Que ser no plano no significa que haya 2 "agujeros" bidimensionales, significa que no hay incrustaciones en el plano. Puede haber una incrustación en otro espacio sin agujeros; de hecho, todos los gráficos se pueden incrustar en 3 dimensiones.
Un agujero bidimensional tendría intuitivamente un límite que parece una superficie. Un gráfico no contiene nada que parezca una superficie. es puramente 1 -dimensional.
Los gráficos no planos también pueden tener números de Betti impares. Realmente no ser plano tiene muy poco que ver con la homología, aunque implica que hay algunos ciclos.
@MattSamuel No estoy seguro de si esto aclara algo, o solo provocará más correcciones, pero me doy cuenta de que el "agujero bidimensional" no capta bien lo que estoy tratando de decir, quiero decir "una cavidad análoga a esa delimitada por la 2-esfera, analizada por el segundo grupo de homología, que consiste en un conjunto tridimensional de puntos" y cuando digo que un gráfico no plano tiene tal agujero, lo más cercano a la afirmación rigurosa que se me ocurre es que posee una extensión "permitida" o "agradable" o "intrínseca" a un complejo CW bidimensional que tiene tal agujero.
@MattSamuel También tiene razón (gracias por corregir/enseñarme esto) sobre los números impares de Betti: estaba asumiendo una propiedad de aditividad que no tengo ninguna razón para existir (porque no es así), creo basado en parte por dejarse engañar por ejemplos simples. Dejaré la prueba falsa original con una nota explicando el error.
Nota para futuros lectores: el problema 24, en la sección 2.2, de Topología algebraica de Hatcher (p. 157 de la edición de 2015), es extremadamente relevante aquí.
Adicionalmente el problema 2, p.176, apartado 2.B. Aunque no creo que el segundo resultado sirva para mostrar el teorema de Kuratowski (respecto al primer problema sigo indeciso), ya que hay grafos planos con la misma homología que los grafos no planos. Sin embargo, tal vez el hecho de que se utilice una homología reducida sea relevante.

Respuestas (1)

Esta es una pregunta interesante para mí. El comentario de @ThomasAndrews es un buen punto, pero aún hay algo que considerar:

Cuando un gráfico (conectado) está incrustado en el plano (o, para simplificar las cosas eliminando un caso especial, la esfera), su complemento en el plano consiste en un grupo de celdas (regiones homeomorfas a un disco) -- el " regiones" delimitadas por bordes. Estos, junto con el propio gráfico, pueden convertirse en un complejo celular cuya primera homología es trivial y cuya segunda homología es la de una esfera (es decir, Z ).

¿Qué pasa con un gráfico no plano (conectado)? Si PUDIERA unir celdas de tal manera que la homología "pareciera correcta" (es decir, ( Z , 0 , Z ) en dimensiones 0, 1, 2) y para que cada borde se uniera a exactamente dos 2 celdas (para que sea como una variedad), entonces la variedad resultante sería necesariamente una esfera (según el teorema de clasificación para 2-variedades), y por lo tanto el gráfico sería incrustable, una contradicción.

Entonces, lo que puedes decir es que para un gráfico conectado no plano GRAMO , todos los posibles complejos de 2 células similares a variedades cuyo 1 esqueleto es GRAMO tienen grupos de homología que no son los de la 2-esfera.

Ahora, esa no es una declaración muy útil en su mayor parte, pero muestra que la homología captura algo útil aquí.

Creo que este es el enfoque correcto para el problema. Si echamos un vistazo a los primeros capítulos de Foundations of Topological Graph Theory de Bonnington y Little, parece que hay un resultado (Corolario 3.10 en la página 51) que muestra que un gráfico es plano si y solo si su característica de Euler es 2, con las "caras " del gráfico que se define tomando la extensión del gráfico a un complejo de 2 llamado "gema" o "gráfico de 3" (en realidad, todavía no estoy seguro de cuáles son estos a partir de sus definiciones).
¿Por qué la homología no puede distinguir entre gráficos planos y no planos?
RespuestasAquíPolítica de privacidad1y, 0v