Diferencia entre revisiones de «Teoría de Ramsey»

Contenido eliminado Contenido añadido
Rovnet (discusión · contribs.)
+ teoremas, problemas abiertos, img
Línea 1:
[[Archivo:Pleiades large.jpg|thumb|300px|Del total de estrellas del cielo nocturno 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 el orden debe aparecer. 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?
 
Línea 16:
 
== Resultados ==
OtrosAlgunos dosresultados teoremas básicosimportantes 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 Erdős-Szekeres]](1936)'''. Si tenemos n<sup>2</sup> + 1 números reales, n + 1 de ellos forman una sucesión monótona.
 
* '''[[Teorema de Vanvan der Waerden]]: (1927)'''. Para lostodo númerospar naturalesde '''c'''enteros l y '''n'''c, existe elun númeroN naturaltal '''N(c,n)'''que, dedada taluna maneraprogresión quearitmética enP cadade '''c'''-[[coloraciónlongitud dea grafos|coloración]]lo delmenos conjuntoN de(en númerosun <math>1,2,grupo ...,aditivo N(c,nZ)\,</math>, existey si unacoloreamos la [[progresión aritmética]]P decon longitudc '''n'''colores, cuyosentonces elementosexiste sonuna todossub-progresión delaritmética mismoPo color (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 estan coloreadas con un solo color. Esto es, si se juega el [[tres en linea]] 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''' ó '''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.
 
 
==Naturaleza de los resultados==
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úsquedaBúsqueda porde 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 [[Crecimiento exponencial|exponencial]], o incluso más rápido que la [[función de Ackermann]] no son infrecuentes.
 
==Problemas abiertos==
<!-- <!-- == Resultados de tipo Ramsey y de tipo Turán== -->
* '''Problema de Erdős-Szekeres''': este problema corresponde a la generalización del problema del final feliz, y es:
<math>N(n)=2^{n-2} -1 \,</math>
* '''Problema del Limite de R<sub>k</sub> = R(k,k;2)'''. Existe <math>\lim_{k \to \infty} R_k ^{\frac{1}{k}} \;</math>, y de existir ¿Cuál es su valor?
 
== Véase también ==