Teoria de ramsey

La Teoría de Ramsey
Pablo Fernández Gallardo Facultad Informática UPM

Imagínate una noche clara y estrellada... Al principio, las estrellas forman una mancha difusa que llena el horizonte... Pero, poco a poco, se van distinguiendo una línea recta aquí, un cuadrado allí... Y si te dejas llevar lo suficiente por tu imaginación, llegarás a ver un león, un escorpión o un oso...

Primerresultado “a la Ramsey” El principio del palomar

O, en palabras,
si tenemos n nidos y n+1 palomas, entonces al menos dos de ellas duermen en el mismo nido.

Más generalmente:
si tenemos n nidos y kn+1 palomas, entonces al menos k+1 de ellas duermen en el mismo nido

Segundo ejemplo
n

En cualquier reunión de 6 personas, o bien 3 de ellas se conocen entre sí, o bien 3 de ellas no se conocenentre sí.

Es decir, si coloreamos de rojo y azul las aristas del grafo

o bien tenemos un triángulo rojo o bien uno azul

El teorema de Ramsey. Los números de Ramsey.
Problema: dados p y q, encontrar el mínimo N que cumpla que si coloreamos las aristas de KN con dos colores, rojo y azul, podemos encontrar un Kp azul o un Kq rojo. El mínimo entero con esa propiedad es el número de RamseyR(p,q;2) El ejemplo anterior (y un ingrediente más) nos dice que R(3,3;2)=6

Teorema (Ramsey)
Dados p1,..., pt, existe N tal que si coloreamos KN con t colores, entonces hay un K p1 del primer color, o bien un Kp2 del segundo, etc. El menor N con esa propiedad es el número de Ramsey R(p1,..., pt ;2)

Teorema (Ramsey) II
Dados p1,..., pt y r≥ 1, existe N tal que si un conjunto tiene almenos ese número de elementos y coloreamos sus r-subconjuntos con t colores, entonces hay un pisubconjunto con todos sus r-subconjuntos de color i. El menor N con esa propiedad es el número de Ramsey R(p1,..., pt ;r)

El principio del palomar, “a la Ramsey”
R(2,...,2 ; 1) = t+1 t Es decir, coloreamos los vértices de un Kt+1 con t colores distintos y al menos hay dos vértices en uno de los colores.R(r+1,...,r+1 ; 1) = rt+1 t

Tercer ejemplo (una observación de Esther Klein):
n

dados 5 puntos del plano (sin tríos colineales), hay cuatro que forman un cuadrilátero convexo.

La envolvente convexa de 5 puntos en el plano es un polígono de 5, 4 o 3 lados

¿Y el problema general?
n

¿Podemos encontrar, para un n dado, un N(n) de manera que si situamos N(n) puntos en el plano(sin tríos colineales), haya n formando un polígono convexo?
(Hemos visto que N(4)=5)

Respuesta: Erdös-Szekeres
N(n)≥ R(5,n;4)

Coloreamos los 4-subconjuntos con los colores “convexo” y “no convexo”. La definición de número de Ramsey nos dice que • o bien hay 5 puntos cuyos 4-subconjuntos son todos cuadriláteros no convexos, • o bien hay n cuyos 4-subconjuntos son todos cuadriláterosconvexos. ¡Ah!, y un polígono es convexo si sus cuadriláteros lo son. Por cierto, N(4)=5=22+1 N(5)=9=23+1

Conjetura: N(n)=2n-2+1

Cuarto ejemplo:
n

dada una lista ordenada de 5 números reales, al menos 3 de ellos (en el mismo orden) forman una sucesión monótona.

El problema general:
n

dado n, encontrar M(n) de manera que cualquier sucesión de M(n) números reales contenga una subsucesiónmonótona de longitud n Resultado: M(n) ≥ R(n,n,n,n ; 3)

Coloreamos los tríos de números con los colores

Un resultado mejor (Erdös y Szekeres, de nuevo):
n

dados n2+1 números reales, n+1 de ellos forman una sucesión monótona.

¡Son versiones cuantitativas del teorema de Bolzano!

Quinto ejemplo: ¡Fermat no tenía razón!
(¡ejem!, en Zp)
Teorema (Schur) Dado un entero m, podemosencontrar S(m) tal que si p es un primo grande, p ≥ S(m), entonces xm +ym=zm tiene solución no trivial en Zp

Se prueba utilizando el siguiente lema: Lema Dado un entero m, podemos encontrar N(m) tal que si N ≥ Ν y coloreamos el conjunto {1,...,N} con m (m) colores, existirán x, y, z del conjunto con el mismo color y tales que x+y=z Basta comprobar que N(m)= R(3,...,3 ; 2)-1

¿Se conocen los...