Teoría de grafos extremos

El grafo de Turán T ( n , r ) es un ejemplo de grafo extremal. Tiene el máximo número posible de aristas para un grafo en n vértices sin ( r  + 1)- cliques . Esto es T (13,4).

La teoría de grafos extremos es una rama de la combinatoria , en sí misma un área de las matemáticas , que se encuentra en la intersección de la combinatoria extrema y la teoría de grafos . En esencia, la teoría de grafos extremos estudia cómo las propiedades globales de un grafo influyen en la subestructura local. ^[1] Los resultados de la teoría de grafos extremos tratan de conexiones cuantitativas entre varias propiedades de grafos , tanto globales (como el número de vértices y aristas) como locales (como la existencia de subgrafos específicos), y los problemas de la teoría de grafos extremos a menudo se pueden formular como problemas de optimización: ¿qué tan grande o pequeño puede ser un parámetro de un grafo, dadas algunas restricciones que el grafo tiene que satisfacer? ^[2] Un grafo que es una solución óptima a tal problema de optimización se llama grafo extremal , y los grafos extremales son objetos de estudio importantes en la teoría de grafos extremales.

La teoría de grafos extremos está estrechamente relacionada con campos como la teoría de Ramsey , la teoría de grafos espectrales , la teoría de la complejidad computacional y la combinatoria aditiva , y con frecuencia emplea el método probabilístico .

Historia

La teoría de grafos extremos, en su sentido más estricto, es una rama de la teoría de grafos desarrollada y amada por los húngaros.

Bollobás (2004) ^[3]

El teorema de Mantel (1907) y el teorema de Turán (1941) fueron algunos de los primeros hitos en el estudio de la teoría de grafos extremales. ^[4] En particular, el teorema de Turán se convertiría más tarde en una motivación para el hallazgo de resultados como el teorema de Erdős-Stone (1946). ^[1] Este resultado es sorprendente porque conecta el número cromático con el número máximo de aristas en un grafo libre. Una prueba alternativa de Erdős-Stone se dio en 1975, y utilizó el lema de regularidad de Szemerédi , una técnica esencial en la resolución de problemas de teoría de grafos extremales. ^[4] ${\displaystyle H}$

Temas y conceptos

Coloración de gráficos

El gráfico de Petersen tiene número cromático 3.

Una coloración (de vértices) adecuada de un grafo es una coloración de los vértices de tal manera que no haya dos vértices adyacentes que tengan el mismo color. El número mínimo de colores necesarios para colorear correctamente se denomina número cromático de , denotado como . Determinar el número cromático de grafos específicos es una cuestión fundamental en la teoría de grafos extremales, porque muchos problemas en el área y áreas relacionadas se pueden formular en términos de coloración de grafos. ^[2] ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle \chi (G)}$

Dos límites inferiores simples para el número cromático de un grafo están dados por el número de camarilla —todos los vértices de una camarilla deben tener colores distintos— y por , donde es el número de independencia, porque el conjunto de vértices con un color dado debe formar un conjunto independiente . ${\displaystyle G}$ ${\displaystyle \omega (G)}$ ${\displaystyle |V(G)|/\alpha (G)}$ ${\displaystyle \alpha (G)}$

Una coloración voraz da como resultado el límite superior , donde es el grado máximo de . Cuando no es un ciclo impar ni una camarilla, el teorema de Brooks establece que el límite superior se puede reducir a . Cuando es un grafo plano , el teorema de los cuatro colores establece que tiene un número cromático de cuatro como máximo. ${\displaystyle \chi (G)\leq \Delta (G)+1}$ ${\displaystyle \Delta (G)}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle \Delta (G)}$ ${\displaystyle G}$ ${\displaystyle G}$

En general, se sabe que determinar si un gráfico dado tiene una coloración con un número prescrito de colores es NP-difícil .

Además de la coloración de vértices, también se estudian otros tipos de coloración, como la coloración de aristas . El índice cromático de un grafo es el número mínimo de colores en una coloración adecuada de las aristas de un grafo, y el teorema de Vizing establece que el índice cromático de un grafo es o . ${\displaystyle \chi '(G)}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle \Delta (G)}$ ${\displaystyle \Delta (G)+1}$

Subgrafos prohibidos

El problema del subgrafo prohibido es uno de los problemas centrales de la teoría de grafos extremos. Dado un grafo , el problema del subgrafo prohibido pide el número máximo de aristas en un grafo de -vértice que no contenga un subgrafo isomorfo a . ${\displaystyle G}$ ${\displaystyle \operatorname {ex} (n,G)}$ ${\displaystyle n}$ ${\displaystyle G}$

Cuando es un grafo completo, el teorema de Turán proporciona un valor exacto para y caracteriza a todos los grafos que alcanzan este máximo; dichos grafos se conocen como grafos de Turán . Para grafos no bipartitos , el teorema de Erdős-Stone proporciona un valor asintótico de en términos del número cromático de . El problema de determinar las asintóticas de cuando es un grafo bipartito está abierto; cuando es un grafo bipartito completo, esto se conoce como el problema de Zarankiewicz . ${\displaystyle G=K_{r}}$ ${\displaystyle \operatorname {ex} (n,K_{r})}$ ${\displaystyle G}$ ${\displaystyle \operatorname {ex} (n,G)}$ ${\displaystyle G}$ ${\displaystyle \operatorname {ex} (n,G)}$ ${\displaystyle G}$ ${\displaystyle G}$

Densidad de homomorfismo

La densidad de homomorfismo de un grafo en un grafo describe la probabilidad de que un mapa elegido al azar del conjunto de vértices de al conjunto de vértices de sea también un homomorfismo de grafo . Está estrechamente relacionada con la densidad de subgrafos , que describe la frecuencia con la que un grafo se encuentra como subgrafo de . ${\displaystyle t(H,G)}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$

El problema del subgrafo prohibido puede reformularse como la maximización de la densidad de aristas de un grafo con densidad cero, y esto naturalmente conduce a la generalización en forma de desigualdades de homomorfismo de grafos , que son desigualdades relacionadas para varios grafos . Al extender la densidad de homomorfismo a los grafones , que son objetos que surgen como un límite de grafos densos , la densidad de homomorfismo de grafos puede escribirse en forma de integrales, y desigualdades como la desigualdad de Cauchy-Schwarz y la desigualdad de Hölder pueden usarse para derivar desigualdades de homomorfismo. ${\displaystyle G}$ ${\displaystyle t(H,G)}$ ${\displaystyle H}$

Un importante problema abierto relacionado con las densidades de homomorfismo es la conjetura de Sidorenko , que establece un límite inferior estricto para la densidad de homomorfismo de un gráfico bipartito en un gráfico en términos de la densidad de aristas de . ${\displaystyle G}$ ${\displaystyle G}$

Regularidad gráfica

Los bordes entre las partes de una partición regular se comportan de manera "aleatoria".

El lema de regularidad de Szemerédi establece que todos los grafos son "regulares" en el siguiente sentido: el conjunto de vértices de cualquier grafo dado se puede dividir en un número acotado de partes de modo que el grafo bipartito entre la mayoría de los pares de partes se comporte como grafos bipartitos aleatorios . ^[2] Esta partición proporciona una aproximación estructural al grafo original, que revela información sobre las propiedades del grafo original.

El lema de regularidad es un resultado central en la teoría de grafos extremales, y también tiene numerosas aplicaciones en los campos adyacentes de la combinatoria aditiva y la teoría de la complejidad computacional . Además de la regularidad (de Szemerédi), también se han estudiado nociones estrechamente relacionadas con la regularidad de grafos, como la regularidad fuerte y la regularidad débil de Frieze-Kannan, así como extensiones de la regularidad a los hipergrafos .

Las aplicaciones de la regularidad de grafos a menudo utilizan formas de lemas de conteo y lemas de eliminación. En las formas más simples, el lema de conteo de grafos utiliza la regularidad entre pares de partes en una partición regular para aproximar el número de subgrafos, y el lema de eliminación de grafos establece que, dado un grafo con pocas copias de un subgrafo dado, podemos eliminar una pequeña cantidad de aristas para eliminar todas las copias del subgrafo.

Véase también

Campos relacionados

• Teoría de Ramsey
• Teoría de Ramsey-Turán
• Teoría de grafos espectrales
• Combinatoria aditiva
• Teoría de la complejidad computacional
• Combinatoria probabilística

Técnicas y métodos

• Método probabilístico
• Elección aleatoria dependiente
• Método de contenedor
• Método de regularidad de hipergrafos

Teoremas y conjeturas (además de los mencionados anteriormente)

• Teorema de Ore
• Problema de Ruzsa-Szemerédi

Referencias

1. Diestel, Reinhard (2010), Teoría de grafos (4ª ed.), Berlín, Nueva York: Springer-Verlag, págs. 169-198, ISBN 978-3-642-14278-9, archivado desde el original el 28 de mayo de 2017 , consultado el 18 de noviembre de 2013
2. Alon, Noga ; Krivelevich, Michael (2008). "Combinatoria extrema y probabilística". En Gowers, Timothy ; Barrow-Green, June ; Leader, Imre (eds.). The Princeton Companion to Mathematics . Princeton, Nueva Jersey : Princeton University Press . págs. 562–575. doi :10.1515/9781400830398. ISBN 978-0-691-11880-2. JSTOR  j.ctt7sd01. LCCN  2008020450. MR  2467561. OCLC  227205932. OL  19327100M. Zbl  1242.00016.
3. Bollobás, Béla (2004), Teoría de grafos extremos , Nueva York: Dover Publications , ISBN 978-0-486-43596-1
4. Bollobás, Béla (1998), Teoría de grafos moderna , Berlín, Nueva York: Springer-Verlag , págs. 103-144, ISBN 978-0-387-98491-9