El lugar donde están, sin confundirse, todos los lugares del orbe, vistos desde todos los ángulos

septiembre 10, 2008

‘It’s a fabulous monster!’ the Unicorn cried out.
Lewis Carroll, Through the Looking-Glass

Muestre que existe un grafo \Gamma con conjunto de vértices numerable que tiene la siguiente propiedad:

Todo grafo numerable es isomorfo a un subgrafo inducido de \Gamma.

Más aún, muestre que existe, a menos de isomorfismo, exactamente un grafo numerable con esa propiedad y que \Gamma es isomorfo a cualquiera de los subgrafos que se obtienen de él sacándole una cantidad finita de vértices y de arcos.

Una respuesta to “El lugar donde están, sin confundirse, todos los lugares del orbe, vistos desde todos los ángulos”

  1. charlydif said

    ¡Copado! A mi lo que mas me sorprende es que el grafo sea unico.

    Construirlo no es dificil, voy a ir armandolo de a poco.

    Paso 0: Primero ponemos un vertice. Llamemos este grafo G_0.

    Paso 1: Ahora agregamos dos vertices mas, uno unido al primero y otro no. Llamemos a este grafo G_1

    Paso 2: Ahora vamos a agregar 8 vertices, uno por cada forma de agregar un vertice a G_1. Como G_1 tenia 3 vertices, hay 8=2^3 formas de agregar un vertice.

    Paso n: Ahora vamos a agregar 2^{|G_{n-1}|} vertices, uno por cada forma de agregar un vertice a G_{n-1}.

    Por ultimo ponemos G=\bigcup G_n o como mas les guste.

    Si llamamos H_n=G_{n}-G_{n-1} entonces a cualquier grafo numerable lo podemos meter (de forma unica!) adentro de G poniendo su primer vertice en H_0, el segundo en H_1, el tercero en H_2 y asi….

    Por la construccion del grafo se puede ver que si borramos del grafo a todo G_n de todas formas va a seguir teniendo la misma propiedad.

    Falta ver entonces que tal grafo es unico.

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: