Teorema dels cantons

Archiu:Иллюстрация уголков.png

Una ilustració de la teorema dels cantons de la combinatòria aditiva: un subconjunt del quadrat.

En combinatoria aritmètica, la teorema dels cantons declara que per a cada $\epsilon >0$, per a $N$ suficientment gran, qualsevol conjunt en a lo manco $\epsilon N^2$ punts en el látice de $N\times N$ dau per $\{1,\dots ,N{\}}^2$ conté un cantó, és dir una terna de punts de la forma $\{(x,y),(x+h,y),(x,y+h)\}$ en $h\ne 0$. Va ser provat primer per Miklós Ajtai i Endre Szemerédi en 1974 utilisant el Teorema de Szemerédi. En 2003, József Solymosi va donar una prova curta utilisant el lema d'extracció del triàngul.

Enunciat

Definim un cantó com un subconjunt de ${\mathbb{Z}}^2$ de la forma $\{(x,y),(x+h,y),(x,y+h)\}$, a on i $x,y,h\in \mathbb{Z}$. Per a cada $h\ne 0$, existix un sancer positiu $N(\epsilon )$ tal que per a qualsevol $\epsilon >0$, qualsevol $N\ge N(\epsilon )$, qualsevol subconjunt $A\subseteq \{1,\dots ,N{\}}^2$ en tamany a lo manco $\epsilon N^2$ conté un cantó.

La condició $h\ne 0$ pot ser relaixada a $h>0$, mostrant que si $A$ és dens, llavors té algun subconjunt dens que és centralmente simètric.

Visió general de la prova

Lo que seguix és un esbós de l'argument de Solymosi.

Supongam que $A\subset \{1,\dots ,N{\}}^2$ és un conjunt lliure de cantons. Construir un grafo auxiliar tripartit $G$ en parts $X=\{x_1,\dots ,x_N\}$, $Y=\{y_1,\dots ,y_N\}$, i $Z=\{z_1,\dots ,z_{2N}\}$, a on $x_i$ correspon a la llínea $x=i$, $y_j$ correspon a la llínea $y=j$, i $z_k$ correspon a la llínea $x+y=k$. Conectem dos vèrtiços si l'intersecció de les seues llínees corresponents es troba en $A$.

Notem que un triàngul en $G$ correspon a un cantó en $A$, exceptuant el cas trivial a on les llínees que corresponen als vèrtiços del triàngul concur en un punt en $A$. Seguix que cada aresta de $G$ es troba en exactament un triàngul, per lo tant, pel lema d'extracció del triàngul, $G$ té $o(|V(G){|}^2)$ arestes, aixina que $|A|=o(N^2)$, com desijàvem mostrar.