Una cota superior para poset Ramsey número $2n \le R(Q_n,Q_n) \le n^2+2n$

Question

Para cada entero $n,m \ge 1$

$2n \le R(Q_n,Q_n) \le n^2+2n$.

Aquí $Q_n$ denota un valor Booleano rejilla de la dimensión $n$ $R(P,P')$ o $R_{\dim_2}(P,P')$ es el más pequeño de $N$ de manera tal que cualquier rojo/azul para colorear de $Q_N$ contiene rojo de copiar o $P$ o un azul copia de $Q$. (Se llama un poset Ramsey número.)

Para el límite inferior en $R(Q_n,Q_n) $, $Q_n$ considera $Q_{2n-1}$. El Color de los conjuntos de tamaño $0, . . .,n-1$ rojo y todos los demás conjuntos de azul. A continuación, no es monocromática de la cadena de con $n+1$ elementos y no es monocromática copia de $Q_n$. es fácil comprender el límite inferior y estoy pegado a entender el límite superior.

¿Cómo encontrar una cota superior para $n^2+2n$? Cualquier ayuda será apreciada. Gracias.

Me encontré con este resultado en el papel de Maria Axenovich, Stefan Walzer: Boolean redes: Ramsey propiedades y las incrustaciones, https://arxiv.org/abs/1512.05565, http://dx.doi.org/10.1007/s11083-016-9399-7

La prueba dada en el papel es:

Para el límite superior en $R(Q_n,Q_n)$, considere la posibilidad de un rojo/azul para colorear de $Q_{n^2+2n}$. Deje que el suelo se $X_0\cup X_1 \cup \dots \cup X_{n+1}$ donde $X_i$'s son disjuntos a pares y de tamaño $n$ cada uno. Considerar a las familias de los conjuntos de $\mathcal B_Y$ por cada $Y\subseteq X_0$ $|Y|\ge1$ $\mathcal B_Y = \{Y\cup X_1\cup \dots \cup X_{|Y|} \cup X; X\subseteq X_{|Y|+1}\}$, deje $\mathcal B_{\emptyset}=2^{X_1}$. Vemos que cada una de las $\mathcal B_Y$ es una copia de $Q_n$. Si esta copia es de color azul, a continuación, $\mathcal B_Y$ da un monocromático copia de $Q_n$. De lo contrario, no es un elemento rojo en cada una de las $\mathcal B_Y$. Este elemento es $Z_Y=Y\cup X_1 \cup \dots X_{|Y|}\cup S_Y$ donde $S_Y\subseteq X_{|Y|+1}$. Pretendemos que estos elementos forman una red de copia de $Q_n$. De hecho, vamos a ver, por $Y, Y' \subseteq [n]$ que $Y\subseteq Y'$ fib $Z_Y\subseteq Z_{Y'}$.

Answer 1

No estoy seguro de lo mucho que esto va a ayudar, porque este es, precisamente, la prueba de esta versión del documento vinculado en la pregunta: acabo de agregar comentarios a algunos pasos. (Pero si nada, esto podría ayudar a identificar cuáles son los pasos que el OP no se entiende.)

Observe que en la versión publicados, los autores se omite esta parte, porque es una consecuencia de la más general $$n+m \le R(Q_n,Q_m) \le mn+n+m.$$

Para el límite superior en $R(Q_n,Q_n)$, considere la posibilidad de un rojo/azul para colorear de $Q_{n^2+2n}$.

Eso es precisamente lo que queremos hacer - para demostrar que la coloración de $Q_{n^2+2n}$ contiene rojo $Q_n$ o azul $Q_n$.

Deje que el suelo se $X_0\cup X_1 \cup \dots \cup X_{n+1}$ donde $X_i$'s son disjuntos a pares y de tamaño $n$ cada uno.

Ciertamente, podemos dividir el conjunto de con $n^2+n=n(n+1)$ elementos en $(n+1)$ conjuntos con $n$ elementos de cada uno.

Considerar a las familias de los conjuntos de $\mathcal B_Y$ por cada $Y\subseteq X_0$ $|Y|\ge1$ $$\mathcal B_Y = \{Y\cup X_1\cup \dots \cup X_{|Y|} \cup X; X\subseteq X_{|Y|+1}\},$$ deje $\mathcal B_{\emptyset}=2^{X_1}$.

Hemos definido $B_Y$ por cada $Y\subseteq X_0$.

Vemos que cada una de las $\mathcal B_Y$ es una copia de $Q_n$. Si esta copia es de color azul, a continuación, $\mathcal B_Y$ da un monocromático copia de $Q_n$.

De hecho, si queremos corregir algunos $Y\subseteq X_0$,entonces la única parte que cambia es $X$. Así que hemos monotono bijection $$Y\cup X_1\cup \dots \cup X_{|Y|} \cup X\mapsto X$$ entre el $B_Y$ y los conjuntos de $\mathcal P(X_{|Y|+1})$.

Así que esto es (orden)-isomorfo a $Q_n$.

De lo contrario, no es un elemento rojo en cada una de las $\mathcal B_Y$. Este elemento es $Z_Y=Y\cup X_1 \cup \dots X_{|Y|}\cup S_Y$ donde $S_Y\subseteq X_{|Y|+1}$.

Si ninguno de los conjuntos de $\mathcal B_Y$ es de color azul, al menos uno de los elementos en cada una de las $\mathcal B_Y$ es de color rojo. Elegimos ese elemento de $\mathcal B_Y$ y que se denota es $Z_Y$.

Pretendemos que estos elementos forman una red de copia de $Q_n$. De hecho, vamos a ver, por $Y, Y' \subseteq [n]$ que $Y\subseteq Y'$ fib $Z_Y\subseteq Z_{Y'}$.

Si lo anterior es cierto, entonces $$Y\mapsto Z_Y$$ es una orden isomorfismo entre el$\mathcal P(X_0)$$\{Z_Y; Y\in X_0\}$.

A ver que esto de los mapas, de hecho, conserva el orden, basta ver que si $Y\subseteq Y'$ entonces $|Y|<|Y'|$, en cuyo caso $$Z_Y = Y\cup X_1\cup \dots \cup X_{|Y|} \cup S_Y \subseteq Y\cup X_1\cup \dots \cup X_{|Y'|} \subseteq Z_{Y'}$$ o $|Y|=|Y'|$, lo que claramente implica $Y=Y'$$Z_Y=Z_{Y'}$.