Teoría de Ramsey
La teoría de Ramsey estudia cómo el desorden completo es imposible: cualquier estructura suficientemente grande debe contener una subestructura altamente organizada.
Definition
La rama de la combinatoria que pregunta cuán grande debe ser una estructura para garantizar que cualquier partición o coloración de la misma produzca una subestructura monocromática o de otra manera prescrita.
Scope
El área abarca el teorema de Ramsey para grafos e hipergrafos y sus números de Ramsey cuantitativos, resultados de partición para los enteros como los teoremas de Schur, van der Waerden y Hales-Jewett, y la teoría abstracta de Ramsey estructural de conjuntos de parámetros. Ejemplifica el principio extremal-combinatorio de que los sistemas suficientemente grandes no pueden evitar el orden.
Sub-topics
Core questions
- ¿Cuán grande debe ser una estructura para forzar una subestructura ordenada ineludible?
- ¿Cuáles son los umbrales exactos o aproximados, los números de Ramsey, para estas garantías?
- ¿Cómo garantizan los teoremas de partición para los enteros patrones aritméticos?
- ¿Qué familias abstractas de estructuras satisfacen una propiedad de Ramsey?
Key concepts
- Teorema de Ramsey
- Números de Ramsey
- Subestructuras monocromáticas
- Teorema de Van der Waerden
- Teorema de Schur
- Teorema de Hales-Jewett
Clinical relevance
Las garantías de tipo Ramsey de estructura ineludible informan los argumentos de límite inferior en la informática teórica, el análisis de grandes redes y la teoría aditiva de números, mientras que la brecha entre los límites conocidos impulsa el método probabilístico.
History
El teorema de Frank Ramsey de 1930 sobre particiones, originalmente probado para una cuestión de lógica, fue reconocido por Erdos y Szekeres como la semilla de una amplia teoría de la estructura ineludible que creció a lo largo del siglo XX.
Key figures
- Frank Ramsey
- Paul Erdos
- Bartel van der Waerden
Related topics
Seminal works
- graham1990
- landman2003
Frequently asked questions
- ¿Cuál es el eslogan de la teoría de Ramsey?
- El desorden completo es imposible: cualquier sistema suficientemente grande, por muy dispuesto que esté, debe contener una parte ordenada considerable.
- ¿Por qué los números de Ramsey son difíciles de calcular?
- El número de coloraciones a verificar crece astronómicamente, e incluso pequeños números de Ramsey como R(5,5) siguen siendo desconocidos a pesar de un intenso esfuerzo.