Existe un problema razonablemente conocido:
Dado un plano con cada punto coloreado de uno de k colores, demuestre que existe un rectángulo cuyos vértices son todos del mismo color, cuyos ejes son paralelos a los ejes x e y
Una solución a este problema es considerar puntos en {0,1,…,k}×{0,…,k2(k+1)2}{0,1,…,k}×{0,…,k2(k+1)2} . De cada fila {0,…,k}×{j}{0,…,k}×{j} elige un par (aj,j),(bj,j)(aj,j),(bj,j) con aj<bjaj<bj de puntos que son del mismo color, que debe existir por encasillamiento. Puesto que sólo hay k(k+1)2k(k+1)2 posibles opciones para (aj,bj)(aj,bj) para algún par (a,b)(a,b) hay al menos k+1k+1 valores de jj tal que (a,b)=(aj,bj)(a,b)=(aj,bj) . Dado que existen kk colores, algún par (j1,j2)(j1,j2) de valores distintos de jj entre ellos han (a,j1)(a,j1) y (a,j2)(a,j2) del mismo color, y el rectángulo deseado tiene el conjunto de vértices {a,b}×{j1,j2}{a,b}×{j1,j2} .
Esto en realidad demuestra algo más fuerte, a saber, que hay un conjunto de k42+k3+k22+k+1k42+k3+k22+k+1 puntos que deben contener vértices de un rectángulo, orientados con los ejes de coordenadas, que son todos del mismo color. También está bastante claro que el k2(k+1)2k2(k+1)2 no se puede mejorar con este método.
Por otro lado, el método parece ineficiente, al menos para k grandes. Así que mi pregunta es: ¿Se puede hacer algo mejor que O(k4)O(k4) ? Más explícitamente, ¿existen conjuntos, de tamaño o(k4)o(k4) tal que para cualquier coloración del plano con kk colores, el kk -¿el enésimo de estos conjuntos debe contener los vértices, todos del mismo color, de un rectángulo cuyos lados sean paralelos a los ejes de coordenadas? En caso afirmativo, ¿cuál es el mejor número (conocido) de puntos?