Teorema de Szemeredi-Trotter

El teorema de Szemeredi-Trotter es un resultado de la geometría combinatoria . El teorema establece que dados n puntos y m líneas en un plano, el número de incidencias (es decir, el número de pares punto/línea donde un punto se encuentra en una línea) es

y este límite no se puede mejorar.

Una formulación equivalente del teorema es la siguiente. Dados n puntos y un entero k > 2 , el número de líneas que pasan por al menos k puntos es

La prueba original de Szemeredi y Trotter [1] era compleja y utilizaba una técnica combinatoria conocida como división celular . Más tarde, Szekei descubrió una prueba mucho más simple utilizando la desigualdad del número de intersección para los gráficos [2] (ver más abajo).

El teorema de Szemeredi-Trotter tiene varias consecuencias, incluido el teorema de Beck en geometría de incidencia .

Prueba de la primera afirmación

Podemos descartar líneas que contengan dos o menos puntos, ya que pueden dar un máximo de 2 m de incidencia. Por lo tanto, podemos suponer que cualquier línea contiene al menos tres puntos.

Si una línea contiene k puntos, entonces contiene k − 1 segmentos de línea que conectan dos de los n puntos. En particular, la línea contendrá al menos k / 2 de tales segmentos, ya que asumimos k ≥ 3 . Sumando todas esas incidencias a lo largo de todas las m líneas, encontramos que el número de segmentos obtenidos de esta manera es al menos igual a la mitad del número de todas las incidencias. Si denotamos por e el número de tales segmentos, es suficiente mostrar que

Consideremos ahora un grafo formado por n puntos como vértices ye segmentos como aristas. Como cada segmento se encuentra en una de las m rectas y dos rectas se cortan como máximo en un punto, el número de intersecciones de este gráfico no excede de m 2 . De la desigualdad del número de intersección, concluimos que e ≤ 7.5 n o m 2 ≥ e 3 / 33.75 n 2 . En cualquier caso, e ≤ 3.24( nm ) 2/3 + 7.5 n y obtenemos el límite requerido

Prueba de la segunda formulación

Dado que cualquier par de puntos puede conectarse como máximo por una línea, puede haber como máximo n ( n − 1)/2 l líneas que pueden conectar k o más puntos ya que k ≥ 2 . Este límite prueba el teorema para k pequeño (por ejemplo, si k ≤ C para alguna constante absoluta C ). Por lo tanto, solo tiene sentido considerar los casos en los que k es grande, digamos k ≥ C.

Supongamos que hay m líneas, cada una de las cuales contiene al menos k puntos. Estas líneas forman al menos mk incidencias, y luego, por la primera variante del teorema de Szemerédy-Trotter, tenemos

y al menos una igualdad de o se cumple . Descartamos la tercera posibilidad porque asumimos que k es grande, por lo que quedan las dos primeras. Pero en ambos casos, luego de simples cálculos algebraicos, obtenemos , que es requerido.

Optimalidad

Si no se tienen en cuenta factores constantes, el límite de incidencia de Szemeredy-Trotter no se puede mejorar. Para ver esto, considere para cualquier entero positivo N ∈ Z + el conjunto de puntos de la red de enteros

y un conjunto de líneas

Está claro que y . Dado que cada línea incide en N puntos (es decir, una vez para cada ), el número de incidencias es igual a , que corresponde al límite superior [3] .

Generalización para R d

Agaval y Aronov [4] encontraron una generalización de este resultado para una dimensión arbitraria R d . Dado un conjunto S que contiene n puntos y un conjunto H que contiene m hiperplanos, el número de incidencias de puntos desde S e hiperplanos desde H está acotado superiormente por el número

De manera equivalente, el número de hiperplanos en H que contienen k o más puntos está acotado arriba por el número

La construcción de Edelbrunner muestra que el límite es asintóticamente óptimo [5] .

Soimoshi y Tao obtuvieron un límite superior casi exacto para el número de ocurrencias entre puntos y variedades algebraicas en espacios de alta dimensión. Su demostración utiliza el teorema del sándwich polinomial [6] .

Aplicaciones

El teorema de Szemeredy-Trotter encuentra muchas aplicaciones en aditivo [7] [8] [9] y combinatoria aritmética (por ejemplo, para probar el teorema de la suma del producto [10] ).

Notas

  1. ↑ Szemerédi, Trotter, 1983 , p. 381–392.
  2. ↑ Szekely, 1997 , pág. 353–358.
  3. ↑ Tao, 2011 .
  4. ↑ Agarwal, Aronov, 1992 , pág. 359–369.
  5. ↑ Edelsbrunner, 1987 .
  6. ↑ Solimosi, Tao, 2012 .
  7. ↑ Tomasz Schoen, Ilya Shkredov, "Sobre sumas de conjuntos convexos" . Consultado el 19 de noviembre de 2018. Archivado desde el original el 12 de junio de 2018.
  8. ↑ A. Iosevich, S. Konyagin, M. Rudnev y V. Ten, "Sobre la complejidad combinatoria de las secuencias convexas", 19 de julio de 2004 . Consultado el 19 de noviembre de 2018. Archivado desde el original el 12 de junio de 2018.
  9. ↑ Elekes, Nathanson, Ruzsa, "Convexity and sumsets" (enlace no disponible) . Consultado el 19 de noviembre de 2018. Archivado desde el original el 12 de junio de 2018. 
  10. ↑ G. Elekes, Sobre el número de sumas y productos, Acta Arith. 81 (1997), 365–367. . Fecha de acceso: 19 de noviembre de 2018. Archivado desde el original el 7 de febrero de 2019.

Literatura

Lecturas adicionales