Teoría de grafos extremales

Un Grafo de Turán T(n,r) es un ejemplo de un grafo extremal. Es el grafo en n vértices con el máximo número posible de aristas tal que no se forman (r + 1)- cliques. En particular, este grafo es T(13,4).

La teoría de grafos extremales es una rama de las matemáticas que estudia cómo es que propiedades globales de un grafo pueden influir en su subestructura local.^[1]​ Esta rama abarca un vasto número de resultados que describen cómo ciertas propiedades de las gráficas - número de vértices, número de aristas, densidad de aristas, número cromático, o cintura, por ejemplo - garantizan la existencia de ciertas subestructuras locales.

Uno de los principales objetos de estudio de esta área de teoría de grafos son los grafos extremales, que son o bien maximales o minimales con respecto a algún parámetro global, y tales que contienen (o no contienen) cierta subestructura local - ya sea un clique, o una coloración de sus aristas.

Ejemplos

La teoría de grafos extremales puede ser motivada por preguntas tales como las siguientes:

Pregunta 1. ¿Cuál es el máximo número posible de aristas en un grafo con ${\displaystyle n}$ vértices tal que no contiene un ciclo?

Si un grafo con ${\displaystyle n}$ vértices contiene al menos ${\displaystyle n}$ aristas, entonces debe contener un ciclo. Más aún, cualquier árbol en ${\displaystyle n}$ vértices contiene ${\displaystyle n-1}$ aristas y no contiene ciclos. Por lo tanto, la respuesta a esta pregunta es ${\displaystyle n-1}$, y los árboles son los grafos extremales.^[2]​

Pregunta 2. Si un grafo con ${\displaystyle n}$ 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 ${\displaystyle \lfloor n^{2}/4\rfloor }$. El grafo extremal correspondiente es el grafo bipartito completo en ${\displaystyle (\lceil n/2\rceil ,\lfloor n/2\rfloor )}$ vértices; es decir, tal que sus dos partes difieren en tamaño en a lo más 1.

La siguiente es una generalización de la Pregunta 2:

Pregunta 3. Sea ${\displaystyle r}$ un entero positivo. ¿Cuántas aristas debe haber en un grafo ${\displaystyle G}$ con ${\displaystyle n}$ vértices para garantizar que, sin importar cómo las aristas estén distribuidas, el clique ${\displaystyle K_{r}}$ esté embedido como subgrafo?

La respuesta a esta pregunta es

${\displaystyle {\frac {r-2}{r-1}}\cdot {\frac {n^{2}}{2}}+1}$ ,

y proviene del Teorema de Turán. Por lo tanto, si un grafo ${\displaystyle G}$ con ${\displaystyle n}$ vértices es ${\displaystyle K_{r+1}}$-libre, entonces puede tener a lo sumo este número de aristas:

${\displaystyle \left\lfloor {\frac {(r-2)n^{2}}{2(r-1)}}\right\rfloor =\left\lfloor \left(1-{\frac {1}{r-1}}\right){\frac {n^{2}}{2}}\right\rfloor }$.

El grafo extremal correspondiente es un Grafo de Turán, el cual se puede contemplar en la Figura de arriba. Es la unión completa de ${\displaystyle r-1}$ grafos independientes, con distribución de tamaños lo más equitativa posible.

A continuación, una generalización de la Pregunta 3 para grafos no-completos:

Pregunta 4. Sea ${\displaystyle r}$ un entero positivo, y ${\displaystyle H}$ un grafo no completo. ¿Cuántas aristas debe haber en un grafo ${\displaystyle G}$ con ${\displaystyle n}$ vértices para garantizar que, sin importar cómo las aristas estén distribuidas, el clique ${\displaystyle H}$ esté embedido como subgrafo?

La respuesta a esta pregunta proviene del Teorema de Erdös-Stone.

Varios de los resultados fundamentales de la teoría extremal de grafos provienen de respuestas a preguntas formuladas de la manera siguiente:

Pregunta 5. Dada una propiedad ${\displaystyle P}$, una invariante ${\displaystyle u}$, y una familia de grafos ${\displaystyle {\mathcal {S}}}$, queremos encontrar el mínimo valor posible de cierto parámetro global del grafo ${\displaystyle m}$ tal que cualquier grafo en ${\displaystyle {\mathcal {S}}}$ con ${\displaystyle u>m}$ cumple la propiedad ${\displaystyle P}$.

En la Pregunta 1, por ejemplo, ${\displaystyle H}$ corresponde al conjunto de grafos en ${\displaystyle n}$-vértices, ${\displaystyle P}$ a la propiedad de contener un ciclo, ${\displaystyle u}$ al parámetro que cuenta la cantidad de aristas, y ${\displaystyle m=n-1}$.

Historia

La teoría de grafos extremales es, en su sentido más estricto, una rama de la teoría de grafos desarrollada y amada por los Húngaros. —Bollobás (2004)

El Teorema de Mantel (1907), así como el Teorema de Turán (1941) fueron de los primeros grandes descubrimientos en la teoría extremal de grafos.^[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 ${\displaystyle H}$-libree. Una demostración alternativa de Ërdos-Stone-Simonovits fue encontrada 1975, y utilizaba el Teorema de Szemerédi, una técnica esencial para la resolución de problemas de teoría de grafos extremal.^[3]​

Algunos resultados: densidades y desigualdades

Un parámetro global cuyo rol es central en la teoría de grafos extremal es la densidad de homomorfismos. Dado un grafo ${\displaystyle G=(V,E)}$ y otro grafo ${\displaystyle H}$, su densidad de homomorfismo de

${\displaystyle t(H,G)=({\text{number of copies of }}H{\text{ in }}G)/{\binom {n}{|v(H)|}}}$.

En particular, edge density is the subgraph density for ${\displaystyle H=K_{2}}$, for a graph ${\displaystyle H}$, its subgraph density is defined as

${\displaystyle t(K_{2},G)=|E|/{\binom {|V|}{2}}}$.

Los teoremas mencionados en secciones previas de este artículo pueden ser reformulados en términos de densidades de homomorfismos. Por ejemplo, el Teorema de Mantel implica que la densidad de homomorfismo de ${\displaystyle K_{2}}$ en un grafo libre de triángulos es a lo sumo ${\displaystyle 1/2}$. El Teorema de Turán implica que si un grafo ${\displaystyle G}$ es ${\displaystyle K_{r}}$-libre, entonces ${\displaystyle t(K_{2},G)\leq (r-2/r-1)+o(1)}$.

Más aún, el Teorema de Ërdos-Stone-Simonovits establece que

${\displaystyle {\mbox{ex}}(n;H)=\left(1-{\frac {1}{\chi (H)-1}}+o(1)\right){n \choose 2},}$

donde ${\displaystyle ex(n;H)}$ es el máximo número de aristas posible que un grafo ${\displaystyle H}$-libre con ${\displaystyle n}$ vértices puede tener, y ${\displaystyle \chi (H)}$ es el número cromático de ${\displaystyle H}$. Una interpretación de este resultado es que la densidad de homomorfismo con respecto a ${\displaystyle K_{2}}$ (arista) en un grafo ${\displaystyle H}$-libre graph es asintóticamente ${\displaystyle 1-(1/\chi (H)-1)}$.

Otro resultado por Ërdos, Reyni y Sós (1966) establece que un grafo en ${\displaystyle n}$ que no contiene copias de ${\displaystyle C_{4}}$ como subgrafo, tiene a lo sumo la siguiente cantidad de aristas.

${\displaystyle \left({\frac {1}{2}}+o(1)\right)n^{3/2}}$

Condiciones relacionadas al grado mínimo

Los teoremas de la sección previa prueban la existencia de un objeto pequeño en un grafo que es posiblemente muy grande. 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 ${\displaystyle n}$ vértices y

${\displaystyle {\binom {n-1}{2}}}$

aristas tener un vértice aislado, aún si casi todas las aristas posibles están presentes en el grafo. Intuitivamente, condiciones tales como el número de ejes no dan indicación suficiente acerca de cómo están distribuidas las aristas en un grafo, lo cual conlleva a resultados que solo garantizan estructuras de tamaño limitado en grafos con una cantidad arbitraria de vértices.

Es, por lo tanto, más útil en algunas ocasiones considerar el parámetro del grado mínimo, definido así

${\displaystyle \delta (G)=\min _{v\in G}d(v).}$

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 ${\displaystyle G}$ 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 ${\displaystyle G}$ con ${\displaystyle n}$ vértices y grado mínimo mayor o igual que ${\displaystyle n/2}$ contiene un ciclo Hamiltoniano.

Otro teorema^[3]​ establece que si el grado mínimo en un grafo ${\displaystyle G}$ es ${\displaystyle \delta \geq 3}$, y la cintura es ${\displaystyle g\geq 3}$, entonces el número de vértices en el grafo es al menos:

${\displaystyle n_{0}(\delta ,g)={\begin{cases}1+{\frac {\delta }{\delta -2}}[(\delta -1)^{(g-1)/2}-1]&{\text{si }}g{\text{ es impar,}}\\{\frac {2}{\delta -2}}[(\delta -1)^{g/2}-1]&{\text{si }}g{\text{ es par.}}\end{cases}}}$

Algunas preguntas abiertas

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. Por ejemplo, el Problema de Zarankiewicz pregunta por el máximo número posible de aristas en un grafo bipartito con ${\displaystyle n}$ vértices que no tiene subgrafos que son completos bipartitos de tamaño ${\displaystyle m}$.

Otra conjetura importante en teoría extremal de grafos fue formulada por Sidorenko en 1993. Se conjetura que si ${\displaystyle H}$ es un grafo bipartito, entonces su densidad de grafón (una noción generalizada de densidad de homomorfismo) ${\displaystyle t(H,W)}$ es al menos ${\displaystyle t(K_{2},W)^{|v(H)|}}$.

Véase también

• Teoría de Ramsey
• Densidad de homomorfismos
• Problema del subgrafo prohibido

Referencias

1. Bollobás, 2004, p. 9
2. Bollobás, 2004, p. 9
3. Bollobás, 1998, p. 104
4. Diestel, 2010

Bibliografía

• Bollobás, Béla (2004), Extremal Graph Theory, New York: Dover Publications, ISBN 978-0-486-43596-1 ..
• Bollobás, Béla (1998), Modern Graph Theory, Berlin, New York: Springer-Verlag, pp. 103-144, ISBN 978-0-387-98491-9 ..
• Diestel, Reinhard (2010), Graph Theory (4th edición), Berlin, New York: Springer-Verlag, pp. 169-198, ISBN 978-3-642-14278-9, archivado desde el original el 28 de mayo de 2017, consultado el 7 de enero de 2014 ..
• M. Simonovits, Slides from the Chorin summer school lectures, 2006. [1]

• Datos: Q739245