numero crom atico de borelxamanek.izt.uam.mx/coloquio/2013/platicas/pelayo.pdf · sea kv el...

Numero Cromatico de Borel

Fernando Hernandez Jose de Jesus Pelayo Gomez

Posgrado Conjunto en Ciencias Matematicas

7 de Marzo de 2013

Pelayo y Fernando (UMSNH-UNAM) Numero Cromatico de Borel 7 de Marzo de 2013 1 / 28

Contenido

1 PreliminaresMotivacionTeorema de Erdos-BruijnUn ejemplo

2 Juguemos a las escondidas¿Que ocupamos?Contemos, pero solo hasta el 3Uno dos tres por todos mis companeros!!

3 Algunos otros resultadosTodos los valores son posiblesGrado maximo

La grafica de la distancia unitaria

Sea G la grafica dada por:

V (G ) = R2

x , y son adyacentes si d(x , y) = 1.

La grafica de la distancia unitaria

Sea G la grafica dada por:

V (G ) = R2

x , y son adyacentes si d(x , y) = 1.

Surgen algunas preguntas

Podemos preguntarnos algunas cosas sobre esta grafica.

¿Por que la definimos ası?

¿Tiene algo interesante esta grafica?

¿Por que estudiar graficas infinitas?

¿Cual es el numero cromatico de G?

Bueno, como no soy filosofo, solo respondere (en parte) la ultimapregunta.

Un dibujito

Otro dibujo

Parte de la respuesta

De estas dos observaciones se sigue que χ(G ) ∈ {4, 5, 6, 7}.

No es muydifıcil probar que toda subgrafica finita de G tiene numero cromatico 4. Sisoponemos Axioma de Eleccion resutla que χ(G ) = 4. Si todos los subcon-juntos de R2 son medibles segun Lebesgue, entonces χ(G ) ∈ {5, 6, 7}.

De estas dos observaciones se sigue que χ(G ) ∈ {4, 5, 6, 7}. No es muydifıcil probar que toda subgrafica finita de G tiene numero cromatico 4.

Sisoponemos Axioma de Eleccion resutla que χ(G ) = 4. Si todos los subcon-juntos de R2 son medibles segun Lebesgue, entonces χ(G ) ∈ {5, 6, 7}.

De estas dos observaciones se sigue que χ(G ) ∈ {4, 5, 6, 7}. No es muydifıcil probar que toda subgrafica finita de G tiene numero cromatico 4. Sisoponemos Axioma de Eleccion resutla que χ(G ) = 4.

Si todos los subcon-juntos de R2 son medibles segun Lebesgue, entonces χ(G ) ∈ {5, 6, 7}.

De estas dos observaciones se sigue que χ(G ) ∈ {4, 5, 6, 7}. No es muydifıcil probar que toda subgrafica finita de G tiene numero cromatico 4. Sisoponemos Axioma de Eleccion resutla que χ(G ) = 4. Si todos los subcon-juntos de R2 son medibles segun Lebesgue, entonces χ(G ) ∈ {5, 6, 7}.

Teorema de Erdos-Bruijn

Sea G una grafica. Entonces χ(G ) ≤ k si y solo si χ(H) ≤ k para toda Hsubgrafica finita de G .

Demostracion:

Una implicacion es obvia. Para la otra, consideremos ak = {0, 1, ..., k − 1} con la topologıa discreta.

Sea kV el conjunto de funciones de V en k con la topologıa producto.

Claro que k es compacto, pues es finito. Por teorema de TychonoffkV es compacto.

Sea G una grafica. Entonces χ(G ) ≤ k si y solo si χ(H) ≤ k para toda Hsubgrafica finita de G . Demostracion:

Una implicacion es obvia.

Para la otra, consideremos ak = {0, 1, ..., k − 1} con la topologıa discreta.

Demostracion

Sea FH = {f ∈ kV : f |H es buena coloracion de H}.

Claramente {FH}H≤G y H finita, tiene la PIF.

Sea f /∈ FH , entonces existen u, v ∈ V (H) tales que a = f (u) = f (v)con u y v adyacentes en H. Ası U = {g ∈ kV : g(u) = g(v) = a} esabierto basico de la topologıa producto que contiene a f y nointersecta a FH .

De este modo f es punto interior de kV \ FH por lo que kV \ FH esabierto y entonces FH es cerrado.

Por compacidad,⋂

H FH 6= ∅ y cualquier funcion en la interseccion esuna buena coloracion para G . �

Demostracion

Sea FH = {f ∈ kV : f |H es buena coloracion de H}.Claramente {FH}H≤G y H finita, tiene la PIF.

Por compacidad,⋂

Demostracion

Por compacidad,⋂

Demostracion

Por compacidad,⋂

Demostracion

Por compacidad,⋂

Definiciones

Antes de continuar, unas pocas definiciones.

I Un espacio topologico se dira que es polaco si es completamentemetrizable y separable.

I R, Rn, Cn, I, IN, P, 2N, NN, SN son polacos.

I La σ-algebra de Borel es la generada por los abiertos (o cerrados).

I Una funcion se llam Borel si regresa conjuntos abiertos en conjuntosBorel (por ejemplo, las funciones continuas).

I Se define una coloracion Borel como una buena coloracion y tal que lafuncion es Borel (pensando el conjunto de colores con la topologıadiscreta).

Definiciones

Rn, Cn, I, IN, P, 2N, NN, SN son polacos.

Definiciones

I R, Rn,

Cn, I, IN, P, 2N, NN, SN son polacos.

Definiciones

I R, Rn, Cn,

I, IN, P, 2N, NN, SN son polacos.

Definiciones

I R, Rn, Cn, I,

IN, P, 2N, NN, SN son polacos.

Definiciones

I R, Rn, Cn, I, IN,

P, 2N, NN, SN son polacos.

Definiciones

I R, Rn, Cn, I, IN, P,

2N, NN, SN son polacos.

Definiciones

I R, Rn, Cn, I, IN, P, 2N,

NN, SN son polacos.

Definiciones

I R, Rn, Cn, I, IN, P, 2N, NN,

SN son polacos.

Definiciones

Ahora sı, el ejemplo

Sea H la grafica tal que los vertices son los reales y dos vertices son adya-centes si su distancia es una potencia (entera) de 3. Entonces:

I χ(H) = 2 con Axioma de Eleccion.

I χ(H) > ℵ0 si asumimos que todos los subconjuntos de R sonmedibles.

I χB(H) > ℵ0

I χB(H) = c con Hipotesis del Continuo o con Axioma de Martin.

I χB(H) > ℵ0

I Sea (x0, x1, ..., xn−1) un ciclo de H. Entonces |xi − xi+1| = 3ni , parai ∈ Zn.

I Ademas∑

ı∈Zn

±(xi − xi+1) = 0.

I Sea n = min{ni |i ∈ Zn}. De aquı que 3n∑

ı∈Zn

±3ni−n = 0.

I Los sumandos son todos impares y la suma da 0, ası en particular hayuna cantidad par de ellos y por lo tanto H no tiene ciclos de longitudimpar.

I Por teorema de Erdos-Bruijn χB(H) = 2 (aquı usamos eleccion).

I Ademas∑

ı∈Zn

±(xi − xi+1) = 0.

ı∈Zn

±3ni−n = 0.

I Ademas∑

ı∈Zn

±(xi − xi+1) = 0.

I Sea n = min{ni |i ∈ Zn}.

De aquı que 3n∑

ı∈Zn

±3ni−n = 0.

I Ademas∑

ı∈Zn

±(xi − xi+1) = 0.

ı∈Zn

±3ni−n = 0.

I Ademas∑

ı∈Zn

±(xi − xi+1) = 0.

ı∈Zn

±3ni−n = 0.

I Ademas∑

ı∈Zn

±(xi − xi+1) = 0.

ı∈Zn

±3ni−n = 0.

I Supongamos que tenemos una coloracion con ℵ0 colores, y seanA0,A1, ... Las clases cromaticas.

I Si todos los A′ns son medibles entonces existe Ak de medida postivia.

I Es un ejercicio clasico de medida probar que existe ε > 0 tal que(−ε, ε) ⊆ Ak − Ak (teorema de Steinhaus).

I Tomemos N ∈ Z suficientemente chico de modo que 3N ∈ (−ε, ε).

I Entonces en Ak hay dos puntos a distancia 3N y esos dos puntos sonadyacentes.

Hasta aquı hemos probado las afirmaciones 1 a 3 porque los conjuntos Borelson medibles.

La ultima afirmacion es obvia con hipotesis del continuo. Parala ultima parte de la demostracion basta recordar que union de κ conjuntosde medida 0 es medible y de medida 0, asumiendo axioma de Martin.

Hasta aquı hemos probado las afirmaciones 1 a 3 porque los conjuntos Borelson medibles. La ultima afirmacion es obvia con hipotesis del continuo.

Parala ultima parte de la demostracion basta recordar que union de κ conjuntosde medida 0 es medible y de medida 0, asumiendo axioma de Martin.

Hasta aquı hemos probado las afirmaciones 1 a 3 porque los conjuntos Borelson medibles. La ultima afirmacion es obvia con hipotesis del continuo. Parala ultima parte de la demostracion basta recordar que union de κ conjuntosde medida 0 es medible y de medida 0, asumiendo axioma de Martin.

Proposicion 1

Sean (X , τ) un espacio polaco y f : X → N una funcion Borel. Entonces,existe topologıa polaca σ tal que f es continua con esa topologıa.Demostracion:

I Sea (X , τ) polaco y sea A ⊂ X cerrado. Entonces existe τ ⊂ τAtopologıa polaca tal que A es clopen.

I Si τ1 ⊂ τ2 ⊂ . . . son topologıas polacas sobre X , entonces 〈⋃

n∈N τn〉es polaca.

I Sea A = {A ⊂ X | existe τ ⊂ τA topologıa polaca en donde A esclopen}.

I B ⊂ A porque A es σ-algebra y contine a los cerrados.

Proposicion 1

I Consideremos An = f −1[{n}] y τn topologıa en la cual A1,A2, . . . ,An

son clopen.

I Entonces en la topologıa 〈⋃

n∈N τn〉 cada An es abierto y de estemodo f es continua. �

Proposicion 1

I Consideremos An = f −1[{n}] y τn topologıa en la cual A1,A2, . . . ,An

son clopen.

I Entonces en la topologıa 〈⋃

n∈N τn〉 cada An es abierto y de estemodo f es continua. �

Proposicion 2

Sean X polaco y D = (X ,A) una grafica dirigida. Sea G la graficacorrespondiente a D. Supongamos que para cada conjunto Borel Y ⊂ X elconjunto A−1(Y ) es Borel. Entonces χB(G) ≤ ℵ0 si y solo si existetopologıa τ ⊂ σ tal que x /∈ clσ(A(x)). Demotracion:

I ⇐: Sea {Un} una base para σ. Sea c(x) = el menor n tal que x ∈ Un

y Un ∩ A(x) = ∅. Entonces c es Borel y buena coloracion.

I ⇒: Si c : X → N es una coloracion Borel, entonces sea σ topologıaPolaca tal que c es continua. Cada An = f −1[{n}] es σ-clopen.Ası que An ∩ A(x) = ∅. �

Proposicion 2

I ⇐: Sea {Un} una base para σ.

Sea c(x) = el menor n tal que x ∈ Un

Proposicion 2

y Un ∩ A(x) = ∅.

Entonces c es Borel y buena coloracion.

Proposicion 2

Lema 1

Sean X Polaco y D = (X ,A) una grafica dirigida. Sea G la graficacorrespondiente a D. Supongamos que para cada conjunto Borel Y ⊂ X elconjunto A−1(Y ) es Borel. Entonces χB(G) ≤ ℵ0 si cada vertice tieneexgrado finito. En particular si G esta generada por una cantidad finita defunciones Borel entonces χB(G) ≤ ℵ0. Demotracion:

I En Proposicon 2 tome σ = τ .

Lema 1

Sean X Polaco y D = (X ,A) una grafica dirigida. Sea G la graficacorrespondiente a D. Supongamos que para cada conjunto Borel Y ⊂ X elconjunto A−1(Y ) es Borel. Entonces χB(G) ≤ ℵ0 si cada vertice tieneexgrado finito. En particular si G esta generada por una cantidad finita defunciones Borel entonces χB(G) ≤ ℵ0. Demotracion:

I En Proposicon 2 tome σ = τ .

Lema 2

Sea sn : nN → nN dada por sn(x)i = xi+1. Entonces χB(Gsn) ≤ 3.Demotracion por induccion sobre n:n=2:

I Partimos 2N como sigue:

I A0 = {x ∈ 2N : x comienza con un numero impar de ceros }I A1 = {x ∈ 2ω : x comienza con un numero impar de unos }I A2 = 2N\(A0 ∪ A1)

Esta es una coloracion Borel de Gs2

Lema 2

I A0 = {x ∈ 2N : x comienza con un numero impar de ceros }

I A1 = {x ∈ 2ω : x comienza con un numero impar de unos }I A2 = 2N\(A0 ∪ A1)

Lema 2

I A0 = {x ∈ 2N : x comienza con un numero impar de ceros }I A1 = {x ∈ 2ω : x comienza con un numero impar de unos }

I A2 = 2N\(A0 ∪ A1)Esta es una coloracion Borel de Gs2

Lema 2

n→ n + 1:

I Sea c : nN → 3 una coloracion Borel de Gsn . Ahora encontremosc∗ : (n + 1)N → 3 coloracion Borel. Para x ∈ (n + 1)N consideremoslos siguientes casos:

I Si existe una infinidad de i ’s tales que xi = n y una infinidad tal quexi ∈ n. Al conjunto de estos x ’s llamemoslo X1

c∗(x) = 0 si x comienza con un numero impar de n’sc∗(x) = 1 si x comienza con un numero impar de elementos de nc∗(x) = 2 en otro caso

Lema 2

n→ n + 1:

I Sea c : nN → 3 una coloracion Borel de Gsn . Ahora encontremosc∗ : (n + 1)N → 3 coloracion Borel.

Para x ∈ (n + 1)N consideremoslos siguientes casos:

Lema 2

n→ n + 1:

Lema 2

n→ n + 1:

Lema 2

n→ n + 1:

c∗(x) = 0 si x comienza con un numero impar de n’s

c∗(x) = 1 si x comienza con un numero impar de elementos de nc∗(x) = 2 en otro caso

Lema 2

n→ n + 1:

c∗(x) = 0 si x comienza con un numero impar de n’sc∗(x) = 1 si x comienza con un numero impar de elementos de n

c∗(x) = 2 en otro caso

Lema 2

n→ n + 1:

Lema 2

I En x solo hay una contidad finita de coordenadas distintas de n.

Atales x ’s los agrupamos en un conjunto X2

I c∗(x) = 0 si x comienza con un numero impar de elementos menoresque n.

I c∗(x) = 1 si x comienza con un numero impar de n’s.

I c∗(x) = 2 en otro caso.

Lema 2

I En x solo hay una contidad finita de coordenadas distintas de n. Atales x ’s los agrupamos en un conjunto X2

Lema 2

I En x solo hay una contidad finita de coordenadas iguales a n. Este esnuestro conjunto X3.

I Para x ∈ X3 podemos escribir de manera unica x = s_y dondes ∈ (n + 1)k para algun k , sk−1 = n (si x > 0) y y ∈ nN. Entonces:c∗(x) = (c(y) + k)mod3

I Cada coloracion en Xi es coloracion Borel, ademas no hay arista entrex y y si x ∈ Xi y y ∈ Xj para i 6= j .

Lema 2

I En x solo hay una contidad finita de coordenadas iguales a n.

Este esnuestro conjunto X3.

Lema 2

I Para x ∈ X3 podemos escribir de manera unica x = s_y dondes ∈ (n + 1)k para algun k , sk−1 = n (si x > 0) y y ∈ nN.

Entonces:c∗(x) = (c(y) + k)mod3

Lema 2

Teorema

Sean X un espacio polaco y F : X → X una funcion Borel. EntoncesχB(GF ) ∈ {1, 2, 3,ℵ0}.

I Por Lema 1 χB(GF ) ≤ ℵ0.

I Supongamos que χB(GF ) ≤ n y sea c : X → n una buena coloracionBorel.

I Definimos p : X → nN por p(x)i = c(F i (x)).

I Sea c ′ : nN → 3 una buena coloracion (por Lema 2)

I Entonces c = c ′ ◦ p es una coloracion Borel. �

Teorema

Sean X un espacio polaco y F : X → X una funcion Borel. EntoncesχB(GF ) ∈ {1, 2, 3,ℵ0}.I Por Lema 1 χB(GF ) ≤ ℵ0.

Teorema

Ejemplos

Resulta que todos los valores son posibles.

I Si por ejemplo tomados F : R→ R como la identidad entonces comoGF no tiene aristas y ası χB(GF ) = 1.

I Tomando F : R→ R como F (x) = −x se tiene que χB(GF ) = 2.

I Para cualquier n resutla que χB(Gsn) = 3 pues Gsn tiene triangulos.

I Si tomamos F : [N]N → [N]N, entonces χ(GF ) = 2, peroχB(GF ) = ℵ0.

Ejemplos

Proposicion

Sea f : N → N una funcion cualquiera. Entonces χB(Gf ) ≤ 3.

De-mostracion:

I Es facil probar que toda subgrafica finita tiene una coloracion propiacon 3 colores.

I Por teorema de Erdos el numero cromatico es menor o igual que 3

I Toda coloracion es coloracion Borel en N porque N es discreto.

I ¡¡Esto es cierto incluso si cada vertice tiene grado infinito!!

Proposicion

Sea f : N → N una funcion cualquiera. Entonces χB(Gf ) ≤ 3. De-mostracion:

Proposicion

Teorema

Sea G una grafica sobre un espacio polaco X y tal que N(Y ) es Borel paracada Y Borel (Esto es cierto por ejemplo si cada vertice tiene grado finito osi G esta generada por una cantidad numerable de funciones).

Si ∆(G ) = k,entonces χB(G ) ≤ k + 1. Demostracion:

I Primero probamos que G tiene nucleo Borel.

I El resto de la prueba es por induccion y se hace identica que engraficas finitas.

Un “corolario” de esto es que si G esta generada por n funciones todas ellas≤ k a 1, entonces χB(G ) ≤ k(n + 1) + 1

Teorema

Sea G una grafica sobre un espacio polaco X y tal que N(Y ) es Borel paracada Y Borel (Esto es cierto por ejemplo si cada vertice tiene grado finito osi G esta generada por una cantidad numerable de funciones). Si ∆(G ) = k,entonces χB(G ) ≤ k + 1. Demostracion:

Teorema

Datos curiosos

Realmente lo que se hizo en la prueba de 1, 2, 3 fue encajar con una funcionBorel a cualquier grafica generada por una funcion en otra grafica de la cualya sabıamos datos.

Resulta que hay graficas isomorfas pero de modo queno se pueden encajar la primera en la segunda ni viceversa con funcionesBorel, aunque eso ya sera tema de otra platica.

Datos curiosos

Realmente lo que se hizo en la prueba de 1, 2, 3 fue encajar con una funcionBorel a cualquier grafica generada por una funcion en otra grafica de la cualya sabıamos datos. Resulta que hay graficas isomorfas pero de modo queno se pueden encajar la primera en la segunda ni viceversa con funcionesBorel, aunque eso ya sera tema de otra platica.

G R A C I A S ! ! !

numero crom atico de borelxamanek.izt.uam.mx/coloquio/2013/platicas/pelayo.pdf · sea kv el...

Documents