En combinatoria aritmética, el teorema de las esquinas declara que para cada
, para
suficientemente grande, cualquier conjunto con al menos
puntos en el látice de
dado por
contiene una esquina, es decir una terna de puntos de la forma
con
. Fue probado primero 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 extracción del triángulo.[2]
Enunciado
Definimos una esquina como un subconjunto de
de la forma
, donde y
. Para cada
, existe un entero positivo
tal que para cualquier
, cualquier
, cualquier subconjunto
con tamaño al menos
contiene una esquina.
La condición
puede ser relajada a
, mostrando que si
es denso, entonces tiene algún subconjunto denso que es centralmente simétrico.
Visión general de la prueba
Lo que sigue es un esbozo del argumento de Solymosi.
Supongamos que
es un conjunto libre de esquinas. Construir un grafo auxiliar tripartito
con partes
,
, y
, donde
corresponde a la línea
,
corresponde a la línea
, y
corresponde a la línea
. Conectamos dos vértices si la intersección de sus líneas correspondientes se encuentra en
.
Notemos que un triángulo en
corresponde a una esquina en
, exceptuando el caso trivial donde las líneas que corresponden a los vértices del triángulo concur en un punto en
. Sigue que cada arista de
se encuentra en exactamente un triángulo, por lo tanto, por el lema de extracción del triángulo,
tiene
aristas, así que
, como deseábamos mostrar.
Cuotas cuantitativas
Sea
la medida del subconjunto más grande de
tal que no contiene ninguna esquina. Las mejores cuotas conocidas son
![{\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}}}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c0b1a79056dd3480deddb0d2dd545d39cbfab647)
donde
y
. La cuota más baja fue demostrada por Green, construyendo a partir del trabajo de Linial y Shraibman[3]. La cuota superior fue demostrada por Shkredov.[4]
Extensión multidimensional
Una esquina en
es un conjunto de puntos de la forma
, dónde
es la base estándar de
, y
. La extensión natural del teorema de esquinas a esta situación general puede ser mostrada utilizando el lema de extracción de hipergrafo, en el espíritu de la prueba de Solymosi. El lema de extracción de hieprgrafo fue mostrado independientemente por Gowers[5] y Nagle, Rödl, Schacht y Skokan[6].
Teorema Multidimensional de Szemerédi
El teorema multidimensional de Szemerédi declara que para cualquier subconjunto finito fijo
, y para cada
, existe un entero positivo
tal que para cualquier
, cualquier subconjunto
con tamaño al menos
contiene un subconjunto de la forma
. Este teorema sigue del teorema de esquinas multidimensional mediante un argumento de proyección sencillo[5]. En particular, el teorema de Roth sigue directamente del teorema de esquinas normal.
Referencias
- ↑ Ajtai, Miklós; Szemerédi, Endre (1974). «Sets of lattice points that form no squares». Stud. Sci. Math. Hungar. 9: 9-11. .
- ↑ Solymosi, József (2003). «Note on a generalization of Roth's theorem». En Aronov, Boris; Basu, Saugata; Pach, eds. Discrete and computational geometry. Algorithms and Combinatorics 25. Berlin: Springer-Verlag. pp. 825-827. ISBN 3-540-00371-1. doi:10.1007/978-3-642-55566-4_39.
- ↑ Linial, Nati; Shraibman, Adi (2021). «Larger Corner-Free Sets from Better NOF Exactly-N Protocols». Discrete Analysis. arXiv:2102.00421. doi:10.19086/da.28933.
- ↑ Shkredov, I.D. (2006). «On a Generalization of Szemerédi's Thoerem». Proceedings of the London Mathematical Society 93 (3): 723-760. arXiv:math/0503639. doi:10.1017/S0024611506015991.
- ↑ a b Gowers, Timothy (2007). «Hypergraph regularity and the multidimensional Szemerédi theorem». Annals of Mathematics 166 (3): 897-946. arXiv:0710.3032. doi:10.4007/annals.2007.166.897.
- ↑ Rodl, V.; Nagle, B.; Skokan, J.; Schacht, M.; Kohayakawa, Y. (26 de mayo de 2005). «From The Cover: The hypergraph regularity method and its applications». Proceedings of the National Academy of Sciences 102 (23): 8109-8113. Bibcode:2005PNAS..102.8109R. ISSN 0027-8424. PMC 1149431. PMID 15919821. doi:10.1073/pnas.0502771102.
Enlaces externos