4 votos

Conjuntos óptimos para el problema de coloreado de planos

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

Esto en realidad demuestra algo más fuerte, a saber, que hay un conjunto de k42+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)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) ? Más explícitamente, ¿existen conjuntos, de tamaño o(k4) 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?

2voto

JiminyCricket Puntos 143

Puedes conseguir O(k3) 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+x1)/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>k(k+x)(k+x1)/2 . En n=k(k+x)(k+x1)/(2x) el número total n(k+x) de puntos es k(k+x)2(k+x1)/(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 (32k)3+O(k2) .

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

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X