Conjuntos óptimos para el problema de coloreado de planos

Question

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, \ldots, k\} \times \{0, \ldots, \frac{k^2(k+1)}{2}\}$ . De cada fila $\{0, \ldots, k\} \times \{j\}$ elige un par $(a_j, j), (b_j,j)$ con $a_j<b_j$ de puntos que son del mismo color, que debe existir por encasillamiento. Puesto que sólo hay $\frac{k(k+1)}{2}$ posibles opciones para $(a_j,b_j)$ para algún par $(a,b)$ hay al menos $k+1$ valores de $j$ tal que $(a,b)=(a_j,b_j)$ . Dado que existen $k$ colores, algún par $(j_1,j_2)$ de valores distintos de $j$ entre ellos han $(a,j_1)$ y $(a,j_2)$ del mismo color, y el rectángulo deseado tiene el conjunto de vértices $\{a,b\} \times \{j_1, j_2\}$ .

Esto en realidad demuestra algo más fuerte, a saber, que hay un conjunto de $\frac{k^4}{2}+k^3+\frac{k^2}{2}+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 $\frac{k^2(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(k^4)$ ? Más explícitamente, ¿existen conjuntos, de tamaño $o(k^4)$ tal que para cualquier coloración del plano con $k$ colores, el $k$ -¿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?

Answer 1

Puedes conseguir $O(k^3)$ con el mismo método utilizando más de $k+1$ puntos por fila. Una fila de $k+x$ puntos deben contener al menos $x$ pares de colores idénticos, por lo que $n$ dichas filas contienen $nx$ estos pares. En filas de $k+x$ puntos, hay $(k+x)(k+x-1)/2$ diferentes posiciones de pareja, y cada una puede colorearse con $k$ colores. Por lo tanto, se garantiza que dos pares en la misma posición tienen los mismos colores si $nx\gt k(k+x)(k+x-1)/2$ . En $n=k(k+x)(k+x-1)/(2x)$ el número total $n(k+x)$ de puntos es $k(k+x)^2(k+x-1)/(2x)$ y minimizarlo con respecto a $x$ para grandes $k$ produce $x=k/2+O(1)$ por lo que el número mínimo de puntos necesarios es $\left(\frac32k\right)^3+O(k^2)$ .

Sospecho que será difícil hacerlo mucho mejor, pero no sé cómo demostrarlo.