Cruzar la desigualdad numérica

Los dibujos de gráficos densos tienen muchos cruces.

En las matemáticas del dibujo de gráficos , la desigualdad del número de cruce o lema de cruce da un límite inferior en el número mínimo de cruces de aristas en un dibujo plano de un gráfico determinado , en función del número de aristas y vértices del gráfico. Afirma 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 ³ / n ² .

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 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 costa 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 por pares par-cr( G ) . Como señalaron Pach y Tóth (2000), el número de cruces por pares se refiere al número mínimo de pares de aristas que cada uno determina 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 bordes que se crucen más de una vez.) ^[6] ${\displaystyle {\text{pair-cr}}(G)\leq {\text{cr}}(G)}$

Aplicaciones

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

Prueba

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

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

Para probar esto, considere un diagrama de G que tenga exactamente cruces cr( G ) . Cada uno de estos cruces se puede eliminar quitando un borde de G . Por lo tanto, podemos encontrar un gráfico con al menos e − cr( G ) aristas y n vértices sin cruces y, por tanto, es un gráfico plano . Pero a partir de la fórmula de Euler debemos tener entonces 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 real del número de cruce, ahora usamos un argumento probabilístico . Dejamos que 0 < p < 1 sea un parámetro de probabilidad que se elegirá más adelante 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 sólo si se eligiera que sus dos vértices estuvieran 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 numérica de cruce preliminar, tenemos

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

Tomando expectativas obtenemos

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

Dado que cada uno de los n vértices en G tenía 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 ² de permanecer en H ya que ambos puntos finales necesitan 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 cruces cr( G ) . 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 cruzan de las dos aristas y reducir el número de cruce en uno. Por tanto , cada cruce en este diagrama involucra cuatro vértices distintos de G. Por lo tanto, E [cr _H ] = p ⁴ cr( G ) y tenemos

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

Ahora bien, si establecemos 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 que 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 cruzan 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 .; 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, vol. 60, Holanda Septentrional, Ámsterdam, págs. 9–12, SEÑOR  0806962.
2. Leighton, T. (1983), Problemas de complejidad en VLSI , Serie Fundamentos de la Computación, Cambridge, MA: MIT Press.
3. Ackerman, Eyal (2019), "En gráficos topológicos con en la mayoría de los cuatro cruces por borde", Geometría computacional , 85 : 101574, 31, ARXIV : 1509.01932 , doi : 10.1016/j.comgeo.2019.101574, MR  4010251, s2cid  16844443.
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), "Mejorar el lema de cruce encontrando más cruces en gráficos dispersos", Geometría discreta y computacional , 36 (4): 527–552, doi : 10.1007/s00454-006-1264-9 , SEÑOR  2267545.
6. 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.
7. Székely, LA (1997), "Cruce de números y problemas difíciles de Erdős en geometría discreta", Combinatoria, probabilidad y computación , 6 (3): 353–358, doi :10.1017/S0963548397002976, MR  1464571, S2CID  36602807.
8. 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.
9. Pach, J .; Spencer, J .; Tóth, G. (2000), "Nuevos límites al cruzar números", 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].