Ir al contenido

Teoría de Ramsey

De Wikipedia, la enciclopedia libre
Según la teoría de Ramsey, del total de estrellas del cielo nocturno, siempre podemos seleccionar un subconjunto de ellas para dibujar diferentes objetos como: un triángulo, un cuadrilátero, un paraguas o un pulpo.

La teoría de Ramsey, llamada así por Frank P. Ramsey, es un campo de las matemáticas que estudia las condiciones bajo las cuales debe aparecer el orden.

Los problemas de la teoría de Ramsey son típicamente de la forma: ¿Cuántos elementos debe contener una estructura para garantizar la existencia de una propiedad particular?

El desorden completo es imposible
Theodore S. Motzkin[1]

Ejemplos

[editar]

Supongamos que n palomas han sido alojadas en m nidos. ¿Qué tamaño ha de tener n, con respecto a m, para que se pueda garantizar que al menos, un nido contenga dos palomas?. La respuesta está dada por el principio del palomar: si n > m por lo menos un nido tendrá al menos dos palomas. La teoría de Ramsey generaliza este resultado, como se explica a continuación.

Un resultado típico de la teoría de Ramsey se inicia con alguna estructura matemática que se corta en trozos. ¿Qué tamaño ha de tener la estructura original con el fin de garantizar que al menos una de las piezas tenga una propiedad interesante dada?

Por ejemplo, consideremos un grafo completo de orden n, es decir, hay n vértices y cada vértice está conectado a todos los otros vértices por medio de una arista. Un grafo completo de orden 3 se llama triángulo. Ahora bien, cada arista puede tener uno de los siguientes colores: rojo o azul. ¿Cómo de grande debe ser n para poder garantizar que exista un triángulo azul o un triángulo rojo? Resulta que la respuesta es 6. Véase el artículo sobre el teorema de Ramsey para una prueba rigurosa.

Otra manera de expresar este resultado es el siguiente: en cualquier actividad con al menos seis personas, hay tres personas que son mutuamente conocidas o mutuamente desconocidas. Véase el teorema de la amistad.

Este es un caso especial del teorema de Ramsey, que dice que para cualquier entero dado c, y dado los enteros n1,...,nc, existe el número: R(n1,...,nc), llamado número de Ramsey, tal que si las aristas de un grafo completo de orden R(n1,...,nc) se colorean con c colores distintos, entonces para algún i entre 1 y c, debe contener un subgrafo completo de orden ni cuyas aristas están todas coloreadas con el color i. El caso especial de arriba tiene c = 2 y n1 = n2 = 3.

Para dos colores se conocen los siguientes valores exactos y cotas para R(r, s):

r, s 3 4 5 6 7 8 9 10
3 6
4 9 18
5 14 25 43–48
6 18 36–41 58–87 102–165
7 23 49–61 80–143 115–298 205–540
8 28 59–84 101–216 134–495 219–1031 282–1870
9 36 73–115 133–316 183–780 252–1713 329–3583 565–6588
10 40–42 92–149 149–442 204–1171 292–2826 343–6090 581–12677 798–23556
11 47-50 102-191 183-633 262-1804 405-4553 457-10630 22325 45881
12 53-59 128-238 203-848 294-2566 417-6954 16944 38832 81123
13 60-68 138-291 233-1138 347-3703 511-10578 817-27485 64864
14 67-77 147-349 267-1461 5033 15263 41525
15 74-87 158-417 275-1878 401-6911 22112 873-63609 1313

Como R(r, s) = R(s, r), hay una simetría trivial con respecto la diagonal. También es trivial el caso R(n,2) ya que R(n,2)=n.

Esta tabla está extraída del survey "Small Ramsey Numbers" de Stanisław Radziszowski[2]​, excepto R(4,6)≥36, probado por Geoffrey Exoo en 2012;[3]R(3,10) ≤ 42, probado por Jan Goedgebeur y Stanisław Radziszowski en 2012;[4]​ y R(4,8) ≥ 58, probado por Hiroshi Fujita en 2012.[5]

Para tres colores, el único valor exacto no trivial conocido es R(3,3,3)=17.

De idéntica forma se puede definir el número de Ramsey de grafos que no sean completos, conociéndose para dos colores y grafos con a lo más 5 vértices, todos los valores exactos salvo los dos casos formados por dos grafos completos con 5 vértices y por uno completo de 5 vértices menos una arista y uno completo de 5 vértices.

Resultados

[editar]

Algunos resultados importantes de teoría de Ramsey son:

  • Teorema de Ramsey Infinito (1928). Si tenemos un conjunto infinito y distribuimos sus elementos en un número finito de cajas, entonces hay una caja que contiene infinitos elementos.
  • Teorema de Bolzano. Toda sucesión infinita de números reales contiene una subsucesión infinita creciente o decreciente.
  • Problema del final feliz (Erdős, Szekeres & Klein; 1933). Dados 5 puntos en el plano (de forma que cada 3 de ellos no sean colineales), hay cuatro que forman un cuadrilátero convexo.
  • Teorema de la amistad (Ramsey; 1928). En cualquier reunión de 6 personas, o bien 3 de ellas se conocen entre sí, o bien, 3 de ellas no se conocen entre sí.
  • Teorema de van der Waerden (1927). Para todo par de enteros l y c, existe un N tal que, dada una progresión aritmética P de longitud a lo menos N (en un grupo aditivo Z), y si coloreamos la progresión P con c colores, entonces existe una sub-progresión aritmética Po monocromática de longitud l.
  • Teorema de Hales-Jewett (1963): Para enteros n y c, existe el número H de manera que las celdas de un cubo H-dimensional n×n×n×...×n son coloreados con c colores, debe existir una fila, columna, etc. de longitud n en donde sus celdas están coloreadas con un solo color. Esto es, si se juega el tres en línea en un tablero-hipercubo de dimensiones suficientemente grandes, entonces no se puede terminar el juego en empate, no importando que tan grande sea n (la longitud de X o 0 necesaria para ganar la partida), ni el número c de jugadores. El teorema de Hales-Jewett implica el teorema de Van der Waerden.
  • Teorema de Schur. Para todo número c, hay un N tal que si los números 1,2,..., N son coloreados por c colores, existe un par de enteros x, y tal que x, y, x+y tienen el mismo color.

Naturaleza de los resultados

[editar]

Los resultados en la teoría de Ramsey normalmente tienen dos características básicas. En primer lugar, generalmente no son constructivas, los resultados muestran la existencia de alguna estructura, pero no se da una receta o procedimiento para encontrarla (que no sea la Búsqueda de fuerza bruta). En segundo lugar, mientras los resultados de la teoría de Ramsey nos dicen que un objeto lo suficientemente grande deberá contener necesariamente una estructura dada, a menudo la prueba de estos resultados requiere que estos objetos sean enormemente grandes con límites que crecen de manera exponencial.

Problemas abiertos

[editar]
  • Problema de Erdős-Szekeres: este problema corresponde a la generalización del problema del final feliz, y es:

  • Problema del Límite de R(k,k;2) = R(k,k) = Rk. ¿Existe ?, y de existir ¿Cuál es su valor? Se conoce que en caso de existir se encuentra en el intervalo (√2, 4]

Véase también

[editar]

Notas

[editar]
  1. "S. A. Soman" (21 de agosto de 2008). "Computational Methods for Large Sparse Power Systems Analysis". p. 31. 
  2. "Small Ramsey Numbers" Stanisław P. Radziszowski (primerat versión: Junio 11, 1994; revisión #16: Enero 15, 2021).
  3. B. McKay, Ramsey Graphs
  4. Goedgebeur, Jan; Radziszowski, Stanisław (2012). «New computational upper bounds for Ramsey numbers R(3,k)». arXiv:1210.5826. 
  5. Fujita, Hiroshi (2012). «A New Lower Bound for the Ramsey Number R(4, 8)». arXiv:1212.1328. 

Referencias

[editar]