En las matemáticas del dibujo de gráficos , la desigualdad de números de cruce o el lema de cruce da un límite inferior en el número mínimo de cruces de un gráfico dado , en función del número de aristas y vértices del gráfico. Establece que, para gráficos donde el número e de aristas es suficientemente mayor que el número n de vértices, el número de cruce es al menos proporcional a e 3 / n 2 .
Tiene aplicaciones en diseño VLSI y geometría combinatoria , y fue descubierto de forma independiente por Ajtai , Chvátal , Newborn y Szemerédi [1] y por Leighton . [2]
Declaración e historia
La desigualdad del número de cruce establece que, para un gráfico simple no dirigido G con n vértices ye aristas tales que e > 7 n , el número de cruce cr ( G ) obedece a la desigualdad
La constante 29 es la más conocida hasta la fecha y se debe a Ackerman. [3] Para obtener resultados anteriores con constantes más débiles, consulte Pach & Tóth (1997) y Pach et al. (2006) . [4] [5] La constante 7 se puede reducir a 4 , pero a expensas de reemplazar 29 con la peor constante de 64 .
Es importante distinguir entre el número de cruce cr ( G ) y el número de cruce par-cr ( G ) . Como señalaron Pach y Tóth (2000) , el número de cruces por paresse refiere al número mínimo de pares de bordes que cada uno determina un cruce, mientras que el número de cruce simplemente se refiere al número mínimo de cruces. (Esta distinción es necesaria ya que algunos autores asumen que en un dibujo adecuado no se cruzan dos bordes más de una vez) [6].
Aplicaciones
La motivación de Leighton al estudiar los números cruzados fue la aplicación al diseño de VLSI en informática teórica. [2]
Más tarde, Székely (1997) se dio cuenta de que esta desigualdad producía demostraciones muy simples de algunos teoremas importantes en geometría de incidencia . Por ejemplo, el teorema de Szemerédi-Trotter , un límite superior en el número de incidencias que son posibles entre números dados de puntos y líneas en el plano, sigue al construir una gráfica cuyos vértices son los puntos y cuyas aristas son los segmentos de líneas entre puntos de incidencia. Si hubiera más incidencias que el límite de Szemerédi-Trotter, este gráfico necesariamente tendría más cruces que el número total de pares de líneas, una imposibilidad. La desigualdad también se puede usar para probar el teorema de Beck , que si un conjunto de puntos finitos no tiene un número lineal de puntos colineales, entonces determina un número cuadrático de líneas distintas. [7] Del mismo modo, Tamal Dey utilizó para probar los límites superiores sobre geométricas k conjuntos- . [8]
Prueba
Primero damos una estimación preliminar: para cualquier gráfico G con n vértices ye aristas, tenemos
Para probar esto, considere un diagrama de G que tiene exactamente cruces cr ( G ) . Cada uno de estos cruces se pueden eliminar mediante la eliminación de un borde de G . Por lo tanto, podemos encontrar una gráfica con al menos e - cr ( G ) aristas y n vértices sin cruces y, por lo tanto, es una gráfica plana . Pero a partir de la fórmula de Euler debemos tener e - cr ( G ) ≤ 3 n , y la afirmación sigue. (De hecho, tenemos e - cr ( G ) ≤ 3 n - 6 para n ≥ 3 ).
Para obtener la desigualdad de números de cruce real, ahora usamos un argumento probabilístico . Dejamos que 0 < p <1 sea un parámetro de probabilidad que se elegirá más tarde, y construimos un subgrafo aleatorio H de G permitiendo que cada vértice de G se encuentre en H independientemente con probabilidad p , y permitiendo que un borde de G esté en H si y sólo si se eligieron sus dos vértices para estar en H . Sean e H , n H y cr H el número de aristas, vértices y cruces de H , respectivamente. Desde H es un subgrafo de G , el diagrama de G contiene un diagrama de H . Por la desigualdad de números de cruce preliminar, tenemos
Tomando las expectativas que obtenemos
Dado que cada uno de los n vértices de G tiene una probabilidad p de estar en H , tenemos E [ n H ] = pn . De manera similar, cada uno de los bordes en G tiene una probabilidad p 2 de permanecer en H ya que ambos extremos necesitan permanecer en H , por lo tanto E [ e H ] = p 2 e . Finalmente, cada cruce en el diagrama de G tiene una probabilidad p 4 de permanecer en H , ya que cada cruce involucra cuatro vértices. Para ver esto, considere un diagrama de G con cruces cr ( G ) . Podemos suponer que dos aristas cualesquiera en este diagrama con un vértice común son disjuntos, de lo contrario podríamos intercambiar las partes que se cruzan de las dos aristas y reducir el número de cruces en uno. Así, cada cruce en este diagrama implica cuatro vértices distintos de G . Por lo tanto, E [cr H ] = p 4 cr ( G ) y tenemos
Ahora, si establecemos p = 4 n / e <1 (ya que asumimos que e > 4 n ), obtenemos después de algo de álgebra
Un ligero refinamiento de este argumento permite reemplazar 64 por 33,75 para e > 7,5 n . [3]
Variaciones
Para gráficos con la circunferencia más grande que 2 r y e ≥ 4 n , Pach, Spencer & Tóth (2000) demostraron una mejora de esta desigualdad a [9]
Adiprasito mostró una generalización a dimensiones superiores: [10] Sies un complejo simplicial que se asigna a trozos-linealmente a , y tiene -Caras dimensionales y -Caras dimensionales tales que , luego el número de intersecciones por pares -los rostros dimensionales es al menos
Referencias
- ^ Ajtai, M .; Chvátal, V .; Recién nacido, MM; Szemerédi, E. (1982), "Subgrafos sin cruce", Teoría y práctica de la combinatoria , Estudios de matemáticas de Holanda Septentrional, 60 , Holanda del Norte, Amsterdam, págs. 9-12, MR 0806962.
- ^ a b Leighton, T. (1983), Problemas de complejidad en VLSI , Foundations of Computing Series, Cambridge, MA: MIT Press.
- ^ a b Ackerman, Eyal (2019), "Sobre gráficos topológicos con un máximo de cuatro cruces por borde", Geometría computacional , 85 : 101574, 31, arXiv : 1509.01932 , doi : 10.1016 / j.comgeo.2019.101574 , MR 4010251.
- ^ Pach, János ; Tóth, Géza (1997), "Gráficos dibujados con pocos cruces por borde", Combinatorica , 17 (3): 427–439, doi : 10.1007 / BF01215922 , MR 1606052.
- ^ Pach, János ; Radoičić, Radoš; Tardos, Gábor; Tóth, Géza (2006), "Mejorar el lema de cruce al encontrar más cruces en gráficos dispersos", Geometría discreta y computacional , 36 (4): 527–552, doi : 10.1007 / s00454-006-1264-9 , MR 2267545.
- ^ Pach, János; Tóth, Géza (2000), "¿Qué número de cruce es de todos modos?", Journal of Combinatorial Theory, Serie B , 80 (2): 225–246, doi : 10.1006 / jctb.2000.1978.
- ^ Székely, LA (1997), "Números cruzados y problemas difíciles de Erd en geometría discreta", Combinatoria, Probabilidad y Computación , 6 (3): 353–358, doi : 10.1017 / S0963548397002976 , MR 1464571.
- ^ Dey, TK (1998), "Límites mejorados para conjuntos k planos y problemas relacionados", Geometría discreta y computacional , 19 (3): 373–382, doi : 10.1007 / PL00009354 , MR 1608878
- ^ Pach, J .; Spencer, J .; Tóth, G. (2000), "Nuevos límites en el cruce de números", Geometría discreta y computacional , 24 (4): 623–644, doi : 10.1145 / 304893.304943 , MR 1799605.
- ^ Adiprasito, Karim (26/12/2018). "Teoremas combinatorios de Lefschetz más allá de la positividad". arXiv : 1812.10454v3 [ math.CO ].