Teoría de grafos extremos

En la teoría de grafos , un grafo extremo con respecto a una propiedad es un grafo tal que agregar cualquier borde hace que el gráfico verifique la propiedad . El estudio de grafos extremos se puede dividir en dos temas: la búsqueda de límites inferiores en el número de aristas necesarias para asegurar la propiedad (incluso en otros parámetros como el grado mínimo) y la caracterización de los propios grafos extremos. PAG{\ Displaystyle P}PAG{\ Displaystyle P}

El estudio de grafos extremos es una rama del estudio combinatorio de grafos.

Definición rigurosa

Sea una propiedad en los gráficos que se conserva agregando bordes y un gráfico arbitrario. se dice que es extremo con respecto a la propiedad P si: PAG{\ Displaystyle P}GRAMO=(V,mi){\ Displaystyle G = (V, E)}GRAMO{\ Displaystyle G}

• GRAMO{\ Displaystyle G}no verifique  ;PAG{\ Displaystyle P}
• ∀(X,y){\ Displaystyle \ forall (x, y)}no adyacente en , el gráfico comprueba .GRAMO{\ Displaystyle G}GRAMO′=(V,mi∪(X,y)){\ Displaystyle G '= (V, E \ cup (x, y))}PAG{\ Displaystyle P}

Por otro lado, una función es un límite inferior en comparación con la propiedad si hace posible asegurar que satisface . F{\ Displaystyle f}PAG{\ Displaystyle P}∀GRAMO=(V,mi),|mi|>F(|V|){\ Displaystyle \ forall G = (V, E), | E |> f (| V |)}GRAMO{\ Displaystyle G}PAG{\ Displaystyle P}

Tenga en cuenta que los gráficos extremos no satisfacen necesariamente el mejor límite inferior.

Ejemplos de

Para la propiedad "no admitir triángulos como subgrafo", un límite inferior es . Los gráficos extremos son exactamente los gráficos bipartitos y . PAG={\ Displaystyle P =}|mi|=|V|24{\ Displaystyle | E | = {\ frac {| V | ^ {2}} {4}}} Kk,k{\ Displaystyle K_ {k, k}}Kk,k+1{\ Displaystyle K_ {k, k + 1}}

De manera más general, para "no admitir una camarilla de tamaño l como subgrafo", los gráficos extremos son los gráficos completos (l-1) -partis . Este resultado es una consecuencia del teorema de Turán , que también proporciona un límite inferior (demasiado largo para incluirlo aquí). PAGl={\ Displaystyle P_ {l} =}Kk,..,k,k+1,..,k+1{\ Displaystyle K_ {k, .., k, k + 1, .., k + 1}}

Artículos relacionados

• Erdős - Teorema de Stone

Referencias

• (en) JH Van Lint y RM Wilson , Un Curso de Combinatoria , Cambridge University Press, 2001, 2 ª ed. ( ISBN  0-521-80340-3 ) , en particular el capítulo 4: "Teorema de Turan y gráficos extremos"
• (en) Reinhard Diestel , teoría de grafos , Springer-Verlag, Heidelberg, Nueva York, 1997, 2000, 2005 [ leer on-line ] la 3 ª ed.