6 votos

Teoría de Ramsey, colorantes finitos de $\mathbb{N}$ e infinitos conjuntos monocromáticos

Estoy tratando de mostrar que la siguiente afirmación es falsa: cuando $\mathbb{N}$ es finitely de color por $c: \mathbb{N} \to \{1,\ldots,k\}$ (en el sentido de la teoría de Ramsey), existe un conjunto infinito $x_1 <x_2 <x_3 \ldots$ de manera tal que el conjunto $\{x_i+2x_j: i \neq j\}$ es monocromática. Es bastante fácil demostrar que esta afirmación es verdadera para el conjunto $\{x_i+2x_j: i < j\}$, por lo que me da la impresión de que cualquier intento de probar que se celebran $\{x_i+2x_j: i \neq j\}$ podría fallar debido a $x_i + 2x_j$ $x_j + 2x_i$ puede tener diferentes colores, o algo a lo largo de esas líneas.

Así, traté de encontrar una coloración $c$ para las que no hay tales monocromática conjunto, pero no estoy teniendo suerte hasta ahora por intentar elegir un colorante para que $c(x_i + 2x_j) \neq c(x_j + 2x_i)$. El más cercano lo tengo es por la elección de $c(z)$ a la paridad de la potencia más grande de $2$ que se divide $z$: por ejemplo, tenemos en color $1$ "INCLUSO", 2 "EXTRAÑO", 4, 6 IMPAR, 17. Este hecho da $x_i + 2x_j$ $x_j + 2x_i$ diferentes colores, a menos que las potencias de 2 que divide ellos son en la mayoría de uno aparte; por ejemplo, $x_i=2^ap,\,x_j = 2^aq$ o $x_j = 2^{a \pm 1}q$ $p,\,q$ impar. En el primer caso, esto le da el mismo color, y en el último caso, necesariamente no puede decir lo que el color es porque termina tratando de contar la potencia de 2 dividiendo $2^{a+1}(p+q)$, e $p+q$ es algún número par.

No estoy seguro de a donde voy equivocado: lo que yo estoy tratando de hacer es producir una coloración tal que para cualquier $x_i$ $x_j$ en nuestra serie, $x_i + 2x_j$ $x_j + 2x_i$ son de diferente color. En el hecho de que sólo realmente necesitan encontrar 2 elementos que son de diferente color, no necesariamente cada par, así que tal vez mi intento de probar que esto es una exageración. Por ejemplo, traté de seguir mi por encima de la coloración, suponiendo que todas las $x_i$ son de la forma $2^a s$ o $2^{a+1}t$ por extraño $s,\,t$ pero no fue capaz de derivar una contradicción. Creo que podría estar buscando en el lugar equivocado coloración - podría alguien por favor sugerir cómo probar que la afirmación es falsa? Muchas gracias por tu ayuda.

3voto

John Fouhy Puntos 759

Deje $h(n)$ ser la mayor potencia de dos que aparecen en el binario de expansión de $n > 0$, y deje $c(n)$ ser la paridad de $h(n)$.

Supongamos $h(x) = n$$h(y) \leq n-1$. Tenga en cuenta que$h(x+2y) \in \{n,n+1\}$$h(2x+y) \in \{n+1,n+2\}$. Con más precisión, $h(x+2y) = n$ fib $x+2y < 2^{n+1}$, e $h(2x+y) = n+1$ fib $2x+y < 2^{n+2}$. Esto demuestra que $h(x+2y) = n$ implica $h(2x+y) = n+1$, y en este caso, $c(x+2y) \neq c(2x+y)$. La única manera en que podemos tener $c(x+2y) = c(2x+y)$ es al $h(x+2y) = h(2x+y) = n+1$. En este caso $$ 2^{n+2}-4y \leq 2x < 2^{n+2}-y. $$ En particular, si $h(y),h(z) < h(x)$ y el tanto $c(x+2y) = c(2x+y)$$c(x+2z) = c(2x+z)$, debemos tener $y \leq 4z$$z \leq 4y$. Esto implica $|h(y)-h(z)| \leq 2$.

Ahora suponga que tiene un conjunto infinito $A$ tal que $c(x+2y) = c(2x+y)$ todos los $x,y \in A$. Recoger algunas $y \in A$. Desde $A$ es infinito, hay algunos $z \in A$ tal que $|h(y)-h(z)| > 2$. De nuevo desde $A$ es infinito, hay algunos $x \in A$ tal que $h(x) > \max(h(y),h(z))$. Hemos llegado a una contradicción.

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