Problema del subgrafo prohibido

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