Desigualdad de números cruzados

Los dibujos de gráficos densos tienen muchos cruces.

En las matemáticas del dibujo de grafos , la desigualdad del número de cruces o lema de cruces proporciona un límite inferior para el número mínimo de cruces de aristas en un dibujo plano de un grafo dado , en función del número de aristas y vértices del grafo. Establece que, para grafos donde el número e de aristas es suficientemente mayor que el número n de vértices, el número de cruces es al menos proporcional a e ³ / n ² .

Tiene aplicaciones en diseño VLSI y geometría combinatoria , y fue descubierto independientemente por Ajtai , Chvátal , Newborn y Szemerédi ^[1] y por Leighton . ^[2]

Declaración y antecedentes

La desigualdad del número de cruce establece que, para un grafo simple no dirigido G con n vértices y e aristas tales que e > 7 n , el número de cruce cr( G ) obedece a la desigualdad

${\displaystyle \operatorname {cr} (G)\geq {\frac {e^{3}}{29n^{2}}}.}$

La constante 29 es la más conocida hasta la fecha y se debe a Ackerman. ^[3] Para 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 cruces cr( G ) y el número de cruces por pares pair-cr( G ) . Como señalan Pach y Tóth (2000), el número de cruces por pares se refiere al número mínimo de pares de aristas que determinan cada uno un cruce, mientras que el número de cruces simplemente se refiere al número mínimo de cruces. (Esta distinción es necesaria ya que algunos autores suponen que en un dibujo adecuado no hay dos aristas que se crucen más de una vez.) ^[6] ${\displaystyle {\text{pair-cr}}(G)\leq {\text{cr}}(G)}$

Aplicaciones

La motivación de Leighton para estudiar los números cruzados fue para aplicaciones al diseño VLSI en la 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 un número dado de puntos y líneas en el plano, se deduce de la construcción de un grafo cuyos vértices son los puntos y cuyos bordes son los segmentos de líneas entre puntos incidentes. Si hubiera más incidencias que el límite de Szemerédi-Trotter, este grafo necesariamente tendría más cruces que el número total de pares de líneas, una imposibilidad. La desigualdad también se puede utilizar para demostrar el teorema de Beck , que si un conjunto de puntos finito no tiene un número lineal de puntos colineales, entonces determina un número cuadrático de líneas distintas. ^[7] De manera similar, Tamal Dey lo utilizó para demostrar límites superiores en conjuntos geométricos k . ^[8]

Prueba

Primero damos una estimación preliminar: para cualquier grafo G con n vértices y e aristas, tenemos

${\displaystyle \operatorname {cr} (G)\geq e-3n.}$

Para demostrarlo, considere un diagrama de G que tiene exactamente cr( G ) cruces. Cada uno de estos cruces se puede eliminar eliminando una arista de G . Por lo tanto, podemos encontrar un grafo con al menos e − cr( G ) aristas y n vértices sin cruces, y es, por lo tanto, un grafo plano . Pero a partir de la fórmula de Euler debemos tener e − cr( G ) ≤ 3 n , y la afirmación se sigue. (De hecho, tenemos e − cr( G ) ≤ 3 n − 6 para n ≥ 3 ).

Para obtener la desigualdad real del número de cruces, 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 una arista de G se encuentre en H si y solo si se eligió que sus dos vértices se encontraran en H . Sean e _H , n _H y cr _H el número de aristas, vértices y cruces de H , respectivamente. Dado que H es un subgrafo de G , el diagrama de G contiene un diagrama de H . Por la desigualdad preliminar del número de cruces, tenemos

${\displaystyle \operatorname {cr} _{H}\geq e_{H}-3n_{H}.}$

Tomando las expectativas que obtenemos

${\displaystyle \mathbf {E} [\operatorname {cr} _{H}]\geq \mathbf {E} [e_{H}]-3\mathbf {E} [n_{H}].}$

Como cada uno de los n vértices de G tenía una probabilidad p de estar en H , tenemos que E [ n _H ] = pn . De manera similar, cada una de las aristas de G tiene una probabilidad p ² de permanecer en H , ya que ambos extremos deben permanecer en H , por lo tanto, E [ e _H ] = p ² e . Finalmente, cada cruce en el diagrama de G tiene una probabilidad p ⁴ de permanecer en H , ya que cada cruce involucra cuatro vértices. Para ver esto, considere un diagrama de G con cr( G ) cruces. Podemos suponer que dos aristas cualesquiera en este diagrama con un vértice común son disjuntas, de lo contrario podríamos intercambiar las partes que se intersecan de las dos aristas y reducir el número de cruces en uno. Por lo tanto, cada cruce en este diagrama involucra cuatro vértices distintos de G. El diagrama que tenemos puede no ser óptimo en términos de número de cruces, pero obviamente tiene al menos cr _H cruces. Por lo tanto,

${\displaystyle p^{4}\operatorname {cr} (G)\geq \mathbf {E} [\operatorname {cr} _{H}]}$

y tenemos

${\displaystyle p^{4}\operatorname {cr} (G)\geq p^{2}e-3pn.}$

Ahora bien, si fijamos p = 4 n / e < 1 (ya que asumimos que e > 4 n ), obtenemos después de algo de álgebra

${\displaystyle \operatorname {cr} (G)\geq {\frac {e^{3}}{64n^{2}}}.}$

Un ligero refinamiento de este argumento permite reemplazar 64 por 33,75 para e > 7,5 n . ^[3]

Variaciones

Para gráficos con circunferencia mayor a 2 r y e ≥ 4 n , Pach, Spencer y Tóth (2000) demostraron una mejora de esta desigualdad a ^[9]

${\displaystyle \operatorname {cr} (G)\geq c_{r}{\frac {e^{r+2}}{n^{r+1}}}.}$

Adiprasito mostró una generalización a dimensiones superiores: ^[10] Si es un complejo simplicial que se asigna linealmente por partes a , y tiene caras -dimensionales y caras -dimensionales tales que , entonces el número de caras -dimensionales que se intersecan por pares es al menos ${\displaystyle \Delta }$ ${\displaystyle \mathbf {R} ^{2d}}$ ${\displaystyle f_{d}(\Delta )\ \ d}$ ${\displaystyle f_{d-1}(\Delta )\ \ (d-1)}$ ${\displaystyle f_{d}(\Delta )>(d+3)f_{d-1}(\Delta )}$ ${\displaystyle d}$

${\displaystyle {\frac {f_{d}^{d+2}(\Delta )}{(d+3)^{d+2}f_{d-1}^{d+1}(\Delta )}}.}$

Referencias

1. Ajtai, M. ; Chvátal, V. ; Newborn, MM; Szemerédi, E. (1982), "Subgrafos sin cruces", Teoría y práctica de la combinatoria , North-Holland Mathematics Studies, vol. 60, North-Holland, Ámsterdam, págs. 9-12, MR  0806962.
2. Leighton, T. (1983), Problemas de complejidad en VLSI , Serie Fundamentos de la computación, Cambridge, MA: MIT Press.
3. Ackerman, Eyal (2019), "Sobre gráficos topológicos con un máximo de cuatro cruces por arista", Computational Geometry , 85 : 101574, 31, arXiv : 1509.01932 , doi : 10.1016/j.comgeo.2019.101574, MR  4010251, S2CID  16847443.
4. Pach, János ; Tóth, Géza (1997), "Gráficos dibujados con pocos cruces por arista", Combinatorica , 17 (3): 427–439, doi :10.1007/BF01215922, MR  1606052, S2CID  20480170.
5. Pach, János ; Radoičić, Radoš; Tardos, Gábor; Tóth, Géza (2006), "Mejora del lema de cruces mediante la búsqueda de más cruces en grafos dispersos", Geometría discreta y computacional , 36 (4): 527–552, doi : 10.1007/s00454-006-1264-9 , MR  2267545.
6. Pach, János; Tóth, Géza (2000), "¿Qué número de cruce es, en cualquier caso?", Journal of Combinatorial Theory, Serie B , 80 (2): 225–246, doi : 10.1006/jctb.2000.1978.
7. Székely, LA (1997), "Números cruzados y problemas de Erdős difíciles en geometría discreta", Combinatorics, Probability and Computing , 6 (3): 353–358, doi :10.1017/S0963548397002976, MR  1464571, S2CID  36602807.
8. Dey, TK (1998), "Límites mejorados para conjuntos k planares y problemas relacionados", Geometría discreta y computacional , 19 (3): 373–382, doi : 10.1007/PL00009354 , MR  1608878.
9. Pach, J. ; Spencer, J. ; Tóth, G. (2000), "Nuevos límites en los números cruzados", Geometría discreta y computacional , 24 (4): 623–644, doi : 10.1007/s004540010011 , MR  1799605.
10. Adiprasito, Karim (26 de diciembre de 2018), "Teoremas combinatorios de Lefschetz más allá de la positividad", arXiv : 1812.10454v3 [math.CO].