Número de cruce (teoría de grafos)
[1] Sin embargo, el mismo problema de minimizar cruces fue también considerado en sociología aproximadamente al mismo tiempo que Turán, en conexión con la construcción de sociogramas.
El error en la prueba de la cota inferior no fue descubierto hasta once años después de su publicación, casi simultáneamente por Gerhard Ringel y Paul Kainen (véase "Decline and fall of Zarankiewicz's Theorem").
[6] El problema de determinar el número de cruce del grafo completo fue planteado por primera vez por Anthony Hill, y aparece impreso en 1960.
[7] Hill y su colaborador John Ernest eran dos artistas constructivistas fascinados por las matemáticas, quienes no solo formularon este problema sino que también originaron un límite superior conjetural para este número de cruce, publicado por Richard K. Guy en 1960,[7] a saber: que da valores de
[8] Una formulación independiente de la conjetura fue hecha por Thomas L. Saaty en 1964.
[9] Saaty verificó además que el límite superior es alcanzado por
Los números de cruce rectilíneos para K5 hasta K12 son 1, 3, 9, 19, 36, 62, 102, 153,[10] y se conocen los valores hasta K27, con K28 requiriendo o 7233 o 7234 cruces.
Valores posteriores son recogidos en el Rectilinear Crossing Number project.
[11] Curiosamente, no se sabe si los números de cruce ordinarios y rectilíneos son los mismos para grafos bipartitos completos.
Ha habido algunos avances en cotas inferiores, según lo informado por de Klerk et al.
[13] La conjetura de Albertson, formulada por Michael O. Albertson en 2007, establece que, entre todos los grafos con número cromático n, el grafo completo Kn tiene el número mínimo de cruces.
[15] De hecho, el problema sigue siendo NP-difícil incluso cuando se restringe a grafos cúbicos[16] y a los gráficos casi planos[17] (gráficos que se vuelven planos después de eliminar un solo borde).
[18] En el lado positivo, existen algoritmos eficientes para determinar si el número de cruce es menor que una constante fija k; en otras palabras, el problema es de complejidad parametrizada.
[20] En la práctica, se utilizan algoritmos heurísticos, como el algoritmo simple que comienza sin bordes y agrega continuamente cada nuevo borde de manera que produzca la menor cantidad posible de cruces adicionales.
Estos algoritmos se utilizan en el proyecto Rectilinear Crossing Number[21] mediante computación distribuida.
Los grafos cúbicos más pequeños con números de cruce del 1 al 8 se conocen como (sucesión A110507 en OEIS).
El gráfico cúbico de 1 cruce más pequeño es el grafo bipartito completo K3,3, con 6 vértices.
[23][24] La muy útil desigualdad del número de cruce, descubierta independientemente por Ajtai, Chvátal, Newborn y Szemerédi[25] y por Leighton,[26] afirma que si un grafo G (no dirigido, sin bucles ni aristas múltiples) con n vértices y e aristas satisface entonces se tiene que La constante 29 es la más conocida hasta la fecha, y se debe a Ackerman.
Tamal Dey lo usó para probar los límites superiores en k-conjuntos geométricos.
[29] Para gráficos con cintura mayor que 2r y e ≥ 4n, Pach, Spencer y Tóth[30] demostraron una mejora de esta desigualdad a: Primero se da una estimación preliminar: para cualquier grafo G con n vértices y e aristas, se tiene que Para probar esto, considérese un diagrama G que tiene exactamente cr(G) cruces.
Pero según la fórmula de Euler entonces se deben tener
Para obtener la desigualdad del número de cruce real, se usa un argumento probabilístico.
Por la desigualdad del número de cruce previa, se tiene que Tomando estadísticamente esperanzas, se obtiene que Como cada uno de los vértices n en G tenía una probabilidad p de estar en H, entonces
Finalmente, todo cruce en el diagrama de G tiene una probabilidad
de permanecer en H, ya que todo cruce involucra cuatro vértices, y por tanto
