Teoría de Grafos Extremales
La teoría de grafos extremales investiga cuán grande o denso puede ser un grafo sin contener una subestructura prescrita, e identifica las configuraciones extremales.
Definition
El estudio del valor máximo o mínimo de un parámetro de grafo, como el número de aristas, sujeto a una restricción estructural como la ausencia de un subgrafo fijo.
Scope
Este tema se centra en problemas de tipo Turan —el número máximo de aristas en un grafo sin un subgrafo dado—, comenzando con los teoremas de Mantel y Turan y extendiéndose al teorema de Erdos-Stone, que determina la densidad extremal asintótica para cualquier subgrafo prohibido. Introduce la interacción entre densidad, estructura y el método de regularidad de Szemeredi.
Core questions
- ¿Cuál es el número máximo de aristas en un grafo de n vértices que no contiene una copia de un subgrafo dado?
- ¿Qué grafos alcanzan estos límites extremales?
- ¿Cómo rige el número cromático de un subgrafo prohibido la respuesta asintótica?
- ¿Cómo reducen los métodos de regularidad los grafos densos a una estructura acotada?
Key concepts
- Subgrafos prohibidos
- Grafo de Turan
- Teorema de Mantel
- Número extremal (número de Turan)
- Teorema de Erdos-Stone
- Lema de regularidad de Szemeredi
Key theories
- Teorema de Turan
- Entre todos los grafos de n vértices sin un subgrafo completo de r+1 vértices, el grafo r-partito completo balanceado tiene la mayor cantidad de aristas, generalizando el límite libre de triángulos de Mantel y sirviendo como ancla para la teoría de grafos extremales.
- Teorema de Erdos-Stone
- Para cualquier subgrafo prohibido H fijo, la densidad máxima de aristas de un grafo libre de H está determinada asintóticamente por el número cromático de H, unificando los resultados extremales de tipo Turan.
Clinical relevance
Los resultados de densidad extremal delimitan la estructura de grandes redes y sistemas de restricciones, y el método de regularidad desarrollado en esta área tiene aplicaciones en pruebas de propiedades, informática teórica y combinatoria aditiva.
History
El límite libre de triángulos de Mantel de 1907 y la generalización de Turan de 1941 iniciaron el campo; la teoría de Erdos-Stone-Simonovits y el lema de regularidad de Szemeredi lo convirtieron en un pilar central de la combinatoria moderna.
Key figures
- Paul Turan
- Paul Erdos
- Endre Szemeredi
Related topics
Seminal works
- bollobas1998
- diestel2017
Frequently asked questions
- ¿Qué es un problema de tipo Turan?
- Pregunta por el mayor número de aristas que puede tener un grafo sin contener un subgrafo fijo; el ejemplo canónico es el número máximo de aristas en un grafo libre de triángulos.
- ¿Cómo se relaciona la teoría de grafos extremales con la teoría de Ramsey?
- Ambas estudian la estructura ineludible, pero la teoría extremal fija un subgrafo prohibido y maximiza las aristas, mientras que la teoría de Ramsey garantiza una estructura monocromática una vez que el grafo es lo suficientemente grande.