¿Cuál es la diferencia entre la teoría de Ramsey y la teoría de los grafos extremos?

Question

Wikipedia nos enseña que los problemas de la teoría de Ramsey suelen plantear una pregunta de la forma "¿cuántos elementos de alguna estructura debe haber para garantizar que se cumpla una determinada propiedad?"

También nos enseña que "la teoría de los grafos extremos estudia los grafos extremos (máximos o mínimos) que satisfacen una determinada propiedad". Esto suena muy parecido. Tomemos el teorema de Turan (el ejemplo básico de un teorema EGT): da un límite al número de aristas de un grafo sin camarillas (para un tamaño de camarilla dado). Dicho de otro modo, nos dice cuántos elementos (aristas) de una determinada estructura (grafo con un número fijo de vértices) debe haber para garantizar que se cumpla una determinada propiedad (existencia de una camarilla de un tamaño específico).

Se puede argumentar que en EGT tratamos de entender la estructura de los objetos extremos, pero no veo por qué la teoría de Ramsey no debería tratar de hacer lo mismo, y tampoco veo cómo se hace en el (hermoso) teorema de Erdos-Stone que se considera un teorema fundamental de EGT.

Entonces, ¿hay una diferencia real o es sólo cuestión de gustos?

Answer 1

Estoy de acuerdo con el comentario de Shahab más arriba. La teoría de Ramsey es, sin duda, más general, y suele ocuparse de cuestiones relacionadas con el orden inevitable que contienen incluso las estructuras más caóticas. Algunas de estas preguntas (y respuestas) pueden plantearse (o resolverse) en un contexto de teoría de grafos utilizando las técnicas de la teoría de grafos extremos.

La teoría de los grafos extremos tiende a centrarse en cuestiones específicas de los grafos en cuanto a la minimalidad y la maximalidad. Preguntas como: ¿cómo puedo garantizar que cada vértice de un subgrafo tiene un grado mínimo determinado? ¿Cuántos ciclos disjuntos debe tener un grafo de tamaño $m$ ¿tiene? O dado un $k$ -gráfico regular ¿cuál es su circunferencia mínima/máxima? Se trata de preguntas que tienen que ver con las construcciones explícitas y la naturaleza de los objetos de la teoría de grafos. A veces, los resultados que se obtienen encuentran aplicación en el mundo "real", pero a menudo simplemente nos ayudan a comprender mejor la naturaleza extrema de los grafos regulares.

Creo que esa es la diferencia que se sugiere al final de tu pregunta. La teoría de los grafos extremos estudia las propiedades extremas de los grafos regulares, mientras que la teoría de Ramsey se ocupa más de las propiedades necesarias (regulares) de los grafos extremos.