Teorema de las esquinas

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]

EnunciadoEditar

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 pruebaEditar

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 cuantitativasEditar

Sea   la medida del subconjunto más grande de   tal que no contiene ninguna esquina. Las mejores cuotas conocidas son

 

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 multidimensionalEditar

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édiEditar

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.

ReferenciasEditar

  1. Ajtai, Miklós; Szemerédi, Endre (1974). «Sets of lattice points that form no squares». Stud. Sci. Math. Hungar. 9: 9-11. .
  2. 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. 
  3. 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. 
  4. 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. 
  5. 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. 
  6. 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 externosEditar