El teorema de Szemerédi-Trotter es un resultado matemático en el campo de la geometría combinatoria . Afirma que dados n puntos ym líneas en el plano euclidiano , el número de incidencias ( es decir , el número de pares punto-línea, de manera que el punto se encuentra en la línea) es
este límite no se puede mejorar, excepto en términos de las constantes implícitas. En cuanto a las constantes implícitas, János Pach , Radoš Radoičić, Gábor Tardos y Géza Tóth [1] demostraron que el límite superiorsostiene. (Desde entonces se conocen mejores constantes debido al mejor cruce de las constantes del lema; la mejor corriente es 2,44.) Por otro lado, Pach y Tóth demostraron que la afirmación no es verdadera si se reemplaza el coeficiente 2,5 por 0,42. [2]
Una formulación equivalente del teorema es la siguiente. Dados n puntos y un número entero k ≥ 2 , el número de líneas que pasan por al menos k de los puntos es
La prueba original de Endre Szemerédi y William T. Trotter fue algo complicada, utilizando una técnica combinatoria conocida como descomposición celular . [3] [4] Más tarde, László Székely descubrió una prueba mucho más simple usando la desigualdad de números cruzados para gráficas . [5] (Ver más abajo).
El teorema de Szemerédi-Trotter tiene varias consecuencias, incluido el teorema de Beck en geometría de incidencia .
Prueba de la primera formulación
Podemos descartar las líneas que contienen dos o menos de los puntos, ya que pueden contribuir como máximo a incidencias de 2 m al número total. Por tanto, podemos suponer que cada línea contiene al menos tres de los puntos.
Si una línea contiene k puntos, entonces contendrá k - 1 segmentos de línea que conectan dos puntos consecutivos a lo largo de la línea. Debido a que k ≥ 3 después de descartar las líneas de dos puntos, se deduce que k - 1 ≥ k / 2 , por lo que el número de estos segmentos de línea en cada línea es al menos la mitad del número de incidencias en esa línea. Sumando todas las líneas, el número de estos segmentos de línea es nuevamente al menos la mitad del número total de incidencias. Por tanto, si e denota el número de tales segmentos de recta, será suficiente mostrar que
Ahora considere la gráfica formada usando los n puntos como vértices y los segmentos de línea e como aristas. Dado que cada segmento de línea se encuentra en una de m líneas, y dos líneas cualesquiera se cruzan como máximo en un punto, el número de cruce de este gráfico es como máximo el número de puntos donde se cruzan dos líneas, que es como máximo m ( m - 1) / 2 . La desigualdad del número de cruce implica que e ≤ 7.5 n , o que m ( m - 1) / 2 ≥ e 3 / 33.75 n 2 . En cualquier caso e ≤ 3.24 ( nm ) 2/3 + 7.5 n , dando el límite deseado
Prueba de la segunda formulación
Dado que cada par de puntos puede estar conectado como máximo por una línea, puede haber como máximo n ( n - 1) / 2 líneas que pueden conectarse en k o más puntos, ya que k ≥ 2 . Este límite probará el teorema cuando k es pequeño (por ejemplo, si k ≤ C para alguna constante absoluta C ). Por lo tanto, sólo hay que considerar el caso cuando k es grande, digamos k ≥ C .
Suponga que hay m rectas y cada una contiene al menos k puntos. Estas líneas generan al menos mk incidencias, por lo que según la primera formulación del teorema de Szemerédi-Trotter, tenemos
y entonces al menos una de las declaraciones , o es verdad. La tercera posibilidad está descartada ya que se supuso que k era grande, por lo que nos quedamos con las dos primeras. Pero en cualquiera de estos dos casos, algo de álgebra elemental dará el límite como se desee.
Optimalidad
Excepto por su constante, el límite de incidencia de Szemerédi-Trotter no se puede mejorar. Para ver esto, considere para cualquier entero positivo N ∈ Z + un conjunto de puntos en la red de enteros
y un conjunto de lineas
Claramente, y . Dado que cada línea incide en N puntos (es decir, una vez por cada), el número de incidencias es que coincide con el límite superior. [6]
Generalización a R d
Agarwal y Aronov encontraron una generalización de este resultado a una dimensión arbitraria, R d . [7] Dado un conjunto de n puntos, S , y el conjunto de m hiperplanos, H , cada uno de los cuales está abarcado por S , el número de incidencias entre S y H está acotado arriba por
De manera equivalente, el número de hiperplanos en H que contienen k puntos o más está acotado arriba por
Una construcción debida a Edelsbrunner muestra que este límite es asintóticamente óptimo. [8]
József Solymosi y Terence Tao obtuvieron límites superiores casi nítidos para el número de incidencias entre puntos y variedades algebraicas en dimensiones superiores, cuando los puntos y variedades satisfacen "ciertos axiomas de tipo pseudo-lineal". Su demostración utiliza el teorema del sándwich de jamón polinomial . [9]
Análogos sobre otros campos
Ha habido un cierto interés en probar análogos al teorema Szemerédi-Trotter en planos sobre los campos que no sean R . Todas las demostraciones conocidas del teorema de Szemerédi-Trotter sobre R se basan de manera crucial en la topología del espacio euclidiano, por lo que no se extienden fácilmente a otros campos. No obstante, se han obtenido los siguientes resultados:
Referencias
- ^ Pach, János ; Radoičić, Radoš; Tardos, Gábor ; Tóth, Géza (2006). "Mejorar el lema de cruce mediante la búsqueda de más cruces en gráficos dispersos" . Geometría discreta y computacional . 36 (4): 527–552. doi : 10.1007 / s00454-006-1264-9 .
- ^ Pach, János ; Tóth, Géza (1997). "Gráficos dibujados con pocos cruces por borde". Combinatorica . 17 (3): 427–439. CiteSeerX 10.1.1.47.4690 . doi : 10.1007 / BF01215922 .
- ^ Szemerédi, Endre ; Trotter, William T. (1983). "Problemas extremos en geometría discreta". Combinatorica . 3 (3–4): 381–392. doi : 10.1007 / BF02579194 . Señor 0729791 .
- ^ Szemerédi, Endre ; Trotter, William T. (1983). "Una distinción combinatoria entre los planos euclidiano y proyectivo" (PDF) . Revista europea de combinatoria . 4 (4): 385–394. doi : 10.1016 / S0195-6698 (83) 80036-5 .
- ^ Székely, László A. (1997). "Cruce de números y problemas duros de Erd hards en geometría discreta". Combinatoria, Probabilidad y Computación . 6 (3): 353–358. CiteSeerX 10.1.1.125.1484 . doi : 10.1017 / S0963548397002976 . Señor 1464571 .
- ^ Terence Tao (17 de marzo de 2011). "Un teorema de incidencia en dimensiones superiores" . Consultado el 26 de agosto de 2012 .
- ^ Agarwal, Pankaj ; Aronov, Boris (1992). "Contando facetas e incidencias" . Geometría discreta y computacional . 7 (1): 359–369. doi : 10.1007 / BF02187848 .
- ^ Edelsbrunner, Herbert (1987). "6.5 Límites inferiores para muchas celdas". Algoritmos en geometría combinatoria . Springer-Verlag. ISBN 978-3-540-13722-1.
- ^ Solymosi, József ; Tao, Terence (septiembre de 2012). "Un teorema de incidencia en dimensiones superiores". Geometría discreta y computacional . 48 (2): 255–280. arXiv : 1103.2926 . doi : 10.1007 / s00454-012-9420-x . Señor 2946447 .
- ^ Tóth, Csaba D. (2015). "El teorema de Szemerédi-Trotter en el plano complejo". Combinatorica . 35 (1): 95-126. arXiv : matemáticas / 0305283 . doi : 10.1007 / s00493-014-2686-2 .
- ^ Zahl, Joshua (2015). "Un teorema de tipo Szemerédi-Trotter en ℝ4". Geometría discreta y computacional . 54 (3): 513–572. arXiv : 1203,4600 . doi : 10.1007 / s00454-015-9717-7 .