Teorema de Turán

El teorema de Turán es el resultado de la teoría de grafos extremos descubierta por Pál Turán .

Este teorema da un límite superior al número de aristas en los gráficos que no contienen cliques mayores que un parámetro r , y da una caracterización de los gráficos que alcanzan este límite, son los gráficos de Turán .

Este resultado de 1941 lanzó la teoría de los gráficos extremos y tiene muchas pruebas.

El teorema

Cualquier gráfico G que tenga n vértices y que no contenga una camarilla de tamaño mayor que r (es decir, K r +1 libre) tiene como máximo el siguiente número de aristas:

r-1r⋅no22=(1-1r)⋅no22.{\ Displaystyle {\ frac {r-1} {r}} \ cdot {\ frac {n ^ {2}} {2}} = \ left (1 - {\ frac {1} {r}} \ right) \ cdot {\ frac {n ^ {2}} {2}}.}

Este límite se alcanza mediante el gráfico de Turán T ( n , r ).

Teorema de mantel

El caso especial r = 2, corresponde al teorema de Mantel:

El número máximo de aristas en un gráfico sin triángulo es⌊no2/4⌋.{\ Displaystyle \ lfloor n ^ {2} / 4 \ rfloor.}

Bibliografía

(en) Paul Turán , “  Sobre un problema extremo en teoría de grafos  ” , Matematikai és Fizikai Lapok , vol.  48,1941, p.  436-452

Notas y referencias

1. Martin Aigner y Günter M. Ziegler , Divine Reasonings , Springer ( leer en línea ) , p.  235-240.
2. (in) Martin Aigner, "  Teorema del grafo de Turán  " , Am. Math. Mensual , vol.  102,1995, p.  808-816 ( leer en línea )( Premio Paul R. Halmos-Lester R. Ford 1996 ).