Problema del subgrafo prohibido

vértices que no contiene ningún subgrafo isomorfo ade modo que no haya dos vértices adyacentes del mismo color.El teorema de Turán establece que para los enteros positivosEsto resuelve el problema del subgrafo prohibido paracolores y, por lo tanto, no tiene subgrafos con un número cromático mayor queEsto sugiere que los casos de igualdad generales para el problema del subgrafo prohibido pueden estar relacionados con los casos de igualdad paraEsta intuición resulta ser correcta con un margen de error vinculado aEl teorema de Erdős-Stone establece que para todos los números enteros positivosEl 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 longitudEste 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 deSe puede encontrar que el número esperado de aristas restantes esvértices con al menos tantas aristas como el número esperado., el grafo debe prohibir todos los ciclos con longitud menor que igual aPara 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 talTeorema (Brown, 1966): Sin embargo, sigue siendo una cuestión abierta ajustar el límite inferior deTeorema (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 uniformeSe 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 grafovértices que no tiene un subgrafo isomorfo a ningún grafo deEsta disposición no contiene tetraedros y la densidad de aristas es