Teorema de Ramsey y números de Ramsey
El teorema de Ramsey garantiza que cualquier grafo completo bicolor suficientemente grande contiene una camarilla monocromática, y los números de Ramsey cuantifican cuán grande es lo suficiente.
Definition
El número de Ramsey R(s,t) es el entero más pequeño n tal que cada coloración rojo-azul de las aristas del grafo completo en n vértices contiene una camarilla roja en s vértices o una camarilla azul en t vértices.
Scope
Este tema abarca la forma gráfica del teorema de Ramsey, la definición de los números de Ramsey R(s,t), los casos clásicos pequeños como R(3,3)=6, la cota superior de Erdos-Szekeres y la cota inferior probabilística de Erdos, y la extensión a los números de Ramsey multicolor y de hipergrafos. Constituye el núcleo cuantitativo de la teoría de Ramsey.
Core questions
- ¿Qué tan grande debe ser un grafo completo para forzar una camarilla monocromática de un tamaño dado?
- ¿Cuáles son los valores exactos y las cotas conocidas para los números de Ramsey?
- ¿Cómo proporcionan los argumentos probabilísticos cotas inferiores para los números de Ramsey?
- ¿Cómo se generaliza el teorema a varios colores y a hipergrafos?
Key concepts
- Teorema de Ramsey para grafos
- Número de Ramsey R(s,t)
- Camarillas monocromáticas
- Cota de Erdos-Szekeres
- Cotas inferiores probabilísticas
- Números de Ramsey multicolor y de hipergrafos
Key theories
- Cota superior de Erdos-Szekeres
- Los números de Ramsey son finitos y están acotados por R(s,t) siendo como máximo el coeficiente binomial de s+t-2 sobre s-1, una cota basada en recurrencia que demuestra el teorema de Ramsey con estimaciones explícitas.
- Cota inferior probabilística de Erdos
- Al contar las camarillas monocromáticas esperadas en una coloración aleatoria, Erdos demostró en 1947 que el número de Ramsey diagonal R(s,s) crece al menos exponencialmente, una aplicación fundacional del método probabilístico.
Clinical relevance
El método probabilístico introducido a través de las cotas inferiores de los números de Ramsey se convirtió en una herramienta central en la combinatoria y la informática teórica, y las garantías de tipo Ramsey sustentan las cotas inferiores en la comunicación y las estructuras de datos.
History
Erdos y Szekeres redescubrieron y cuantificaron el teorema de Ramsey en 1935 mientras estudiaban polígonos convexos; la cota inferior de Erdos de 1947 basada en coloración aleatoria dio origen al método probabilístico.
Key figures
- Frank Ramsey
- Paul Erdos
- George Szekeres
Related topics
Seminal works
- graham1990
Frequently asked questions
- ¿Por qué R(3,3) es igual a seis?
- Entre seis personas cualesquiera, tres son conocidos mutuos o tres son extraños mutuos, mientras que cinco personas pueden organizarse para evitar ambos, por lo que seis es el umbral exacto.
- ¿Se conocen los números de Ramsey exactos?
- Solo se conocen exactamente unos pocos; incluso R(5,5) está abierto, y el conocimiento actual solo lo reduce a un rango, porque el espacio de búsqueda crece demasiado rápido para resolverse mediante computación.