Problema del subgrafo prohibido
En teoría de grafos extremales, el problema del subgrafo prohibido se enuncia de la manera siguiente: dado un grafo , encontrar el número máximo de aristas en un grafo de vértices que no tiene un subgrafo isomorfo a . En este contexto, se denomina subgrafo prohibido.[1]
Un problema equivalente es: ¿Cuántas aristas en un grafo de vértices garantizan que tiene un subgrafo isomorfo a ?[2]
Definiciones
El número extremo es el número máximo de aristas en un grafo de vértices que no contiene ningún subgrafo isomorfo a . es el grafo completo en los vértices. es el grafo de Turán: un grafo -partite completo en vértices, con vértices distribuidos entre las partes de la manera más equitativa posible. La coloración de de es el número mínimo de colores necesarios para colorear los vértices de de modo que no haya dos vértices adyacentes del mismo color.
Límites superiores
Teorema de Turán
El teorema de Turán establece que para los enteros positivos que satisfacen que ,[3] entonces
Esto resuelve el problema del subgrafo prohibido para . Los casos de igualdad para el teorema de Turán provienen del grafo de Turán .
Este resultado se puede generalizar a grafos arbitrarios considerando la coloración de . Téngase en cuenta que se puede colorear con colores y, por lo tanto, no tiene subgrafos con un número cromático mayor que . En particular, no tiene subgrafos isomorfos a . Esto sugiere que los casos de igualdad generales para el problema del subgrafo prohibido pueden estar relacionados con los casos de igualdad para . Esta intuición resulta ser correcta con un margen de error vinculado a .
Teorema de Erdős-Stone
El teorema de Erdős-Stone establece que para todos los números enteros positivos y todos los grafos ,[4]
Cuando no es bipartito, esto proporciona una aproximación de primer orden de .
Grafos bipartitos
Para grafos bipartitos , el teorema de Erdős-Stone solo implica que . El problema del subgrafo prohibido para grafos bipartitos se conoce como problema de Zarankiewicz y, en general, no está resuelto.
El progreso en el problema de Zarankiewicz incluye el siguiente teorema:
- Teorema de Kővári–Sós–Turán: Para todo par de enteros positivos con , existe una constante (independiente de ) tal que para todo entero positivo .[5]
Otro resultado para grafos bipartitos es el caso de ciclos pares, . Incluso los ciclos se manejan considerando un vértice raíz y caminos que se ramifican desde este vértice. Si dos caminos de la misma longitud tienen el mismo punto final y no se superponen, entonces crean un ciclo de longitud . Esto da el siguiente teorema:
- Teorema (Bondy y Simonovits, 1974): Existe una constante tal que para todo entero positivo y todo entero positivo .[6]
Un lema poderoso en teoría de grafos extremales es de elección aleatoria dependiente. Este lema permite manejar grafos bipartitos con grado acotado en una parte:
- Teorema (Alon, Krivelevich y Sudakov, 2003): Sea un grafo bipartito con partes de vértice y tal que cada vértice en tiene grado como máximo . Entonces existe una constante (que depende solo de ) tal que para cada entero positivo .[7]
En general, se tiene la siguiente conjetura:
- Conjetura de los Exponentes Racionales (Erdős y Simonovits): Para cualquier familia finita de grafos, si hay un bipartito, entonces existe un racional tal que .[8]
Una recopilación realizada por Füredi y Simonovits describió el progreso en el problema del subgrafo prohibido con más detalle.[8]
Límites inferiores
Hay varias técnicas utilizadas para obtener los límites inferiores.
Método probabilístico
Si bien este método en su mayoría proporciona límites débiles, la teoría de grafos aleatorios es un tema en rápido desarrollo. Se basa en la idea de que si se toma un grafo al azar con una densidad suficientemente pequeña, el grafo contendría solo una pequeña cantidad de subgrafos de en su interior. Estas copias se pueden suprimir eliminando una arista de cada copia de en el grafo, lo que genera un grafo libre de .
El método probabilístico se puede usar para probar donde es una constante solo dependiendo del grafo .[9] Para la construcción se puede tomar el grafo aleatorio de Erdős-Rényi, que es el grafo con vértices y la arista con dos vértices dibujados con probabilidad , independientemente. Después de calcular el número esperado de copias de en por expectativa lineal, se elimina una arista de cada copia de y al final nos queda un grafo libre de . Se puede encontrar que el número esperado de aristas restantes es para un constante que depende de . Por lo tanto, existe al menos un grafo de vértices con al menos tantas aristas como el número esperado.
Este método también se puede usar para encontrar las construcciones de un grafo para los límites en la circunferencia del grafo. La circunferencia, denotada por , es la longitud del ciclo más corto del grafo. Téngase en cuenta que para , el grafo debe prohibir todos los ciclos con longitud menor que igual a . Por la linealidad de la expectativa, el número esperado de tales ciclos prohibidos es igual a la suma del número esperado de ciclos (para ). Nuevamente se eliminan las aristas de cada copia de un grafo prohibido y se termina con un grafo libre de ciclos más pequeños y , resultando aristas en el grafo de la izquierda.
Construcciones algebraicas
Para casos específicos, se han realizado mejoras encontrando construcciones algebraicas. Una característica común de tales construcciones es que implican el uso de la geometría para construir un grafo, con vértices que representan objetos geométricos y bordes de acuerdo con las relaciones algebraicas entre los vértices. Se termina sin subgrafos determinados de , simplemente por razones puramente geométricas, mientras que el grafo tiene una gran cantidad de aristas para ser un límite fuerte debido a la forma en que se definieron las incidencias. La siguiente prueba de Erdős, Rényi y Sős[10] que establece el límite inferior de como demuestra el poder de este método.
Primero, supóngase que para algún primo . Considérese el grafo de polaridad cuyos vértices son elementos de y aristas entre los vértices y si y solo si en . Este grafo no contiene a porque un sistema de dos ecuaciones lineales en no puede tener más de una solución. Un vértice (supóngase que ) está conectado a para cualquier , para un total de al menos aristas (restando 1 en el caso de ). Entonces, también hay al menos aristas, tal como se desee. Para un general, se puede tomar con (lo cual es posible porque existe un primo en el intervalo para [11] suficientemente grande) y construir un grafo de polaridad usando tal , agregando luego los vértices aislados de , que no afectan al valor asintótico.
El siguiente teorema es un resultado similar para .
Teorema (Brown, 1966):
- [12]
- Esquema de la demostración:[13]
- Como en el teorema anterior, se puede tomar como primo y dejar que los vértices del grafo sean elementos de . Esta vez, los vértices y están conectados si y solo si en , para algunos elegidos específicamente. Entonces, estará libre de , ya que como máximo dos puntos se encuentran en la intersección de tres esferas. Luego, dado que el valor de es casi uniforme en , cada punto debe tener alrededor de aristas, por lo que el número total de aristas es .
Sin embargo, sigue siendo una cuestión abierta ajustar el límite inferior de para .
Teorema (Alon et al., 1999):
- Para , [14]
Construcciones algebraicas aleatorias
Esta técnica combina las dos ideas anteriores. Utiliza relaciones de tipo polinómico aleatorio a la hora de definir las incidencias entre vértices, que se encuentran en algún conjunto algebraico. Se usa esta técnica para probar el teorema siguiente.
Teorema:
- Por cada , existe algún tal que .
- Esquema de la demostración:
- Se toma la mayor potencia prima con . Debido a las brechas principales, se tiene que . Sea un polinomio aleatorio en con grado como máximo en y y que satisface . Sea el grafo el conjunto de vértices tal que dos vértices son adyacentes si .
- Se define un conjunto y un conjunto como los elementos de que no están en y satisfacen para todos los elementos . Por el límite de Lang-Weil, se obtiene que para suficientemente grande, entonces o para algún constante. Ahora, calculamos el número esperado de tal que tiene un tamaño mayor que , y se elimina un vértice de cada . El grafo resultante resulta ser libre de y existe al menos un grafo con la expectativa del número de aristas de este grafo resultante.
Sobresaturación
La sobresaturación se refiere a una variante del problema del subgrafo prohibido, donde se considera que algún grafo uniforme contiene muchas copias de algún subgrafo prohibido . Intuitivamente, se podría esperar que esto ocurra una vez que contenga significativamente más aristas que . Se introduce la densidad de Turán para formalizar esta noción.
Densidad de Turán
La densidad de Turán de un grafo uniforme se define como:
Es cierto que es de hecho positivo y monótono decreciente, por lo que el límite debe existir.[15]
Como ejemplo, el teorema de Turán da y el teorema de Erdős-Stone da . En particular, para bipartito, . Determinar la densidad de Turán es equivalente a determinar hasta un error vinculado a .[16]
Teorema de sobresaturación
Considérese un hipergrafo uniforme con vértices. El teorema de sobresaturación establece que para cada , existe un tal que si es un grafo con vértices y al menos aristas para suficientemente grandes, entonces hay al menos copias de .[17]
De manera equivalente, se puede reformular este teorema como sigue: si un grafo con vértices tiene copias de , entonces hay como máximo aristas en .
Aplicaciones
Se pueden resolver varios problemas de subgrafos prohibidos considerando problemas del tipo de sobresaturación. A continuación se incluye un bosquejo de la demostración del teorema de Kővári-Sós-Turán:
Teorema de Kővári-Sós-Turán:
- Para todo par de enteros positivos con , existe una constante (independiente de ) tal que para todo entero positivo .[5]
- Esquema de la demostración:
- Sea un -grafo con vértices, y considérese el número de copias de en . Dado un vértice de grado , se obtienen exactamente copias de enraizadas en este vértice, para un total de copias. Aquí, cuando . Por una condición de convexidad, hay un total de al menos copias de . Además, claramente hay subconjuntos de vértices, por lo que si hay más de copias de , entonces por el principio del palomar debe existir un subconjunto de vértices que forman el conjunto de hojas de al menos de estas copias, formando un . Por lo tanto, existe una ocurrencia de mientras se tengan elementos. En otras palabras, se tiene una ocurrencia si , lo que se simplifica a , que es el enunciado del teorema.[18]
- En esta demostración se está usando el método de sobresaturación al considerar el número de ocurrencias de un subgrafo más pequeño. Por lo general, las aplicaciones del método de sobresaturación no utilizan el teorema de sobresaturación. En cambio, la estructura a menudo implica encontrar un subgrafo de algún subgrafo prohibido y mostrar que si aparece demasiadas veces en , también debe aparecer en .
Otros teoremas relacionados con el problema del subgrafo prohibido que se pueden resolver con sobresaturación incluyen:
- .[19]
- Para cualquier y , .[19]
- Si denota el grafo determinado por los vértices y aristas de un cubo, y denota el grafo obtenido al unir dos vértices opuestos del cubo, entonces .[18]
Generalizaciones
El problema puede generalizarse para un conjunto de subgrafos prohibidos : encontrar el número máximo de aristas en un grafo de vértices que no tiene un subgrafo isomorfo a ningún grafo de .[20]
También hay versiones para hipergrafos de problemas de subgrafos prohibidos que son mucho más difíciles. Por ejemplo, el problema de Turán puede generalizarse para hallar el mayor número de aristas en un hipergrafo 3-uniforme de vértices que no contiene tetraedros. El análogo de la construcción de Turán sería dividir los vértices en subconjuntos casi iguales, y conectar los vértices mediante una construcción de 3-aristas si están todos en diferentes, o si dos de ellos están en y el tercero está en (donde ). Esta disposición no contiene tetraedros y la densidad de aristas es . Sin embargo, el límite superior más conocido es 0,562, utilizando la técnica de álgebra de banderas.[21]
Véase también
- Teorema de Turán
- Problema de isomorfismo de subgrafos
- Caracterización de grafos prohibidos
- Erdős-Stone theorem
- Teoría de grafos extremales
Referencias
- ↑ Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Probabilistic Combinatorics, Béla Bollobás, 1986, ISBN 0-521-33703-8, p. 53, 54
- ↑ "Modern Graph Theory", by Béla Bollobás, 1998, ISBN 0-387-98488-7, p. 103
- ↑ Turán, Pál (1941). «On an extremal problem in graph theory». Matematikai és Fizikai Lapok (en húngaro) 48: 436-452.
- ↑ Erdős, P.; Stone, A. H. (1946). «On the structure of linear graphs». Bulletin of the American Mathematical Society 52 (12): 1087-1091. doi:10.1090/S0002-9904-1946-08715-7.
- ↑ a b Kővári, T.; T. Sós, V.; Turán, P. (1954), «On a problem of K. Zarankiewicz», Colloq. Math. 3: 50-57, MR 0065617, doi:10.4064/cm-3-1-50-57 .
- ↑ Bondy, J. A.; Simonovits, M. (April 1974). «Cycles of even length in graphs.». Journal of Combinatorial Theory, Series B 16 (2): 97-105. MR 340095. doi:10.1016/0095-8956(74)90052-5.
- ↑ Alon, Noga; Krivelevich, Michael; Sudakov, Benny. «Turán numbers of bipartite graphs and related Ramsey-type questions». Combinatorics, Probability and Computing. MR 2037065.
- ↑ a b Füredi, Zoltán; Simonovits, Miklós (2013-06-21). «The history of degenerate (bipartite) extremal graph problems». arXiv:1306.5167 [math.CO].
- ↑ Zhao, Yufei. «Graph Theory and Additive Combinatorics». pp. 32-37. Consultado el 2 de diciembre de 2019.
- ↑ Erdős, P.; Rényi, A.; Sós, V. T. (1966). «On a problem of graph theory». Studia Sci. Math. Hungar. 1: 215-235. MR 223262.
- ↑ Baker, R. C.; Harman, G.; Pintz, J. (2001), «The difference between consecutive primes. II.», Proc. London Math. Soc., Series 3 83 (3): 532-562, MR 1851081, doi:10.1112/plms/83.3.532 .
- ↑ Brown, W. G. (1966). «On graphs that do not contain a Thomsen graph». Canad. Math. Bull. 9 (3): 281-285. MR 200182. doi:10.4153/CMB-1966-036-2.
- ↑ Zhao, Yufei. «Graph Theory and Additive Combinatorics». pp. 32-37. Consultado el 2 de diciembre de 2019.
- ↑ Alon, Noga; Rónyai, Lajos; Szabó, Tibor (1999). «Norm-graphs: variations and applications». J. Combin. Theory Ser. B 76 (2): 280-290. MR 1699238. doi:10.1006/jctb.1999.1906.
- ↑ Erdős, Paul; Simonovits, Miklós. «Supersaturated Graphs and Hypergraphs». p. 3. Consultado el 27 de noviembre de 2021.
- ↑ Zhao, Yufei. «Graph Theory and Additive Combinatorics». pp. 16-17. Consultado el 2 de diciembre de 2019.
- ↑ Simonovits, Miklós. «Extremal Graph Problems, Degenerate Extremal Problems, and Supersaturated Graphs». p. 17. Consultado el 25 de noviembre de 2021.
- ↑ a b Simonovits, Miklós. «Extremal Graph Problems, Degenerate Extremal Problems, and Supersaturated Graphs». Consultado el 27 de noviembre de 2021.
- ↑ a b Erdős, Paul; Simonovits, Miklós. «Compactness Results in Extremal Graph Theory». Consultado el 27 de noviembre de 2021.
- ↑ Handbook of Discrete and Combinatorial Mathematics By Kenneth H. Rosen, John G. Michaels p. 590
- ↑ Keevash, Peter. «Hypergraph Turán Problems». Consultado el 2 de diciembre de 2019.
Datos: Q5467390