vértices que no contiene ningún subgrafo isomorfo a
de modo que no haya dos vértices adyacentes del mismo color.
El teorema de Turán establece que para los enteros positivos
Esto resuelve el problema del subgrafo prohibido para
colores y, por lo tanto, no tiene subgrafos con un número cromático mayor que
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
El teorema de Erdős-Stone establece que para todos los números enteros positivos
El problema del subgrafo prohibido para grafos bipartitos se conoce como problema de Zarankiewicz y, en general, no está resuelto.
tienen el mismo punto final y no se superponen, entonces crean un ciclo de longitud
Este lema permite manejar grafos bipartitos con grado acotado en una parte: En general, se tiene la siguiente conjetura: 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.
y al final nos queda un grafo libre de
Se puede encontrar que el número esperado de aristas restantes es
vértices con al menos tantas aristas como el número esperado.
, el grafo debe prohibir todos los ciclos con longitud menor que igual a
Para casos específicos, se han realizado mejoras encontrando construcciones algebraicas.
, 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.
[11] suficientemente grande) y construir un grafo de polaridad usando tal
Teorema (Brown, 1966): Sin embargo, sigue siendo una cuestión abierta ajustar el límite inferior de
Teorema (Alon et al., 1999): 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: La sobresaturación se refiere a una variante del problema del subgrafo prohibido, donde se considera que algún grafo uniforme
Se introduce la densidad de Turán para formalizar esta noción.
es de hecho positivo y monótono decreciente, por lo que el límite debe existir.
[17] De manera equivalente, se puede reformular este teorema como sigue: si un grafo
vértices que no tiene un subgrafo isomorfo a ningún grafo de
Esta disposición no contiene tetraedros y la densidad de aristas es