En la teoría de grafos, el teorema de Erdős-Pose ( Pal Erdős y Lajos Pose ) establece que existe una función f ( k ) tal que, para cualquier número natural k , cualquier gráfico contiene k ciclos separados por vértices o tiene un ciclo- cortando el conjunto de f ( k ) vértices que intersecta cualquier ciclo. Además, f ( k ) = O( k log k ) en notación O Big . En vista de este teorema, se dice que los ciclos tienen la propiedad de Erdős-Pose .
El teorema establece que para cualquier número finito k , existe algún valor (mínimo) f ( k ) para el cual, en cualquier gráfico que no tenga k ciclos de vértice desconectado, todos los ciclos pueden estar cubiertos por f ( k ) vértices. Esto generaliza un resultado no publicado de Bolobash , que establece que f (2) = 3 . Erdős y Poza [1] obtuvieron cotas c 1 k log k < f ( k ) < c 2 k log k en el caso general. Este resultado sugiere que aunque hay infinitos grafos sin k ciclos inconexos, caen en un número finito de clases simplemente descriptibles. Para el caso k = 2 , Lovasz [2] dio una descripción completa. Voss [3] demostró que f (3) = 6 y 9 ≤ f (4) ≤ 12 .
Una familia F de grafos o hipergrafos por definición tiene la propiedad de Erdős-Pose si existe una función f : N → N tal que para cualquier (hiper-)grafo G y cualquier entero k uno de los siguientes es verdadero:
La definición a menudo se formula de la siguiente manera. Si denotamos por ν ( G ) el número máximo de vértices de subgrafos disjuntos de G que son isomorfos a los gráficos de F y por τ ( G ) el número máximo de vértices cuya eliminación de G deja el grafo sin gráficos isomorfos a los gráficos de F , entonces ν ( G ) ≤ f ( τ ( G )) , para alguna función f : N → N independiente de G .