Julianhaddad (julianhaddad@gmail.com)

Marlowe:PI (pzadunaisky@gmail.com)

…un uso turbio de la topología

Marcos Cossarini

Vamos a demostrar la siguiente proposición: Dado un grafo, si cada uno de sus subgrafos finitos se puede pintar con no más de k colores, entonces el propio grafo se puede pintar con no más de k colores. Para eso, vamos a utilizar dos resultados de topología referidos al producto de espacio topológicos. El más simple dice sencillamente que dado un producto de espacio topológicos, la proyección a cada una de las coordenadas es una función continua, y se usa solamente de forma auxiliar. El núcleo del argumento depende principalmente del teorema de Tychonoff, quizás el más importante de la topología general (cf. Munkres, Kelley, etc.) Este teorema afirma que el producto arbitrario de espacios topológicos compactos es compacto (en realidad, necesitamos una versión más debil).

Empezamos definiendo entonces en el espacio k de colores la topología discreta. Como este es un conjunto finito, tenemos que el espacio k es compacto. Sea ahora V el conjunto de vértices del grafo. Podemos llamar k^V al conjunto de funciones f: V \to k, las coloraciones del grafo, que es igual (homeomorfo, más bien) al producto \displaystyle \prod_{v \in V} k, y por lo tanto compacto. Definimos entonces la siguiente familia de conjuntos. Dados A, B \in V vértices contiguos, sea V_{A,B} = \{f \in k^V \ tq \ f(A) \neq f(B)\}, es decir el conjunto de coloraciones que a los vértices A y B les asignan colores distintos. Notar que este conjunto es cerrado. Para verlo, basta notar que V_{A,B} = (\pi_A \times \pi_B)^{-1}(\Delta)^c, donde \Delta = \{(a,a) \ tq \ a \in k\}. Como el producto tiene la topología discreta (heredada del conjunto original), este conjunto es abierto, por lo tanto su preimágen por ambas funciones (continuas) es abierta, y su complemento es cerrado.

Tomamos entonces \displaystyle \mathcal F = \left\{ \bigcap_{n=1}^N V_{A_n,B_n} \right\}, es decir, las familias de intersecciones finitas de conjuntos de la forma V_{A,B}. Por hipótesis, ninguna es vacía: esto es porque la intersección \bigcap V_{A_n, B_n} es el conjunto de coloraciones admisibles del grafo con vértices \{A_i, B_i\} y aristas entre A_i y B_i, que es un subgrafo del original. Pues bien, por compacidad del espacio de las coloraciones, esta familia tiene intersección no vacía. Pero un elemento en la intersección de \mathcal F es una coloración que a cualesquiera dos vértices contiguos les asigna colores distintos. Sabemos entonces que existe por lo menos una.

Un detalle: usamos una versión un poco más debil del teorema de Tychonoff: el producto arbitrario de espacios finitos discretos es compacto. A primera vista, este resultado es más debil que el teorema de Tychonoff ¿Es posible demostrar este resultado sin utilizar el axioma de elección?

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: