Teorema de Szemerédi-Trotter

Acotado en el número de incidencias entre puntos y rectas en el plano.

El teorema de Szemerédi-Trotter es un resultado matemático en el campo de la geometría discreta . 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, tales que el punto se encuentra en la línea) es

$${\displaystyle O\left(n^{2/3}m^{2/3}+n+m\right).}$$

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 superior se cumple. Desde entonces, se conocen mejores constantes debido al mejor cruce de constantes de lemas; el mejor actual es 2,44. ^[2] Por otro lado, Pach y Tóth demostraron que la afirmación no es cierta si se reemplaza el coeficiente 2,5 por 0,42. ^[3] ${\displaystyle 2.5n^{2/3}m^{2/3}+n+m}$

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

$${\displaystyle O\left({\frac {n^{2}}{k^{3}}}+{\frac {n}{k}}\right).}$$

La prueba original de Endre Szemerédi y William T. Trotter fue algo complicada y utilizó una técnica combinatoria conocida como descomposición celular . ^{[4] [5]} Más tarde, László Székely descubrió una prueba mucho más simple utilizando la desigualdad de números cruzados para gráficas . ^[6] (Ver más abajo).

El teorema de Szemerédi-Trotter tiene varias consecuencias, incluido el teorema de Beck en geometría de incidencia y el problema de suma-producto de Erdős-Szemerédi en combinatoria aditiva .

Prueba de la primera formulación.

Podemos descartar las líneas que contengan dos o menos puntos, ya que pueden aportar como máximo 2 m de incidencias 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. Como k ≥ 3 después de descartar las rectas de dos puntos, se deduce que k − 1 ≥ k /2 , por lo que el número de estos segmentos de recta en cada recta es al menos la mitad del número de incidencias en esa recta. 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 lo tanto, si e denota el número de tales segmentos de línea, será suficiente demostrar que

$${\displaystyle e=O\left(n^{2/3}m^{2/3}+n+m\right).}$$

Ahora considere la gráfica formada usando los n puntos como vértices y los e segmentos de línea como aristas. Dado que cada segmento de línea se encuentra en una de las m líneas, y dos líneas cualesquiera se cruzan en como máximo un punto, el número de cruce de esta gráfica es como máximo el número de puntos donde dos líneas se cruzan, 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 ³ / 33,75 n ² . En cualquier caso e ≤ 3,24 ( nm ) ^2/3 + 7,5 n , dando el límite deseado

${\displaystyle e=O\left(n^{2/3}m^{2/3}+n+m\right).}$

Prueba de la segunda formulación.

Dado que cada par de puntos puede conectarse 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 demostrará el teorema cuando k sea pequeño (por ejemplo, si k ≤ C para alguna constante absoluta C ). Por tanto, sólo necesitamos considerar el caso en el que k es grande, digamos k ≥ C .

Supongamos que hay m líneas 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

$${\displaystyle mk=O\left(n^{2/3}m^{2/3}+n+m\right),}$$

y entonces al menos una de las afirmaciones , o es verdadera. La tercera posibilidad se descarta ya que se supuso que k era grande, por lo que nos quedan las dos primeras. Pero en cualquiera de estos dos casos, algo de álgebra elemental dará la cota deseada. ${\displaystyle mk=O(n^{2/3}m^{2/3}),mk=O(n)}$ ${\displaystyle mk=O(m)}$ ${\displaystyle m=O(n^{2}/k^{3}+n/k)}$

Optimidad

Excepto por su constante, el límite de incidencia Szemerédi-Trotter no se puede mejorar. Para ver esto, considere para cualquier número entero positivo un conjunto de puntos en la red de números enteros. ${\displaystyle N\in \mathbb {N} }$

$${\displaystyle P=\left\{(a,b)\in \mathbb {Z} ^{2}\ :\ 1\leq a\leq N;1\leq b\leq 2N^{2}\right\},}$$

y un conjunto de líneas

$${\displaystyle L=\left\{(x,mx+b)\ :\ m,b\in \mathbb {Z} ;1\leq m\leq N;1\leq b\leq N^{2}\right\}.}$$

Claramente, y . Dado que cada línea incide en N puntos (es decir, una vez por cada ), el número de incidencias es el que coincide con el límite superior. ^[7] ${\displaystyle |P|=2N^{3}}$ ${\displaystyle |L|=N^{3}}$ ${\displaystyle x\in \{1,\cdots ,N\}}$ ${\displaystyle N^{4}}$

Generalización a R d {\displaystyle \mathbb {R} ^{d}}

Agarwal y Aronov encontraron una generalización de este resultado a una dimensión arbitraria . ^[8] 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 ${\displaystyle \mathbb {R} ^{d}}$

$${\displaystyle O\left(m^{2/3}n^{d/3}+n^{d-1}\right),}$$

proporcionó . De manera equivalente, el número de hiperplanos en H que contienen k o más puntos está limitado arriba por ${\displaystyle n^{d-2}<m<n^{d}}$

$${\displaystyle O\left({\frac {n^{d}}{k^{3}}}+{\frac {n^{d-1}}{k}}\right).}$$

Una construcción debida a Edelsbrunner muestra que esto es asintóticamente óptimo. ^[9]

József Solymosi y Terence Tao obtuvieron límites superiores casi definidos para el número de incidencias entre puntos y variedades algebraicas en dimensiones superiores, cuando los puntos y variedades satisfacen "ciertos axiomas de tipo pseudolínea". Su prueba utiliza el teorema del sándwich de jamón polinómico. ^[10]

En C 2 {\displaystyle \mathbb {C} ^{2}}

Muchas pruebas del teorema de Szemerédi-Trotter se basan de manera crucial en la topología del espacio euclidiano , por lo que no se extienden fácilmente a otros campos . por ejemplo, la prueba original de Szemerédi y Trotter; la prueba de partición polinómica y la prueba de números de cruce no se extienden al plano complejo . ${\displaystyle \mathbb {R} }$

Tóth generalizó con éxito la prueba original de Szemerédi y Trotter al plano complejo introduciendo ideas adicionales. ^[11] Zahl también obtuvo este resultado de forma independiente y mediante un método diferente. ^[12] La constante implícita en el límite no es la misma en los números complejos : en la prueba de Tóth se puede considerar que la constante es ; la constante no es explícita en la prueba de Zahl. ${\displaystyle \mathbb {C} ^{2}}$ ${\displaystyle 10^{60}}$

Cuando el conjunto de puntos es un producto cartesiano , Solymosi y Tardos demuestran que el límite de Szemerédi-Trotter se cumple utilizando un argumento mucho más simple. ^[13]

En campos finitos

Sea un campo . ${\displaystyle \mathbb {F} }$

Un límite de Szemerédi-Trotter es imposible en general debido al siguiente ejemplo, indicado aquí en : sea el conjunto de todos los puntos y sea el conjunto de todas las líneas en el plano. Como cada línea contiene puntos, hay incidencias. En cambio, un rebote de Szemerédi-Trotter daría incidencias. Este ejemplo muestra que el límite de incidencia combinatoria trivial es ajustado. ${\displaystyle \mathbb {F} _{p}}$ ${\displaystyle {\mathcal {P}}=\mathbb {F} _{p}\times \mathbb {F} _{p}}$ ${\displaystyle p^{2}}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle p^{2}}$ ${\displaystyle p}$ ${\displaystyle p^{3}}$ ${\displaystyle O((p^{2})^{2/3}(p^{2})^{2/3}+p^{2})=O(p^{8/3})}$

Bougain , Katz y Tao ^[14] muestran que si se excluye este ejemplo, entonces se puede alcanzar un límite de incidencia que es una mejora del límite trivial.

Los límites de incidencia sobre campos finitos son de dos tipos: (i) cuando al menos uno del conjunto de puntos o líneas es "grande" en términos de las características del campo; (ii) tanto el conjunto de puntos como el conjunto de líneas son "pequeños" en términos de la característica.

Límites de incidencia establecidos grandes

Sea una potencia prima impar . Luego Vinh ^[15] demostró que el número de incidencias entre puntos y líneas es como máximo ${\displaystyle q}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle \mathbb {F} _{q}^{2}}$

$${\displaystyle {\frac {nm}{q}}+{\sqrt {qnm}}.}$$

Tenga en cuenta que no hay una constante implícita en este límite.

Límites de incidencia establecidos pequeños

Sea un campo de características . Stevens y de Zeeuw ^[16] muestran que el número de incidencias entre puntos y líneas en es ${\displaystyle \mathbb {F} }$ ${\displaystyle p\neq 2}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle \mathbb {F} ^{2}}$

$${\displaystyle O\left(m^{11/15}n^{11/15}\right)}$$

bajo la condición de característica positiva. (En un campo de característica cero, esta condición no es necesaria). Este límite es mejor que la estimación de incidencia trivial cuando . ${\displaystyle m^{-2}n^{13}\leq p^{15}}$ ${\displaystyle m^{7/8}<n<m^{8/7}}$

Si el conjunto de puntos es un producto cartesiano, entonces muestran un límite de incidencia mejorado: sea un conjunto finito de puntos con y sea un conjunto de líneas en el plano. Supongamos que y en característica positiva que . Entonces el número de incidencias entre y es ${\displaystyle {\mathcal {P}}=A\times B\subseteq \mathbb {F} ^{2}}$ ${\displaystyle |A|\leq |B|}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle |A||B|^{2}\leq |{\mathcal {L}}|^{3}}$ ${\displaystyle |A||{\mathcal {L}}|\leq p^{2}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {L}}}$

$${\displaystyle O\left(|A|^{3/4}|B|^{1/2}|{\mathcal {L}}|^{3/4}+|{\mathcal {L}}|\right).}$$

Este límite es óptimo. Tenga en cuenta que por la dualidad punto-línea en el plano, este límite de incidencia se puede reformular para un conjunto de puntos arbitrario y un conjunto de líneas que tienen una estructura de producto cartesiano.

Tanto en el campo real como en el arbitrario, Rudnev y Shkredov ^[17] muestran una incidencia limitada cuando tanto el conjunto de puntos como el conjunto de líneas tienen una estructura de producto cartesiano. A veces esto es mejor que los límites anteriores.

Referencias

1. Pach, János ; Radoičić, Radoš; Tardos, Gabor ; Toth, 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 .
2. Ackerman, Eyal (diciembre de 2019). "Sobre gráficos topológicos con como máximo cuatro cruces por arista". Geometría Computacional . 85 : 101574. arXiv : 1509.01932 . doi : 10.1016/j.comgeo.2019.101574. ISSN  0925-7721. S2CID  16847443.
3. Pach, János ; Toth, Géza (1997). "Gráficos elaborados con pocos cruces por arista". Combinatoria . 17 (3): 427–439. CiteSeerX 10.1.1.47.4690 . doi : 10.1007/BF01215922 . S2CID  20480170. 
4. Szemerédi, Endre ; Trotón, William T. (1983). "Problemas extremos en geometría discreta". Combinatoria . 3 (3–4): 381–392. doi : 10.1007/BF02579194 . SEÑOR  0729791. S2CID  1750834.
5. Szemerédi, Endre ; Trotón, 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 .
6. Székely, László A. (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. CiteSeerX 10.1.1.125.1484 . doi :10.1017/S0963548397002976. SEÑOR  1464571. S2CID  36602807. 
7. Terence Tao (17 de marzo de 2011). "Un teorema de incidencia en dimensiones superiores" . Consultado el 26 de agosto de 2012 .
8. Agarwal, Pankaj ; Aronov, Boris (1992). "Contando facetas e incidencias". Geometría discreta y computacional . 7 (1): 359–369. doi : 10.1007/BF02187848 .
9. Edelsbrunner, Herbert (1987). "6.5 Límites inferiores para muchas celdas". Algoritmos en Geometría Combinatoria . Springer-Verlag. ISBN 978-3-540-13722-1.
10. 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. S2CID  17830766.
11. Tóth, Csaba D. (2015). "El teorema de Szemerédi-Trotter en el plano complejo". Combinatoria . 35 (1): 95-126. arXiv : matemáticas/0305283 . doi : 10.1007/s00493-014-2686-2 . S2CID  13237229.
12. Zahl, Josué (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 . S2CID  16610999.
13. Solymosi, Jozsef; Tardos, Gabor (2007). "Sobre el número de transformaciones ricas en k". Actas del vigésimo tercer simposio anual sobre geometría computacional - SCG '07 . SCG '07. Nueva York, Nueva York, Estados Unidos: ACM Press. págs. 227-231. doi :10.1145/1247069.1247111. ISBN 978-1-59593-705-6. S2CID  15928844.
14. Bourgain, Jean; Katz, redes; Tao, Terence (1 de febrero de 2004). "Una estimación de suma producto en campos finitos y aplicaciones". Análisis Geométrico y Funcional . 14 (1): 27–57. arXiv : matemáticas/0301343 . doi : 10.1007/s00039-004-0451-1 . ISSN  1016-443X. S2CID  14097626.
15. Vinh, Le Anh (noviembre de 2011). "El teorema de tipo Szemerédi-Trotter y la estimación del producto suma en campos finitos". Revista europea de combinatoria . 32 (8): 1177–1181. arXiv : 0711.4427 . doi : 10.1016/j.ejc.2011.06.008 . ISSN  0195-6698. S2CID  1956316.
16. Stevens, Sofía; de Zeeuw, Frank (3 de agosto de 2017). "Una incidencia de línea de puntos mejorada limitada a campos arbitrarios". Boletín de la Sociedad Matemática de Londres . 49 (5): 842–858. arXiv : 1609.06284 . doi :10.1112/blms.12077. ISSN  0024-6093. S2CID  119635655.
17. Rudnev, Misha; Shkredov, Ilya D. (julio de 2022). "Sobre la tasa de crecimiento en SL_2 (F_p), las implicaciones del grupo afín y del tipo de producto suma". Matemática . 68 (3): 738–783. arXiv : 1812.01671 . doi :10.1112/mtk.12120. S2CID  248710290.