Teorema de Erdős-Szekeres

Un camí de quatre arestes ascendents en un conjunt de 17 punts. Per la teorema de Erdős-Szekeres, tot conjunt de 17 punts té un camí d'esta llongitut ben ascendent o ben descendent. El subconjunt de 16 punts que no inclou el punt central no té cap camí d'este tipo.

En matemàtiques, la teorema de Erdős-Szekeres és un resultat de finitud que precisa un dels corolaris del teorema de Ramsey. Mentres que la teorema de Ramsey facilita provar que tota successió infinita de número real distints conté una subsucesión infinita monòtonament creixent o una subsucesión infinita monòtonament decreixent, el resultat que varen provar Paul Erdős i George Szekeres va més allà. Per a $r$, $s$ daus, varen provar que qualsevol successió de llongitut a lo manco $(r-1)(s-1)+1$ conté una subsucesión monòtonament creixent de llongitut $r$ o una subsucesión monòtonament decreixent de llongitut $s$. La demostració està en el mateix artícul de 1935 que menciona el problema del final feliç.

Eixemple

Per a $r=3$ i $s=2$, la fòrmula afirma que qualsevol permutació de tres números té una subsucesión creixent de llongitut tres o una subsucesión decreixent de llongitut dos. Prenent les sis possibles permutació dels números 1, 2, 3:

• 1,2,3 té una subsucesión creixent consistent en els tres números
• 1,3,2 té una subsucesión decreixent 3,2
• 2,1,3 té una subsucesión decreixent 2,1
• 2,3,1 té dos subsucesiones decreixents, 2,1 i 3,1
• 3,1,2 té dos subsucesiones decreixents, 3,1 i 3,2
• 3,2,1 té tres subsucesiones decreixents de llongitut dos, 3,2, 3,1, i 2,1.

Interpretacions alternatives

Interpretació geomètrica

Es poden interpretar les posicions dels números en una successió com les coordenades x de punts en el pla euclídeo, i els propis números com a coordenades i; recíprocamente, per a qualsevol conjunt de punts en el pla, les coordenades i dels punts, ordenades per les seues coordenades x, formen una successió de números (a menos que dos dels punts tinguen iguals coordenades x). En esta relació entre successions i conjunts de punts, la teorema de Erdős-Szekeres es pot interpretar com que en qualsevol conjunt d'a lo manco $rs-r-s+2$ punts es pot trobar un camí poligonal d'o be $r-1$ arestes de pendent positiva o $s-1$ arestes de pendent negativa. En particular (prenent $r=s$), en qualsevol conjunt d'a lo manco n punts es pot trobar un camí poligonal d'a lo manco $\lfloor \sqrt{(}n-1)\rfloor$ arestes en pendents del mateix signe. Per eixemple, prenent $r=s=5$, qualsevol conjunt d'a lo manco 17 punts té un camí de quatre arestes en el que totes les pendents tenen el mateix signe.

Es pot formar un eixemple de $rs-r-s+1$ punts sense un camí d'este tipo, provant que este llímit és fix, aplicant una chicoteta rotació a una ret $(r-1)$ per $(s-1)$.

Interpretació en patrons de permutació

La teorema de Erdős-Szekeres també es pot interpretar en el llenguage dels patrons de permutació com que tota permutació de llongitut a lo manco rs + 1 deu contindre o be el patró 1, 2, 3, …, r + 1 o el patró s + 1, s, …, 2, 1.

Vore també

• Problema de la subsecuencia més llarga