8
$\begingroup$

For each integer $n,m \ge 1$

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

Here $Q_n$ denotes a Boolean lattice of dimension $n$ and $R(P,P')$ or $R_{\dim_2}(P,P')$ is the smallest $N$ such that any red/blue coloring of $Q_N$ contains either red copy or $P$ or a blue copy of $Q$. (It is called a poset Ramsey number.)

For the lower bound on $R(Q_n,Q_n) $, with $Q_n$ consider $Q_{2n-1}$. Color the sets of size $0, . . .,n-1$ red and all other sets blue. Then there is no monochromatic chain with $n+1$ elements and there is no monochromatic copy of $Q_n$. it's easy to understand the lower bound and I am stuck to understand the upper bound.

How do you find an upper bound for $n^2+2n$? Any help will be appreciated. Thanks.

I found this result in the paper Maria Axenovich, Stefan Walzer: Boolean lattices: Ramsey properties and embeddings, https://arxiv.org/abs/1512.05565, http://dx.doi.org/10.1007/s11083-016-9399-7

The proof given in the paper is:

For the upper bound on $R(Q_n,Q_n)$, consider a red/blue coloring of $Q_{n^2+2n}$. Let the ground set be $X_0\cup X_1 \cup \dots \cup X_{n+1}$, where $X_i$'s s are pairwise disjoint and of size $n$ each. Consider families of sets $\mathcal B_Y$ for each $Y\subseteq X_0$ with $|Y|\ge1$ to be $\mathcal B_Y = \{Y\cup X_1\cup \dots \cup X_{|Y|} \cup X; X\subseteq X_{|Y|+1}\}$, let $\mathcal B_{\emptyset}=2^{X_1}$. We see that each $\mathcal B_Y$ is a copy of $Q_n$. If this copy is blue, then $\mathcal B_Y$ gives a monochromatic copy of $Q_n$. Otherwise, there is a red element in each $\mathcal B_Y$. This element is $Z_Y=Y\cup X_1 \cup \dots X_{|Y|}\cup S_Y$, where $S_Y\subseteq X_{|Y|+1}$. We claim that these elements form a red copy of $Q_n$. Indeed, we see for $Y, Y' \subseteq [n]$ that $Y\subseteq Y'$ iff $Z_Y\subseteq Z_{Y'}$.

$\endgroup$
6
  • $\begingroup$ You should probably add what $Q_n$ is. And perhaps also where the inequality is from. (Is it just your conjecture? Is it exercise from some book?) $\endgroup$ – Martin Sleziak Oct 20 '16 at 14:22
  • 1
    $\begingroup$ Simply trying Google lead me to a paper saying that: "...it is a long-standing conjecture of Burr and Erdos that $r(Q_n,Q_n) = O(2^n)$, but the best known bounds (see [10, 17]) are roughly the square of this function." $\endgroup$ – Martin Sleziak Oct 20 '16 at 14:27
  • $\begingroup$ @MartinSleziak I read a paper and i can not understand for the upper bound of this inequality. $Q_n$ is a Boolean lattice of dimension $n$ $\endgroup$ – Verse Oct 21 '16 at 1:41
  • $\begingroup$ Adding an exact reference and link to the paper would be useful, tooo. $\endgroup$ – Martin Sleziak Oct 21 '16 at 2:12
  • 1
    $\begingroup$ Is it the paper Boolean lattices: Ramsey properties and embeddings? arxiv.org/abs/1512.05565 math.kit.edu/iag6/~axenovich/media/poset-15-11-15.pdf dx.doi.org/10.1007/s11083-016-9399-7 $\endgroup$ – Martin Sleziak Oct 21 '16 at 2:14
2
$\begingroup$

I am not sure how much this is going to help - since this is precisely the proof from this version of the paper linked in the question; I have just added comments to some steps. (But if nothing else, this might help to identify what are the steps which the OP does not understand.)

Notice that in the version actually published, the authors omitted this part, because it is a consequence of more general $$n+m \le R(Q_n,Q_m) \le mn+n+m.$$

For the upper bound on $R(Q_n,Q_n)$, consider a red/blue coloring of $Q_{n^2+2n}$.

That's precisely what we want to do - to show that such coloring of $Q_{n^2+2n}$ contains either red $Q_n$ or blue $Q_n$.

Let the ground set be $X_0\cup X_1 \cup \dots \cup X_{n+1}$, where $X_i$'s s are pairwise disjoint and of size $n$ each.

Certainly, we can divide the set with $n^2+n=n(n+1)$ elements into $(n+1)$ sets with $n$ elements each.

Consider families of sets $\mathcal B_Y$ for each $Y\subseteq X_0$ with $|Y|\ge1$ to be $$\mathcal B_Y = \{Y\cup X_1\cup \dots \cup X_{|Y|} \cup X; X\subseteq X_{|Y|+1}\},$$ let $\mathcal B_{\emptyset}=2^{X_1}$.

We have defined $B_Y$ for each $Y\subseteq X_0$.

We see that each $\mathcal B_Y$ is a copy of $Q_n$. If this copy is blue, then $\mathcal B_Y$ gives a monochromatic copy of $Q_n$.

Indeed, if we fix some $Y\subseteq X_0$,then the only part which changes is $X$. So we have monotone bijection $$Y\cup X_1\cup \dots \cup X_{|Y|} \cup X\mapsto X$$ between $B_Y$ and the sets from $\mathcal P(X_{|Y|+1})$.

So this is (order)-isomorphic to $Q_n$.

Otherwise, there is a red element in each $\mathcal B_Y$. This element is $Z_Y=Y\cup X_1 \cup \dots X_{|Y|}\cup S_Y$, where $S_Y\subseteq X_{|Y|+1}$.

If neither of the sets $\mathcal B_Y$ is blue, at least one element in each $\mathcal B_Y$ is colored red. We chose such element from $\mathcal B_Y$ and denoted it $Z_Y$.

We claim that these elements form a red copy of $Q_n$. Indeed, we see for $Y, Y' \subseteq [n]$ that $Y\subseteq Y'$ iff $Z_Y\subseteq Z_{Y'}$.

If the above is true then $$Y\mapsto Z_Y$$ is an order isomorphism between $\mathcal P(X_0)$ and $\{Z_Y; Y\in X_0\}$.

To see that this maps indeed preserves order, it suffices to see that if $Y\subseteq Y'$ then either $|Y|<|Y'|$ in which case $$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'}$$ or $|Y|=|Y'|$, which clearly implies $Y=Y'$ and $Z_Y=Z_{Y'}$.

$\endgroup$
4
  • $\begingroup$ Thank you, it's very helpful. but the paper did not mention the proof of the $$n+m \le R(Q_n,Q_m) \le mn+n+m.$$ $\endgroup$ – Verse Oct 24 '16 at 1:35
  • $\begingroup$ why do we divide the set with $n^2+n=n(n+1)$ elements into $(n+1)$ sets with $n$ elements each ? $\endgroup$ – Verse Oct 24 '16 at 2:45
  • 1
    $\begingroup$ About your first comment: If you have a look into the version of the paper which was actually published (assuming you have access to it), the claim about $R(Q_n,Q_n)$ is omitted in Theorem 1 and it contains the above inequality instead. (Which is proved in the paper, however I did not look at the details of the proof.) $\endgroup$ – Martin Sleziak Oct 24 '16 at 8:08
  • 1
    $\begingroup$ In your second comment you ask why the authors started the proof in this way. Short answer is: because it works. I do not have sufficient insight into this area to be able what might be a reasonable proof strategy for some result. Maybe for somebody who has seen several proofs of this type, it is almost immediate that this is a reasonable start. $\endgroup$ – Martin Sleziak Oct 24 '16 at 8:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.