Problema del subgrafo prohibido

En la teoría de grafos extremales , el problema del subgrafo prohibido es el siguiente: dado un grafo , hallar el número máximo de aristas que puede tener un grafo con vértice tal que no tenga un subgrafo isomorfo a . En este contexto, se denomina subgrafo prohibido . ^[1] ${\displaystyle G}$ ${\displaystyle \operatorname {ex} (n,G)}$ ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle G}$

Un problema equivalente es ¿cuántas aristas en un gráfico de vértice garantizan que tiene un subgráfico isomorfo a ? ^[2] ${\displaystyle n}$ ${\displaystyle G}$

Definiciones

El número extremal es el número máximo de aristas en un grafo -vértice que no contiene ningún subgrafo isomorfo a . es el grafo completo en vértices. es el grafo de Turán : un grafo -partito completo en vértices, con vértices distribuidos entre partes lo más equitativamente posible. El número cromático de es el número mínimo de colores necesarios para colorear los vértices de tal manera que no haya dos vértices adyacentes con el mismo color. ${\displaystyle \operatorname {ex} (n,G)}$ ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle K_{r}}$ ${\displaystyle r}$ ${\displaystyle T(n,r)}$ ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle \chi (G)}$ ${\displaystyle G}$ ${\displaystyle G}$

Límites superiores

Teorema de Turán

El teorema de Turán establece que para números enteros positivos que satisfacen , ^[3] ${\displaystyle n,r}$ ${\displaystyle n\geq r\geq 3}$ ${\textstyle \operatorname {ex} (n,K_{r})=\left(1-{\frac {1}{r-1}}+o(1)\right){\frac {n^{2}}{2}}.}$

Esto resuelve el problema del subgrafo prohibido para . Los casos de igualdad para el teorema de Turán provienen del grafo de Turán . ${\displaystyle G=K_{r}}$ ${\displaystyle T(n,r-1)}$

Este resultado se puede generalizar a grafos arbitrarios considerando el número cromático de . Nótese que se puede colorear con colores y por lo tanto no tiene subgrafos con 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, salvo error. ${\displaystyle G}$ ${\displaystyle \chi (G)}$ ${\displaystyle G}$ ${\displaystyle T(n,r)}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle T(n,\chi (G)-1)}$ ${\displaystyle G}$ ${\displaystyle G=K_{r}}$ ${\displaystyle o(n^{2})}$

Teorema de Erdös-Stone

El teorema de Erdős-Stone establece que para todos los números enteros positivos y todos los gráficos , ^[4] ${\displaystyle n}$ ${\displaystyle G}$ ${\textstyle \operatorname {ex} (n,G)=\left(1-{\frac {1}{\chi (G)-1}}+o(1)\right){\binom {n}{2}}.}$

Cuando no es bipartito, esto nos da una aproximación de primer orden de . ${\displaystyle G}$ ${\displaystyle \operatorname {ex} (n,G)}$

Grafos bipartitos

Para los grafos bipartitos , el teorema de Erdős-Stone solo nos dice que . El problema del subgrafo prohibido para grafos bipartitos se conoce como el problema de Zarankiewicz y, en general, no está resuelto. ${\displaystyle G}$ ${\displaystyle \operatorname {ex} (n,G)=o(n^{2})}$

El avance del problema de Zarankiewicz incluye el siguiente teorema:

Teorema de Kővári–Sós–Turán. Para cada par de números enteros positivos con , existe una constante (independiente de ) tal que para cada número entero positivo . ^[5] ${\displaystyle s,t}$ ${\displaystyle t\geq s\geq 1}$ ${\displaystyle C}$ ${\displaystyle n}$ ${\textstyle \operatorname {ex} (n,K_{s,t})\leq Cn^{2-{\frac {1}{s}}}}$ ${\displaystyle n}$

Otro resultado para los grafos bipartitos es el caso de los ciclos pares, . Los ciclos pares 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. ${\displaystyle G=C_{2k},k\geq 2}$ ${\displaystyle k}$ ${\displaystyle 2k}$

Teorema ( Bondy y Simonovits , 1974). Existe alguna constante tal que para cada entero positivo y entero positivo . ^[6] ${\displaystyle C}$ ${\textstyle \operatorname {ex} (n,C_{2k})\leq Cn^{1+{\frac {1}{k}}}}$ ${\displaystyle n}$ ${\displaystyle k\geq 2}$

Un lema poderoso en la teoría de grafos extremales es la elección aleatoria dependiente. Este lema nos permite manejar grafos bipartitos con grado acotado en una parte:

Teorema ( Alon , Krivelevich y Sudakov , 2003). Sea un grafo bipartito con partes en vértice y tal que cada vértice en tiene grado como máximo . Entonces existe una constante (dependiente solo de ) tal que para cada entero positivo . ^[7] ${\displaystyle G}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle r}$ ${\displaystyle C}$ ${\displaystyle G}$ ${\textstyle \operatorname {ex} (n,G)\leq Cn^{2-{\frac {1}{r}}}}$ ${\displaystyle n}$

En general, tenemos la siguiente conjetura:

Conjetura de los exponentes racionales (Erdős y Simonovits). Para cualquier familia finita de grafos, si existe un bipartito , entonces existe un racional tal que . ^[8] ${\displaystyle {\mathcal {L}}}$ ${\displaystyle L\in {\mathcal {L}}}$ ${\displaystyle \alpha \in [0,1)}$ ${\displaystyle \operatorname {ex} (n,{\mathcal {L}})=\Theta (n^{1+\alpha })}$

Una encuesta realizada por Füredi y Simonovits describe el progreso en el problema del subgrafo prohibido con más detalle. ^[8]

Límites inferiores

Existen varias técnicas utilizadas para obtener los límites inferiores.

Método probabilístico

Si bien este método proporciona en su mayoría 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 tomamos un grafo al azar con una densidad suficientemente pequeña, el grafo contendría solo una pequeña cantidad de subgrafos de dentro de él. Estas copias se pueden eliminar eliminando una arista de cada copia de en el grafo, lo que nos da un grafo libre. ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$

El método probabilístico se puede utilizar para demostrar que es una constante que depende únicamente del grafo . ^[9] Para la construcción podemos tomar el grafo aleatorio de Erdős-Rényi , es decir, el grafo con vértices y la arista son dos vértices cualesquiera dibujados con probabilidad , independientemente. Después de calcular el número esperado de copias de en por linealidad de expectativa , eliminamos una arista de cada una de esas copias de y nos quedamos con un grafo sin - al final. Se puede encontrar que el número esperado de aristas restantes es para una constante que depende de . Por lo tanto, existe al menos un grafo de -vértice con al menos tantas aristas como el número esperado. ${\displaystyle \operatorname {ex} (n,G)\geq cn^{2-{\frac {v(G)-2}{e(G)-1}}}}$ ${\displaystyle c}$ ${\displaystyle G}$ ${\displaystyle G(n,p)}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle G}$ ${\displaystyle G(n,p)}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle \operatorname {ex} (n,G)\geq cn^{2-{\frac {v(G)-2}{e(G)-1}}}}$ ${\displaystyle c}$ ${\displaystyle G}$ ${\displaystyle n}$

Este método también se puede utilizar para encontrar las construcciones de un gráfico para límites en la circunferencia del gráfico. La circunferencia, denotada por , es la longitud del ciclo más corto del gráfico. Nótese que para , el gráfico debe prohibir todos los ciclos con longitud menor que igual a . Por linealidad de expectativa, el número esperado de tales ciclos prohibidos es igual a la suma del número esperado de ciclos (para .). Nuevamente eliminamos las aristas de cada copia de un gráfico prohibido y terminamos con un gráfico libre de ciclos más pequeños y , lo que nos da aristas en el gráfico que quedan. ${\displaystyle g(G)}$ ${\displaystyle g(G)>2k}$ ${\displaystyle 2k}$ ${\displaystyle C_{i}}$ ${\displaystyle i=3,...,n-1,n}$ ${\displaystyle g(G)>2k}$ ${\displaystyle c_{0}n^{1+{\frac {1}{2k-1}}}}$

Construcciones algebraicas

Para casos específicos, se han realizado mejoras mediante la búsqueda de construcciones algebraicas. Una característica común de tales construcciones es que implica el uso de geometría para construir un grafo, con vértices que representan objetos geométricos y aristas de acuerdo con las relaciones algebraicas entre los vértices. Terminamos sin ningún subgrafo de , debido puramente a 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. ${\displaystyle G}$ ${\displaystyle \operatorname {ex} (n,K_{2,2})}$ ${\displaystyle \left({\frac {1}{2}}-o(1)\right)n^{3/2}.}$

Primero, supongamos que para algún primo . Consideremos el gráfico de polaridad con elementos de vértices de y aristas entre vértices y si y solo si en . Este gráfico es libre de porque un sistema de dos ecuaciones lineales en no puede tener más de una solución. Un vértice (supongamos que ) está conectado a para cualquier , para un total de al menos aristas (restando 1 en el caso de ). Por lo tanto, hay al menos aristas, como se desea. Para , podemos tomar con (lo cual es posible porque existe un primo en el intervalo para suficientemente grande ^[11] ) y construir un gráfico de polaridad usando tales , luego agregando vértices aislados, que no afectan el valor asintótico. ${\displaystyle n=p^{2}-1}$ ${\displaystyle p}$ ${\displaystyle G}$ ${\displaystyle \mathbb {F} _{p}^{2}-\{0,0\}}$ ${\displaystyle (x,y)}$ ${\displaystyle (a,b)}$ ${\displaystyle ax+by=1}$ ${\displaystyle \mathbb {F} _{p}}$ ${\displaystyle K_{2,2}}$ ${\displaystyle \mathbb {F} _{p}}$ ${\displaystyle (a,b)}$ ${\displaystyle b\neq 0}$ ${\displaystyle \left(x,{\frac {1-ax}{b}}\right)}$ ${\displaystyle x\in \mathbb {F} _{p}}$ ${\displaystyle p-1}$ ${\displaystyle (a,b)=\left(x,{\frac {1-ax}{b}}\right)}$ ${\displaystyle {\frac {1}{2}}(p^{2}-1)(p-1)=\left({\frac {1}{2}}-o(1)\right)p^{3}=\left({\frac {1}{2}}-o(1)\right)n^{3/2}}$ ${\displaystyle n}$ ${\displaystyle p=(1-o(1)){\sqrt {n}}}$ ${\displaystyle p\leq {\sqrt {n+1}}}$ ${\displaystyle p}$ ${\displaystyle [k-k^{0.525},k]}$ ${\displaystyle k}$ ${\displaystyle p}$ ${\displaystyle n-p^{2}+1}$

El siguiente teorema es un resultado similar para . ${\displaystyle K_{3,3}}$

Teorema (Brown, 1966). ^[12] ${\displaystyle \operatorname {ex} (n,K_{3,3})\geq \left({\frac {1}{2}}-o(1)\right)n^{5/3}.}$

Esquema de la prueba. ^[13] Al igual que en el teorema anterior, podemos tomar como primo y dejar que los vértices de nuestro grafo sean elementos de . Esta vez, los vértices y están conexos si y solo si en , para algún . Entonces esto es -free ya que como máximo dos puntos se encuentran en la intersección de tres esferas. Entonces, dado que el valor de es casi uniforme en , cada punto debería tener alrededor de aristas, por lo que el número total de aristas es . ${\displaystyle n=p^{3}}$ ${\displaystyle p}$ ${\displaystyle \mathbb {F} _{p}^{3}}$ ${\displaystyle (a,b,c)}$ ${\displaystyle (x,y,z)}$ ${\displaystyle (x-a)^{2}+(y-b)^{2}+(z-c)^{2}=u}$ ${\displaystyle \mathbb {F} _{p}}$ ${\displaystyle u}$ ${\displaystyle K_{3,3}}$ ${\displaystyle (x-a)^{2}+(y-b)^{2}+(z-c)^{2}}$ ${\displaystyle \mathbb {F} _{p}}$ ${\displaystyle p^{2}}$ ${\displaystyle \left({\frac {1}{2}}-o(1)\right)p^{2}\cdot p^{3}=\left({\frac {1}{2}}-o(1)\right)n^{5/3}}$

Sin embargo, sigue siendo una cuestión abierta ajustar el límite inferior para . ${\displaystyle \operatorname {ex} (n,K_{t,t})}$ ${\displaystyle t\geq 4}$

Teorema (Alon et al., 1999) Para , ^[14] ${\displaystyle t\geq (s-1)!+1}$ ${\displaystyle \operatorname {ex} (n,K_{s,t})=\Theta (n^{2-{\frac {1}{s}}}).}$

Construcciones algebraicas aleatorias

Esta técnica combina las dos ideas anteriores. Utiliza relaciones de tipo polinomial aleatorio para definir las incidencias entre vértices que se encuentran en algún conjunto algebraico. Utilizando esta técnica se demuestra el siguiente teorema.

Teorema : Para cada , existe algún tal que . ${\displaystyle s\geq 2}$ ${\displaystyle t}$ ${\displaystyle \operatorname {ex} (n,K_{s,t})\geq \left({\frac {1}{2}}-o(1)\right)n^{2-{\frac {1}{s}}}}$

Esquema de la prueba: tomamos la potencia prima más grande con . Debido a los huecos primos, tenemos . Sea un polinomio aleatorio en con grado como máximo en y y que satisface . Sea el gráfico con el conjunto de vértices tal que dos vértices son adyacentes si . ${\displaystyle q}$ ${\displaystyle q^{s}\leq n}$ ${\displaystyle q=(1-o(1))n^{\frac {1}{s}}}$ ${\displaystyle f\in \mathbb {F} _{q}[x_{1},x_{2},\cdots ,x_{s},y_{1},y_{2},\cdots ,y_{s}]_{\leq d}}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle d=s^{2}}$ ${\displaystyle X=(X_{1},X_{2},...,X_{s})}$ ${\displaystyle Y=(Y_{1},Y_{2},...,Y_{s})}$ ${\displaystyle f(X,Y)=f(Y,X)}$ ${\displaystyle G}$ ${\displaystyle \mathbb {F} _{q}^{s}}$ ${\displaystyle x,y}$ ${\displaystyle f(x,y)=0}$

Fijamos un conjunto , y definimos un conjunto como los elementos de no en que satisfacen para todos los elementos . Por el límite de Lang-Weil, obtenemos que para suficientemente grande, tenemos o para alguna constante . Ahora, calculamos el número esperado de tales que tiene un tamaño mayor que , y eliminamos un vértice de cada uno de ellos . El grafo resultante resulta ser libre, y existe al menos un grafo con la expectativa del número de aristas de este grafo resultante. ${\displaystyle U\subset \mathbb {F} _{q}^{s}}$ ${\displaystyle Z_{U}}$ ${\displaystyle \mathbb {F} _{q}^{s}}$ ${\displaystyle U}$ ${\displaystyle f(x,u)=0}$ ${\displaystyle u\in U}$ ${\displaystyle q}$ ${\displaystyle |Z_{U}|\leq C}$ ${\displaystyle |Z_{U}|>{\frac {q}{2}}}$ ${\displaystyle C}$ ${\displaystyle U}$ ${\displaystyle Z_{U}}$ ${\displaystyle C}$ ${\displaystyle U}$ ${\displaystyle K_{s,C+1}}$

Supersaturación

La supersaturación se refiere a una variante del problema del subgrafo prohibido, en el que consideramos cuándo un grafo -uniforme contiene muchas copias de un subgrafo prohibido . Intuitivamente, uno esperaría que esto contenga significativamente más de aristas. Introducimos la densidad de Turán para formalizar esta noción. ${\displaystyle h}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle \operatorname {ex} (n,H)}$

Densidad de Turán

La densidad de Turán de un gráfico -uniforme se define como ${\displaystyle h}$ ${\displaystyle G}$

${\displaystyle \pi (G)=\lim _{n\to \infty }{\frac {\operatorname {ex} (n,G)}{\binom {n}{h}}}.}$

Es cierto que en realidad es positiva y monótona decreciente, por lo que el límite debe existir. ^[15] ${\displaystyle {\frac {\operatorname {ex} (n,G)}{\binom {n}{h}}}}$

Como ejemplo, el teorema de Turán da que , y el teorema de Erdős-Stone da que . En particular, para bipartito , . Determinar la densidad de Turán es equivalente a determinar hasta un error. ^[16] ${\displaystyle \pi (K_{r+1})=1-{\frac {1}{r}}}$ ${\displaystyle \pi (G)=1-{\frac {1}{\chi (H)-1}}}$ ${\displaystyle G}$ ${\displaystyle \pi (G)=0}$ ${\displaystyle \pi (H)}$ ${\displaystyle \operatorname {ex} (n,G)}$ ${\displaystyle o(n^{2})}$

Teorema de sobresaturación

Consideremos un hipergrafo -uniforme con vértices. El teorema de supersaturación establece que para cada , existe un tal que si es un hipergrafo -uniforme sobre vértices y al menos aristas para suficientemente grande, entonces hay al menos copias de . ^[17] ${\displaystyle h}$ ${\displaystyle H}$ ${\displaystyle v(H)}$ ${\displaystyle \epsilon >0}$ ${\displaystyle \delta >0}$ ${\displaystyle G}$ ${\displaystyle h}$ ${\displaystyle n}$ ${\displaystyle (\pi (H)+\epsilon ){\binom {n}{h}}}$ ${\displaystyle n}$ ${\displaystyle \delta n^{v(H)}}$ ${\displaystyle H}$

De manera equivalente, podemos reformular este teorema de la siguiente manera: si un gráfico con vértices tiene copias de , entonces hay como máximo aristas en . ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle o(n^{v(H)})}$ ${\displaystyle H}$ ${\displaystyle \pi (H){\binom {n}{2}}+o(n^{2})}$ ${\displaystyle G}$

Aplicaciones

Podemos resolver varios problemas de subgrafos prohibidos considerando problemas de tipo sobresaturación. Reformulamos y presentamos una demostración del teorema de Kővári–Sós–Turán a continuación:

Teorema de Kővári–Sós–Turán. Para cada par de números enteros positivos con , existe alguna constante (independiente de ) tal que para cada número entero positivo . ^[18] ${\displaystyle s,t}$ ${\displaystyle t\geq s\geq 1}$ ${\displaystyle C}$ ${\displaystyle n}$ ${\textstyle \operatorname {ex} (n,K_{s,t})\leq Cn^{2-{\frac {1}{s}}}}$ ${\displaystyle n}$

Demostración. Sea un -grafo sobre vértices, y considere el número de copias de en . Dado un vértice de grado , obtenemos exactamente copias de con raíz en este vértice, para un total de copias. Aquí, cuando . Por convexidad, hay un total de al menos copias de . Además, hay claramente subconjuntos de vértices, por lo que si hay más de copias de , entonces por el Principio del Pigeonhole debe existir un subconjunto de vértices que formen el conjunto de hojas de al menos de estas copias, formando un . Por lo tanto, existe una ocurrencia de siempre que tengamos . En otras palabras, tenemos una ocurrencia si , que se simplifica a , que es el enunciado del teorema. ^[19] ${\displaystyle G}$ ${\displaystyle 2}$ ${\displaystyle n}$ ${\displaystyle K_{1,s}}$ ${\displaystyle G}$ ${\displaystyle d}$ ${\displaystyle {\binom {d}{s}}}$ ${\displaystyle K_{1,s}}$ ${\displaystyle \sum _{v\in V(G)}{\binom {\operatorname {deg} (v)}{s}}}$ ${\displaystyle {\binom {k}{s}}=0}$ ${\displaystyle 0\leq k<s}$ ${\displaystyle n{\binom {2e(G)/n}{s}}}$ ${\displaystyle K_{1,s}}$ ${\displaystyle {\binom {n}{s}}}$ ${\displaystyle s}$ ${\displaystyle (t-1){\binom {n}{s}}}$ ${\displaystyle K_{1,s}}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle K_{s,t}}$ ${\displaystyle K_{s,t}}$ ${\displaystyle n{\binom {2e(G)/n}{s}}>(t-1){\binom {n}{s}}}$ ${\displaystyle {\frac {e(G)^{s}}{n^{s-1}}}\geq O(n^{s})}$ ${\displaystyle e(G)\geq O(n^{2-{\frac {1}{s}}})}$

En esta prueba, utilizamos el método de supersaturación considerando el número de ocurrencias de un subgrafo más pequeño. Normalmente, las aplicaciones del método de supersaturación no utilizan el teorema de supersaturación. En cambio, la estructura a menudo implica encontrar un subgrafo de algún subgrafo prohibido y demostrar que si aparece demasiadas veces en , entonces debe aparecer también en . Otros teoremas relacionados con el problema del subgrafo prohibido que se pueden resolver con supersaturación incluyen: ${\displaystyle H'}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$

• ${\displaystyle \operatorname {ex} (n,C_{2t})\leq O(n^{1+1/t})}$. ^[20]
• Para cualquier y , . ^[20] ${\displaystyle t}$ ${\displaystyle k\geq 2}$ ${\displaystyle \operatorname {ex} (n,C_{2k},C_{2k-1})\leq O\left(\left({\frac {n}{2}}\right)^{1+1/t}\right)}$
• Si denota el gráfico determinado por los vértices y las aristas de un cubo, y denota el gráfico obtenido al unir dos vértices opuestos del cubo, entonces . ^[19] ${\displaystyle Q}$ ${\displaystyle Q^{*}}$ ${\displaystyle \operatorname {ex} (n,Q)\leq \operatorname {ex} (n,Q^{*})=O(n^{8/5})}$

Generalizaciones

El problema se puede generalizar para un conjunto de subgrafos prohibidos : encontrar el número máximo de aristas en un grafo de -vértice que no tiene un subgrafo isomorfo a ningún grafo de . ^[21] ${\displaystyle S}$ ${\displaystyle n}$ ${\displaystyle S}$

También existen versiones hipergráficas de problemas de subgrafos prohibidos que son mucho más difíciles. Por ejemplo, el problema de Turán puede generalizarse para pedir el mayor número de aristas en un hipergrafo 3-uniforme de vértices que no contenga 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 arista de 3 si todos están en diferentes s, o si dos de ellos están en y el tercero está en (donde ). Esto no tiene tetraedros y la densidad de aristas es . Sin embargo, el límite superior más conocido es 0,562, utilizando la técnica de las álgebras de banderas. ^[22] ${\displaystyle n}$ ${\displaystyle V_{1},V_{2},V_{3}}$ ${\displaystyle x,y,z}$ ${\displaystyle V_{i}}$ ${\displaystyle V_{i}}$ ${\displaystyle V_{i+1}}$ ${\displaystyle V_{4}=V_{1}}$ ${\displaystyle 5/9}$

Véase también

• Gráfica sin biclique
• Conjetura de Erdős-Hajnal
• Número de turán
• Problema de isomorfismo de subgrafos
• Caracterización de gráficos prohibida

Referencias

1. Combinatoria: sistemas de conjuntos, hipergrafos, familias de vectores y combinatoria probabilística , Béla Bollobás , 1986, ISBN  0-521-33703-8 , pág. 53, 54
2. "Teoría de grafos moderna", de Béla Bollobás, 1998, ISBN 0-387-98488-7 , p. 103 
3. Turán, Pál (1941). "Sobre un problema extremo en teoría de grafos". Matematikai és Fizikai Lapok (en húngaro). 48 : 436–452.
4. Erdős, P. ; Stone, AH (1946). "Sobre la estructura de los grafos lineales" (PDF) . Boletín de la American Mathematical Society . 52 (12): 1087–1091. doi : 10.1090/S0002-9904-1946-08715-7 .
5. Kővári, T.; T. Sós, V .; Turán, P. (1954), “Sobre un problema de K. Zarankiewicz” (PDF) , Colloq. Matemáticas. , 3 : 50–57, doi : 10,4064/cm-3-1-50-57 , SEÑOR  0065617
6. Bondy, JA ; Simonovits, M. (abril de 1974). "Ciclos de longitud par en grafos". Journal of Combinatorial Theory . Serie B. 16 (2): 97–105. doi : 10.1016/0095-8956(74)90052-5 . MR  0340095.
7. Alon, Noga ; Krivelevich, Michael ; Sudakov, Benny . "Números de Turán de grafos bipartitos y cuestiones relacionadas de tipo Ramsey". Combinatoria, probabilidad y computación . MR  2037065.
8. Füredi, Zoltán; Simonovits, Miklós (21 de junio de 2013). "La historia de los problemas de gráficos extremos degenerados (bipartitos)". arXiv : 1306.5167 [matemáticas.CO].
9. Zhao, Yufei. "Teoría de grafos y combinatoria aditiva" (PDF) . pp. 32–37 . Consultado el 2 de diciembre de 2019 .
10. Erdős, P.; Rényi, A.; Sós, VT (1966). "Sobre un problema de teoría de grafos". Estudios de ciencia. Matemáticas. Hungría. 1 : 215–235. SEÑOR  0223262.
11. Baker, RC; Harman, G.; Pintz, J. (2001), "La diferencia entre primos consecutivos. II.", Proc. London Math. Soc. , Serie 3, 83 (3): 532–562, doi :10.1112/plms/83.3.532, MR  1851081, S2CID  8964027
12. Brown, WG (1966). "Sobre grafos que no contienen un grafo de Thomsen". Canad. Math. Bull. 9 (3): 281–285. doi : 10.4153/CMB-1966-036-2 . MR  0200182.
13. Zhao, Yufei. "Teoría de grafos y combinatoria aditiva" (PDF) . pp. 32–37 . Consultado el 2 de diciembre de 2019 .
14. Alon, Noga; Rónyai, Lajos; Szabó, Tibor (1999). "Norm-graphs: variaciones y aplicaciones". Journal of Combinatorial Theory . Serie B. 76 (2): 280–290. doi : 10.1006/jctb.1999.1906 . MR  1699238.
15. Erdős, Paul; Simonovits, Miklós. "Gráficos e hipergráficos sobresaturados" (PDF) . pag. 3 . Consultado el 27 de noviembre de 2021 .
16. Zhao, Yufei. "Teoría de grafos y combinatoria aditiva" (PDF) . pp. 16–17 . Consultado el 2 de diciembre de 2019 .
17. Simonovits, Miklós. "Problemas de grafos extremos, problemas de grafos extremos degenerados y grafos supersaturados" (PDF) . p. 17 . Consultado el 25 de noviembre de 2021 .
18. Kővári, T.; T. Sós, V .; Turán, P. (1954), “Sobre un problema de K. Zarankiewicz” (PDF) , Colloq. Matemáticas. , 3 : 50–57, doi : 10,4064/cm-3-1-50-57 , SEÑOR  0065617
19. Simonovits, Miklós. "Problemas de grafos extremos, problemas de grafos extremos degenerados y grafos supersaturados" (PDF) . Consultado el 27 de noviembre de 2021 .
20. Erdős, Paul; Simonovits, Miklós. "Resultados de compacidad en la teoría de grafos extremos" (PDF) . Consultado el 27 de noviembre de 2021 .
21. Manual de matemáticas discretas y combinatorias Por Kenneth H. Rosen, John G. Michaels p. 590
22. Keevash, Peter. «Problemas del Hipergrafo Turán» (PDF) . Consultado el 2 de diciembre de 2019 .