Problema del subgrafo prohibido

En teoría de grafos extremales, el problema del subgrafo prohibido se enuncia de la manera siguiente: dado un grafo ${\displaystyle G}$, encontrar el número máximo de aristas ${\displaystyle \operatorname {ex} (n,G)}$ en un grafo de ${\displaystyle n}$ vértices que no tiene un subgrafo isomorfo a ${\displaystyle G}$. En este contexto, ${\displaystyle G}$ se denomina subgrafo prohibido.^[1]​

Un problema equivalente es: ¿Cuántas aristas en un grafo de ${\displaystyle n}$ vértices garantizan que tiene un subgrafo isomorfo a ${\displaystyle G}$?^[2]​

El número extremo ${\displaystyle \operatorname {ex} (n,G)}$ es el número máximo de aristas en un grafo de ${\displaystyle n}$ vértices que no contiene ningún subgrafo isomorfo a ${\displaystyle G}$. ${\displaystyle K_{r}}$ es el grafo completo en los ${\displaystyle r}$ vértices. ${\displaystyle T(n,r)}$ es el grafo de Turán: un grafo ${\displaystyle r}$-partite completo en ${\displaystyle n}$ vértices, con vértices distribuidos entre las partes de la manera más equitativa posible. La coloración de ${\displaystyle \chi (G)}$ de ${\displaystyle G}$ es el número mínimo de colores necesarios para colorear los vértices de ${\displaystyle G}$ de modo que no haya dos vértices adyacentes del mismo color.

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

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

Este resultado se puede generalizar a grafos ${\displaystyle G}$ arbitrarios considerando la coloración ${\displaystyle \chi (G)}$ de ${\displaystyle G}$. Téngase en cuenta que ${\displaystyle T(n,r)}$ se puede colorear con ${\displaystyle r}$ colores y, por lo tanto, no tiene subgrafos con un número cromático mayor que ${\displaystyle r}$. En particular, ${\displaystyle T(n,\chi (G)-1)}$ no tiene subgrafos isomorfos a ${\displaystyle G}$. Esto sugiere que los casos de igualdad generales para el problema del subgrafo prohibido pueden estar relacionados con los casos de igualdad para ${\displaystyle G=K_{r}}$. Esta intuición resulta ser correcta con un margen de error vinculado a ${\displaystyle o(n^{2})}$.

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

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

Para grafos bipartitos ${\displaystyle G}$, el teorema de Erdős-Stone solo implica que ${\displaystyle \operatorname {ex} (n,G)=o(n^{2})}$. 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 ${\displaystyle s,t}$ con ${\displaystyle t\geq s\geq 1}$, existe una constante ${\displaystyle C}$ (independiente de ${\displaystyle n}$) tal que ${\textstyle \operatorname {ex} (n,K_{s,t})\leq Cn^{2-{\frac {1}{s}}}}$ para todo entero positivo ${\displaystyle n}$.^[5]​

Otro resultado para grafos bipartitos es el caso de ciclos pares, ${\displaystyle G=C_{2k},k\geq 2}$. 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 ${\displaystyle k}$ tienen el mismo punto final y no se superponen, entonces crean un ciclo de longitud ${\displaystyle 2k}$. Esto da el siguiente teorema:

Teorema (Bondy y Simonovits, 1974): Existe una constante ${\displaystyle C}$ tal que ${\textstyle \operatorname {ex} (n,C_{2k})\leq Cn^{1+{\frac {1}{k}}}}$ para todo entero positivo ${\displaystyle n}$ y todo entero positivo ${\displaystyle k\geq 2}$.^[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 ${\displaystyle G}$ un grafo bipartito con partes de vértice ${\displaystyle A}$ y ${\displaystyle B}$ tal que cada vértice en ${\displaystyle A}$ tiene grado como máximo ${\displaystyle r}$. Entonces existe una constante ${\displaystyle C}$ (que depende solo de ${\displaystyle G}$) tal que ${\textstyle \operatorname {ex} (n,G)\leq Cn^{2-{\frac {1}{r}}}}$ para cada entero positivo ${\displaystyle n}$.^[7]​

En general, se tiene la siguiente conjetura:

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

Una recopilación realizada por Füredi y Simonovits describió el progreso en el problema del subgrafo prohibido con más detalle.^[8]​

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

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 ${\displaystyle G}$ en su interior. Estas copias se pueden suprimir eliminando una arista de cada copia de ${\displaystyle G}$ en el grafo, lo que genera un grafo libre de ${\displaystyle G}$.

El método probabilístico se puede usar para probar ${\displaystyle \operatorname {ex} (n,G)\geq cn^{2-{\frac {v(G)-2}{e(G)-1}}}}$ donde ${\displaystyle c}$ es una constante solo dependiendo del grafo ${\displaystyle G}$.^[9]​ Para la construcción se puede tomar el grafo aleatorio ${\displaystyle G(n,p)}$ de Erdős-Rényi, que es el grafo con ${\displaystyle n}$ vértices y la arista con dos vértices dibujados con probabilidad ${\displaystyle p}$, independientemente. Después de calcular el número esperado de copias de ${\displaystyle G}$ en ${\displaystyle G(n,p)}$ por expectativa lineal, se elimina una arista de cada copia de ${\displaystyle G}$ y al final nos queda un grafo libre de ${\displaystyle G}$. Se puede encontrar que el número esperado de aristas restantes es ${\displaystyle \operatorname {ex} (n,G)\geq cn^{2-{\frac {v(G)-2}{e(G)-1}}}}$ para un ${\displaystyle c}$ constante que depende de ${\displaystyle G}$. Por lo tanto, existe al menos un grafo de ${\displaystyle n}$ 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 ${\displaystyle g(G)}$, es la longitud del ciclo más corto del grafo. Téngase en cuenta que para ${\displaystyle g(G)>2k}$, el grafo debe prohibir todos los ciclos con longitud menor que igual a ${\displaystyle 2k}$. 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 ${\displaystyle C_{i}}$ (para ${\displaystyle i=3,...,n-1,n}$). 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 ${\displaystyle g(G)>2k}$, resultando ${\displaystyle c_{0}n^{1+{\frac {1}{2k-1}}}}$ aristas en el grafo de la izquierda.

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 ${\displaystyle G}$, 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 ${\displaystyle \operatorname {ex} (n,K_{2,2})}$ como ${\displaystyle \left({\frac {1}{2}}-o(1)\right)n^{3/2}.}$ demuestra el poder de este método.

Primero, supóngase que ${\displaystyle n=p^{2}-1}$ para algún primo ${\displaystyle p}$. Considérese el grafo de polaridad ${\displaystyle G}$ cuyos vértices son elementos de ${\displaystyle \mathbb {F} _{p}^{2}-\{0,0\}}$ y aristas entre los vértices ${\displaystyle (x,y)}$ y ${\displaystyle (a,b)}$ si y solo si ${\displaystyle ax+by=1}$ en ${\displaystyle \mathbb {F} _{p}}$. Este grafo no contiene a ${\displaystyle K_{2,2}}$ porque un sistema de dos ecuaciones lineales en ${\displaystyle \mathbb {F} _{p}}$ no puede tener más de una solución. Un vértice ${\displaystyle (a,b)}$ (supóngase que ${\displaystyle b\neq 0}$) está conectado a ${\displaystyle \left(x,{\frac {1-ax}{b}}\right)}$ para cualquier ${\displaystyle x\in \mathbb {F} _{p}}$, para un total de al menos ${\displaystyle p-1}$ aristas (restando 1 en el caso de ${\displaystyle (a,b)=\left(x,{\frac {1-ax}{b}}\right)}$). Entonces, también hay al menos ${\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}}$ aristas, tal como se desee. Para un ${\displaystyle n}$ general, se puede tomar ${\displaystyle p=(1-o(1)){\sqrt {n}}}$ con ${\displaystyle p\leq {\sqrt {n+1}}}$ (lo cual es posible porque existe un ${\displaystyle p}$ primo en el intervalo ${\displaystyle [k-k^{0.525},k]}$ para ${\displaystyle k}$^[11]​ suficientemente grande) y construir un grafo de polaridad usando tal ${\displaystyle p}$, agregando luego los vértices aislados de ${\displaystyle n-p^{2}+1}$, que no afectan al valor asintótico.

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

Teorema (Brown, 1966):

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

Esquema de la demostración:^[13]​

• Como en el teorema anterior, se puede tomar ${\displaystyle n=p^{3}}$ como primo ${\displaystyle p}$ y dejar que los vértices del grafo sean elementos de ${\displaystyle \mathbb {F} _{p}^{3}}$. Esta vez, los vértices ${\displaystyle (a,b,c)}$ y ${\displaystyle (x,y,z)}$ están conectados si y solo si ${\displaystyle (x-a)^{2}+(y-b)^{2}+(z-c)^{2}=u}$ en ${\displaystyle \mathbb {F} _{p}}$, para algunos ${\displaystyle u}$ elegidos específicamente. Entonces, estará libre de ${\displaystyle K_{3,3}}$, ya que como máximo dos puntos se encuentran en la intersección de tres esferas. Luego, dado que el valor de ${\displaystyle (x-a)^{2}+(y-b)^{2}+(z-c)^{2}}$ es casi uniforme en ${\displaystyle \mathbb {F} _{p}}$, cada punto debe tener alrededor de ${\displaystyle p^{2}}$ aristas, por lo que el número total de aristas es ${\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 de ${\displaystyle \operatorname {ex} (n,K_{t,t})}$ para ${\displaystyle t\geq 4}$.

Teorema (Alon et al., 1999):

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

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 ${\displaystyle s\geq 2}$, existe algún ${\displaystyle t}$ tal que ${\displaystyle \operatorname {ex} (n,K_{s,t})\geq \left({\frac {1}{2}}-o(1)\right)n^{1-{\frac {1}{s}}}}$.

Esquema de la demostración:

• Se toma la mayor potencia prima ${\displaystyle q}$ con ${\displaystyle q^{s}\leq n}$. Debido a las brechas principales, se tiene que ${\displaystyle q=(1-o(1))n^{\frac {1}{s}}}$. Sea ${\displaystyle f\in \mathbb {F} _{q}[x_{1},x_{2},\cdots ,x_{s},y_{1},y_{2},\cdots ,y_{s}]_{\leq d}}$ un polinomio aleatorio en ${\displaystyle \mathbb {F} _{q}}$ con grado como máximo ${\displaystyle d=s^{2}}$ en ${\displaystyle X=(X_{1},X_{2},...,X_{s})}$ y ${\displaystyle Y=(Y_{1},Y_{2},...,Y_{s})}$ y que satisface ${\displaystyle f(X,Y)=f(Y,X)}$. Sea el grafo ${\displaystyle G}$ el conjunto de vértices ${\displaystyle \mathbb {F} _{q}^{s}}$ tal que dos vértices ${\displaystyle x,y}$ son adyacentes si ${\displaystyle f(x,y)=0}$.

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

La sobresaturación se refiere a una variante del problema del subgrafo prohibido, donde se considera que algún grafo uniforme ${\displaystyle h}$ ${\displaystyle G}$ contiene muchas copias de algún subgrafo prohibido ${\displaystyle H}$. Intuitivamente, se podría esperar que esto ocurra una vez que ${\displaystyle G}$ contenga significativamente más aristas que ${\displaystyle \operatorname {ex} (n,H)}$. Se introduce la densidad de Turán para formalizar esta noción.

La densidad de Turán de un grafo uniforme ${\displaystyle h}$ ${\displaystyle G}$ se define como:

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

Es cierto que ${\displaystyle {\frac {\operatorname {ex} (n,G)}{\binom {n}{h}}}}$ 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 ${\displaystyle \pi (K_{r+1})=1-{\frac {1}{r}}}$ y el teorema de Erdős-Stone da ${\displaystyle \pi (G)=1-{\frac {1}{\chi (H)-1}}}$. En particular, para ${\displaystyle G}$ bipartito, ${\displaystyle \pi (G)=0}$. Determinar la densidad de Turán ${\displaystyle \pi (H)}$ es equivalente a determinar ${\displaystyle \operatorname {ex} (n,G)}$ hasta un error vinculado a ${\displaystyle o(n^{2})}$.^[16]​

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

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

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 ${\displaystyle s,t}$ con ${\displaystyle t\geq s\geq 1}$, existe una constante ${\displaystyle C}$ (independiente de ${\displaystyle n}$) tal que ${\textstyle \operatorname {ex} (n,K_{s,t})\leq Cn^{2-{\frac {1}{s}}}}$ para todo entero positivo ${\displaystyle n}$.^[5]​

Esquema de la demostración:

• Sea ${\displaystyle G}$ un ${\displaystyle 2}$-grafo con ${\displaystyle n}$ vértices, y considérese el número de copias de ${\displaystyle K_{1,s}}$ en ${\displaystyle G}$. Dado un vértice de grado ${\displaystyle d}$, se obtienen exactamente ${\displaystyle {\binom {d}{s}}}$ copias de ${\displaystyle K_{1,s}}$ enraizadas en este vértice, para un total de ${\displaystyle \sum _{v\in V(G)}{\binom {\operatorname {deg} (v)}{s}}}$ copias. Aquí, ${\displaystyle {\binom {k}{s}}=0}$ cuando ${\displaystyle 0\leq k<s}$. Por una condición de convexidad, hay un total de al menos ${\displaystyle n{\binom {2e(G)/n}{s}}}$ copias de ${\displaystyle K_{1,s}}$. Además, claramente hay ${\displaystyle {\binom {n}{s}}}$ subconjuntos de ${\displaystyle s}$ vértices, por lo que si hay más de ${\displaystyle (t-1){\binom {n}{s}}}$ copias de ${\displaystyle K_{1,s}}$, entonces por el principio del palomar debe existir un subconjunto de ${\displaystyle s}$ vértices que forman el conjunto de hojas de al menos ${\displaystyle t}$ de estas copias, formando un ${\displaystyle K_{s,t}}$. Por lo tanto, existe una ocurrencia de ${\displaystyle K_{s,t}}$ mientras se tengan ${\displaystyle n{\binom {2e(G)/n}{s}}>(t-1){\binom {n}{s}}}$ elementos. En otras palabras, se tiene una ocurrencia si ${\displaystyle {\frac {e(G)^{s}}{n^{s-1}}}\geq O(n^{s})}$, lo que se simplifica a ${\displaystyle e(G)\geq O(n^{2-{\frac {1}{s}}})}$, 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 ${\displaystyle H'}$ de algún subgrafo prohibido ${\displaystyle H}$ y mostrar que si aparece demasiadas veces en ${\displaystyle G}$, ${\displaystyle H}$ también debe aparecer en ${\displaystyle G}$.

Otros teoremas relacionados con el problema del subgrafo prohibido que se pueden resolver con sobresaturación incluyen:

• ${\displaystyle \operatorname {ex} (n,C_{2t})\leq O(n^{1+1/t})}$.^[19]​
• Para cualquier ${\displaystyle t}$ y ${\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)}$.^[19]​
• Si ${\displaystyle Q}$ denota el grafo determinado por los vértices y aristas de un cubo, y ${\displaystyle Q^{*}}$ denota el grafo obtenido al unir dos vértices opuestos del cubo, entonces ${\displaystyle \operatorname {ex} (n,Q)\leq \operatorname {ex} (n,Q^{*})=O(n^{8/5})}$.^[18]​

El problema puede generalizarse para un conjunto de subgrafos prohibidos ${\displaystyle S}$: encontrar el número máximo de aristas en un grafo de ${\displaystyle n}$ vértices que no tiene un subgrafo isomorfo a ningún grafo de ${\displaystyle S}$.^[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 ${\displaystyle n}$ vértices que no contiene tetraedros. El análogo de la construcción de Turán sería dividir los vértices en subconjuntos ${\displaystyle V_{1},V_{2},V_{3}}$ casi iguales, y conectar los vértices ${\displaystyle x,y,z}$ mediante una construcción de 3-aristas si están todos en ${\displaystyle V_{i}}$ diferentes, o si dos de ellos están en ${\displaystyle V_{i}}$ y el tercero está en ${\displaystyle V_{i+1}}$ (donde ${\displaystyle V_{4}=V_{1}}$). Esta disposición no contiene tetraedros y la densidad de aristas es ${\displaystyle 5/9}$. Sin embargo, el límite superior más conocido es 0,562, utilizando la técnica de álgebra de banderas.^[21]​

• Teorema de Turán
• Problema de isomorfismo de subgrafos
• Caracterización de grafos prohibidos
• Erdős-Stone theorem
• Teoría de grafos extremales