Teorema de los vértices

Enunciado en combinatoria aritmética

En combinatoria aritmética , el teorema de los vértices establece que para cada , para un número suficientemente grande de , cualquier conjunto de al menos puntos en la cuadrícula contiene un vértice, es decir, un triple de puntos de la forma con . Fue demostrado por primera vez por Miklós Ajtai y Endre Szemerédi en 1974 utilizando el teorema de Szemerédi . ^[1] En 2003, József Solymosi dio una prueba corta utilizando el lema de eliminación de triángulos . ^[2] ${\displaystyle \varepsilon >0}$ ${\displaystyle N}$ ${\displaystyle \varepsilon N^{2}}$ ${\displaystyle N\times N}$ ${\displaystyle \{1,\ldots ,N\}^{2}}$ ${\displaystyle \{(x,y),(x+h,y),(x,y+h)\}}$ ${\displaystyle h\neq 0}$

Declaración

Defina una esquina como un subconjunto de de la forma , donde y . Para cada , existe un entero positivo tal que para cualquier , cualquier subconjunto con tamaño al menos contiene una esquina. ${\displaystyle \mathbb {Z} ^{2}}$ ${\displaystyle \{(x,y),(x+h,y),(x,y+h)\}}$ ${\displaystyle x,y,h\in \mathbb {Z} }$ ${\displaystyle h\neq 0}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle N(\varepsilon )}$ ${\displaystyle N\geq N(\varepsilon )}$ ${\displaystyle A\subseteq \{1,\ldots ,N\}^{2}}$ ${\displaystyle \varepsilon N^{2}}$

La condición se puede relajar mostrando que si es denso, entonces tiene algún subconjunto denso que es centralmente simétrico. ${\displaystyle h\neq 0}$ ${\displaystyle h>0}$ ${\displaystyle A}$

Resumen de la prueba

Lo que sigue es un esbozo del argumento de Solymosi.

Supóngase que no tiene vértices. Construya un grafo auxiliar tripartito con partes , , y , donde corresponde a la recta , corresponde a la recta y corresponde a la recta . Conecte dos vértices si la intersección de sus rectas correspondientes se encuentra en . ${\displaystyle A\subset \{1,\ldots ,N\}^{2}}$ ${\displaystyle G}$ ${\displaystyle X=\{x_{1},\ldots ,x_{N}\}}$ ${\displaystyle Y=\{y_{1},\ldots ,y_{N}\}}$ ${\displaystyle Z=\{z_{1},\ldots ,z_{2N}\}}$ ${\displaystyle x_{i}}$ ${\displaystyle x=i}$ ${\displaystyle y_{j}}$ ${\displaystyle y=j}$ ${\displaystyle z_{k}}$ ${\displaystyle x+y=k}$ ${\displaystyle A}$

Nótese que un triángulo en corresponde a una esquina en , excepto en el caso trivial donde las líneas correspondientes a los vértices del triángulo concurren en un punto en . De ello se deduce que cada arista de está en exactamente un triángulo, por lo que por el lema de eliminación de triángulos , tiene aristas, por lo que , como se desea. ${\displaystyle G}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle o(|V(G)|^{2})}$ ${\displaystyle |A|=o(N^{2})}$

Límites cuantitativos

Sea el tamaño del subconjunto más grande del cual no contiene ningún vértice. Los límites más conocidos son ${\displaystyle r_{\angle }(N)}$ ${\displaystyle [N]^{2}}$

${\displaystyle {\frac {N^{2}}{2^{(c_{1}+o(1)){\sqrt {\log _{2}N}}}}}\leq r_{\angle }(N)\leq {\frac {N^{2}}{(\log \log N)^{c_{2}}}},}$

donde y . El límite inferior se debe a Green, ^[3] basándose en el trabajo de Linial y Shraibman. ^[4] El límite superior se debe a Shkredov. ^[5] ${\displaystyle c_{1}\approx 1.822}$ ${\displaystyle c_{2}\approx 0.0137}$

Extensión multidimensional

Un vértice en es un conjunto de puntos de la forma , donde es la base estándar de , y . La extensión natural del teorema de vértices a esta configuración se puede demostrar utilizando el lema de eliminación de hipergrafos , en el espíritu de la prueba de Solymosi. El lema de eliminación de hipergrafos fue demostrado independientemente por Gowers ^[6] y Nagle, Rödl, Schacht y Skokan. ^[7] ${\displaystyle \mathbb {Z} ^{d}}$ ${\displaystyle \{a\}\cup \{a+he_{i}:1\leq i\leq d\}}$ ${\displaystyle e_{1},\ldots ,e_{d}}$ ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle h\neq 0}$

Teorema de Szemerédi multidimensional

El teorema multidimensional de Szemerédi establece que para cualquier subconjunto finito fijo , y para cada , existe un entero positivo tal que para cualquier , cualquier subconjunto con tamaño contiene al menos un subconjunto de la forma . Este teorema se deduce del teorema de los vértices multidimensionales mediante un argumento de proyección simple. ^[6] En particular, el teorema de Roth sobre progresiones aritméticas se deduce directamente del teorema de los vértices ordinario. ${\displaystyle S\subseteq \mathbb {Z} ^{d}}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle N(S,\varepsilon )}$ ${\displaystyle N\geq N(S,\varepsilon )}$ ${\displaystyle A\subseteq \{1,\ldots ,N\}^{d}}$ ${\displaystyle \varepsilon N^{d}}$ ${\displaystyle a\cdot S+h}$

Referencias

1. Ajtai, Miklós ; Szemerédi, Endre (1974). "Conjuntos de puntos de red que no forman cuadrados". Semental. Ciencia. Matemáticas. Hungría . 9 : 9–11. SEÑOR  0369299..
2. Solymosi, József (2003). "Nota sobre una generalización del teorema de Roth". En Aronov, Boris; Basu, Saugata; Pach, János; et al. (eds.). Geometría discreta y computacional . Algoritmos y combinatoria. Vol. 25. Berlín: Springer-Verlag. págs. 825–827. doi :10.1007/978-3-642-55566-4_39. ISBN 3-540-00371-1.Señor 2038505  .
3. Green, Ben (2021). "Límites inferiores para conjuntos sin esquinas". Revista de Matemáticas de Nueva Zelanda . 51 . arXiv : 2102.11702 . doi :10.53733/86.
4. Linial, Nati ; Shraibman, Adi (2021). "Conjuntos sin esquinas más grandes a partir de mejores protocolos NOF Exactly-N". Análisis discreto . 2021 . arXiv : 2102.00421 . doi :10.19086/da.28933. S2CID  231740736.
5. Shkredov, ID (2006). "Sobre una generalización del teorema de Szemerédi". Actas de la London Mathematical Society . 93 (3): 723–760. arXiv : math/0503639 . doi :10.1017/S0024611506015991. S2CID  : 55252774.
6. Gowers, Timothy (2007). "Regularidad de hipergrafos y el teorema multidimensional de Szemerédi". Anales de Matemáticas . 166 (3): 897–946. arXiv : 0710.3032 . doi :10.4007/annals.2007.166.897. MR  2373376. S2CID  56118006.
7. Rodl, V.; Nagle, B.; Skokan, J.; Schacht, M.; Kohayakawa, Y. (26 de mayo de 2005). "De la portada: El método de regularidad de hipergrafos y sus aplicaciones". Actas de la Academia Nacional de Ciencias . 102 (23): 8109–8113. Bibcode :2005PNAS..102.8109R. doi : 10.1073/pnas.0502771102 . ISSN  0027-8424. PMC 1149431 . PMID  15919821. 

Enlaces externos

• Prueba del teorema de los vértices en Polymath.