Teoría de grafos extremales
¿Cuál es el máximo número posible de aristas en un grafo con
vértices tal que no contiene un ciclo?
vértices no contiene ningún triángulo como subgrafo, ¿cuál es el máximo número de aristas que puede tener?
Por el Teorema de Mantel, la respuesta a esta pregunta es
vértices; es decir, tal que sus dos partes difieren en tamaño en a lo más 1.
vértices para garantizar que, sin importar cómo las aristas estén distribuidas, el clique
, y proviene del Teorema de Turán.
-libre, entonces puede tener a lo sumo este número de aristas:
grafos independientes, con distribución de tamaños lo más equitativa posible.
vértices para garantizar que, sin importar cómo las aristas estén distribuidas, el clique
La respuesta a esta pregunta proviene del Teorema de Erdös-Stone.
, queremos encontrar el mínimo valor posible de cierto parámetro global del grafo
al parámetro que cuenta la cantidad de aristas, y
[3] En particular, el Teorema de Turán pronto se convertiría en una motivación para probar resultados tales como el Teorema de Ërdos-Stone-Simonovits (1946).
[4] Este último resultado es interesante, ya que relaciona el número cromático con el máximo número de aristas en un grafo que es
, its subgraph density is defined as
El Teorema de Turán implica que si un grafo
Más aún, el Teorema de Ërdos-Stone-Simonovits establece que
es el máximo número de aristas posible que un grafo
Otro resultado por Ërdos, Reyni y Sós (1966) establece que un grafo en
como subgrafo, tiene a lo sumo la siguiente cantidad de aristas.
Hay, sin embargo, otro tipo de teoremas en teoría extremal de grafos, que consisten en buscar condiciones que garanticen la existencia de una estructura que cubra todos los vértices del grafo.
Note que es incluso posible para un grafo denso con
Es, por lo tanto, más útil en algunas ocasiones considerar el parámetro del grado mínimo, definido así Un grado mínimo que es suficientemente grande descarta la posibilidad de tener vértices 'patológicos'; si el mínimo grado en un grafo
fuera 1, por ejemplo, entonces dicho grafo no puede tener vértices aislados, aún si tuviera muy pocas aristas.
Un resultado importante en teoría de grafos extremal es el Teorema de Dirac, que establece que en cualquier grafo
vértices y grado mínimo mayor o igual que
Otro teorema[3] establece que si el grado mínimo en un grafo
Incluso si muchas observaciones importantes se han podido hacer en el campo de teoría extremal de grafos, muchas preguntas también yacen sin contestar aún.
Otra conjetura importante en teoría extremal de grafos fue formulada por Sidorenko en 1993.
