una pregunta tipo Ramsey

Question

Esta pregunta está relacionada con este pero se siente más del tipo Ramsey, así que tal vez sea más fácil. Deja que $S$ sea un conjunto finito, $|S|=k$ . Supongamos que coloreamos todos los subconjuntos de $S$ en $1000$ colores. ¿Cuál es el máximo (en términos de $k$ ) longitud garantizada $l=l(k)$ de una secuencia monocromática de subconjuntos diferentes entre sí $A_1,A_2,..., A_l$ tal que $|A_i\setminus A_{i+1}|+|A_{i+1}\setminus A_i|\le 2$ por cada $i$ ? Claramente si $A$ es un subconjunto de $S$ tal que todos los subconjuntos de 2 elementos de $A$ son monocromáticos, entonces $l(n)\ge |A|-1$ (hay una secuencia de subconjuntos de 2 elementos de $A$ que satisface la propiedad anterior). Así que $l(k)$ es al menos tan grande como el número correspondiente de la teoría de Ramsey. ¿Es mucho más grande? El número 1000 es, por supuesto, "cualquier número fijo".

Actualización 1 Fedor y Tony mostraron a continuación que $l(k)\ge k/1000$ . Por lo tanto, sólo queda la primera pregunta: ¿Qué es $l(k)$ ? ¿Es exponencial en $k$ ¿ por ejemplo?

Actualización 2 Aunque la pregunta que he formulado tiene sentido (véase la actualización 1), me he dado cuenta de que no es la pregunta que quería hacer. Esta es la pregunta correcta. Los mismos supuestos: $|S|=k$ 1000 colores. Consideramos secuencias monocromáticas de subconjuntos pares diferentes ${\mathcal A}=A_1,A_2,...,A_l$ , donde $|A_i\setminus A_{i+1}|+|A_{i+1}\setminus A_i|\le 2$ . Para cada una de estas secuencias calculamos $\chi({\mathcal A})=|A_1\setminus A_l|+|A_l\setminus A_1|$ . Ahora la pregunta: ¿cuál es el máximo garantizado $\chi({\mathcal A})$ en términos de $k$ Llámalo $\chi(k)$ ? Por Ramsey, este número crece con $k$ . De hecho, si coloreamos sólo $s$ -de elementos, podremos (si $k\gg s$ ) para encontrar un subconjunto de tamaño $2s$ donde todos los subconjuntos de tamaño $s$ están coloreados con el mismo color; entonces podemos encontrar una secuencia monocromática de subconjuntos de tamaño $s$ con la propiedad anterior y $\chi=2s$ porque el primer y el último subconjunto de esa secuencia son disjuntos. La pregunta es cuál es la tasa de crecimiento de $\chi(k)$ . La pregunta está motivada por la respuesta de Justin Moore aquí.

Answer 1

Aquí hay una prueba de un límite superior muy débil para $l(k)$ . Considere la coloración de $2^S$ donde cada conjunto está coloreado por su tamaño (mod. 1000). Una buena secuencia monocomática debe estar formada por conjuntos del mismo tamaño. Así obtenemos $l(k) \leq \binom{k}{k/2}$ .

Sin embargo, podemos ser un poco más inteligentes. En lugar de colorear todo $i$ -subconjuntos de $S$ con el mismo color, podemos utilizar 333 colores y seguir garantizando que una buena secuencia monocromática debe utilizar conjuntos del mismo tamaño. Así, nos encontramos con el problema de los 333 colores $\binom{S}{i}$ para minimizar la longitud de una buena secuencia monocromática dentro de $\binom{S}{i}$ .

Answer 2

Seguro que es mucho más grande, aunque restrinjamos dos subconjuntos de cardinalidad 2 (llámalos aristas). Se necesita un camino monocromático de longitud $\ell$ . Tome el color con al menos $k(k-1)/2000$ bordes de este color, considere sólo ellos. Consideremos el camino máximo de nuestro grafo. Tiene una longitud máxima de $l-1$ . Por lo tanto, su punto final (ambos) tiene grado como máximo $l-1$ . Elimínalo y repite (o utiliza la inducción). Obtenemos que nuestro gráfico tiene como máximo $(l-1)k$ bordes. Así que, $k(k-1)/2000\leq (l-1)k$ , $l\geq (k-1)/2000+1$ .