# Poset Ramsey numbers: large Boolean lattice versus a fixed poset

Maria Axenovich Karlsruhe Institute of Technology, Karlsruhe, Germany
Christian Winter Karlsruhe Institute of Technology, E-mail:
<EMAIL_ADDRESS>
###### Abstract

Given partially ordered sets (posets) $(P,\leq_{P})$ and
$(P^{\prime},\leq_{P^{\prime}})$, we say that $P^{\prime}$ contains a copy of
$P$ if for some injective function $f:P\rightarrow P^{\prime}$ and for any
$X,Y\in P$, $X\leq_{P}Y$ if and only of $f(X)\leq_{P^{\prime}}f(Y)$. For any
posets $P$ and $Q$, the poset Ramsey number $R(P,Q)$ is the least positive
integer $N$ such that no matter how the elements of an $N$-dimensional Boolean
lattice are colored in blue and red, there is either a copy of $P$ with all
blue elements or a copy of $Q$ with all red elements. We focus on a poset
Ramsey number $R(P,Q_{n})$ for a fixed poset $P$ and an $n$-dimensional
Boolean lattice $Q_{n}$, as $n$ grows large. We show a sharp jump in behaviour
of this number as a function of $n$ depending on whether or not $P$ contains a
copy of either a poset $V$, i.e. a poset on elements $A,B,C$ such that $B>C$,
$A>C$, and $A$ and $B$ incomparable, or a poset $\Lambda$, its symmetric
counterpart. Specifically, we prove that if $P$ contains a copy of $V$ or
$\Lambda$ then $R(P,Q_{n})\geq n+\frac{1}{15}\frac{n}{\log n}$. Otherwise
$R(P,Q_{n})\leq n+c(P)$ for a constant $c(P)$. This gives the first non-
marginal improvement of a lower bound on poset Ramsey numbers and as a
consequence gives $R(Q_{2},Q_{n})=n+\Theta(\frac{n}{\log n})$.

##  1 Introduction

A partially ordered set, shortly a poset, is a set $P$ equipped with a
relation $\leq_{P}$ that is transitive, reflexive, and antisymmetric. For any
non-empty set $\mathcal{X}$, let $\mathcal{Q}(\mathcal{X})$ be the Boolean
lattice of dimension $|\mathcal{X}|$ on a ground set $\mathcal{X}$, i.e. the
poset consisting of all subsets of $\mathcal{X}$ equipped with the inclusion
relation, $\subseteq$. We use $Q_{n}$ to denote a Boolean lattice with an
arbitrary $n$-element ground set. We refer to a poset either as a pair
$(P,\leq_{P})$, or, when it is clear from context, simply as a set $P$. The
elements of $P$ are often called vertices.

For two posets $(P_{1},\leq_{P_{1}})$ and $(P_{2},\leq_{P_{2}})$, an embedding
$\phi\colon P_{1}\to P_{2}$ of $P_{1}$ into $P_{2}$ is an injective function
such that for every $X_{1},X_{2}\in P_{1}$,

$X_{1}\leq_{P_{1}}X_{2}\text{ if and only if
}\phi(X_{1})\leq_{P_{2}}\phi(X_{2}).$

A poset $P_{1}$ is an induced subposet of $P_{2}$ if $P_{1}\subseteq P_{2}$
and for every $X_{1},X_{2}\in P_{1}$, $X_{1}\leq_{P_{1}}X_{2}$ if and only if
$X_{1}\leq_{P_{2}}X_{2}.$ An copy of a poset $P_{1}$ in $P_{2}$ is an induced
subposet $P^{\prime}$ of $P_{2}$, isomorphic to $P_{1}$.

Extremal properties of posets and their induced subposets have been
investigated in recent years and mirror similar concepts in graphs. Carroll
and Katona [3] initiated the consideration of so called Turán-type problems
for induced subposets. Most notable is a result by Methuku and Pálvölgyi [13]
which provides an asymptotically tight bound on the maximum size of a subposet
of a Boolean lattice that does not have a copy of a fixed poset $P$, for
general $P$. Their statement has been refined for several special cases, see
e.g. Lu and Milans [10] and Méroueh [12]. Further Turán-type results are, for
example, given by Methuku and Tompkins [14] and Tomon [15]. Note that Turán-
type properties are also investigated in depth for non-induced, so called weak
subposets, which are not considered here. Besides that, saturation-type
extremal problems are studied for induced and weak subposets, see a recent
survey of Keszegh, et al. [9].

In this paper we are dealing with Ramsey-type properties of induced subposets
in Boolean lattices. Consider an assignment of two colors, blue and red, to
the vertices of posets. Such a coloring $c:P\rightarrow\\{blue,red\\}$ is a
blue/red coloring of $P$. A colored poset is monochromatic if all of its
vertices share the same color. A monochromatic poset whose vertices are blue
is called a blue poset. Similarly defined is a red poset. Extending the
classical definition of graph Ramsey numbers, Axenovich and Walzer [1]
introduced the poset Ramsey number which is defined as follows. For posets $P$
and $Q$, let

$R(P,Q)=\min\\{N\in\mathbb{N}\colon\text{ every blue/red coloring of $Q_{N}$
contains either}\\\ \text{a blue copy of $P$ or a red copy of $Q$}\\}.$

One of the central questions in this area is to determine $R(Q_{n},Q_{n})$.
The best bounds currently known are $2n+1\leq R(Q_{n},Q_{n})\leq n^{2}-n+2$,
see listed chronologically Walzer [16], Axenovich and Walzer [1], Cox and
Stolee [7], Lu and Thompson [11], Bohman and Peng [2]. For off-diagonal
setting $R(Q_{k},Q_{n})$ with $k$ fixed and $n$ large, an exact result is only
known if $k=1$. It is easy to see that $R(Q_{1},Q_{n})=n+1$. For $k=2$, it was
shown in [1] that $R(Q_{2},Q_{n})\leq 2n+2$. This was improved by Lu and
Thompson to $R(Q_{2},Q_{n})\leq(5/3)n+2$. Finally, it was further improved by
Grósz, Methuku, and Tompkins [8]:

######  Theorem 1 (Grósz et al. [8]).

Let $\epsilon>0$ and let $n\in\mathbb{N}$ be sufficiently large. Then

$n+3\leq R(Q_{2},Q_{n})\leq n+\frac{(2+\epsilon)n}{\log n}.$

Further known bounds on poset Ramsey numbers include results of Chen et al.
[5], [6] as well as Chang et al. [4].

In this paper, we start a more systematic investigation of $R(P,Q_{n})$ for a
fixed poset $P$ and large $n$. This Ramsey number gives an analogue of the
graph Ramsey number $R(H,K_{n})$ that claims that every edge-coloring of a
complete graph in red and blue with no given induced blue subgraph $H$,
contains a large red clique of size $n$. Here, the goal is to provide a
quantitative version of a statement that every blue/red coloring of a Boolean
lattice with no blue (induced) subposet $P$ contains a large red Boolean
sublattice. One of the key roles here plays a small, three-vertex poset
$\Lambda=(\Lambda,<)$, with vertices $Z_{1},Z_{2}$ and $Z_{3}$, such that
$Z_{1}<Z_{3}$, $Z_{2}<Z_{3}$, and $Z_{1}$ and $Z_{2}$ incomparable. A poset
$V$ is the symmetric counterpart of $\Lambda$, having vertices $Z_{1},Z_{2}$
and $Z_{3}$, such that $Z_{1}>Z_{3}$, $Z_{2}>Z_{3}$, and $Z_{1}$ and $Z_{2}$
not comparable.

Our main result shows a sharp jump in the behaviour of $R(P,Q_{n})$ as a
function of $n$ depending whether or not $P$ contains a copy $\Lambda$ or $V$.

######  Theorem 2.

For every poset $P$ there is an integer $n_{0}$ such that for any $n>n_{0}$
the following holds. If $P$ contains a copy of $\Lambda$ or $V$, then
$R(P,Q_{n})\geq n+\frac{1}{15}\frac{n}{\log n}$. If $P$ contains neither a
copy of $\Lambda$ nor a copy of $V$, then $R(P,Q_{n})\leq n+f(P)$, for some
function $f$.

In order to show the lower bound, we prove a structural duality statement that
together with a probabilistic construction allows to find a desired coloring.
This is the first of a kind non-marginal improvement of a trivial lower bound
for poset Ramsey numbers. Most other known lower bounds corresponded to so-
called layered colorings of Boolean lattices, where any two vertices of the
same size have the same color. The only two constructions different from this
and known so far are the aforementioned lower bound of Grósz et al. [8] as
well as a construction of Bohman and Peng [2] improving the trivial lower
bound for the diagonal case $R(Q_{n},Q_{n})\geq 2n$ to $2n+1$.

We show the following bounds on the poset Ramsey number of $\Lambda$ versus
$Q_{n}$.

######  Theorem 3.

Let $\epsilon>0$. There exists an $n_{0}\in\mathbb{N}$ such that for all
$n\geq n_{0}$,

$n+\frac{1}{15}\cdot\frac{n}{\log n}\leq R(\Lambda,Q_{n})\leq
n+\big{(}1+\epsilon)\cdot\frac{n}{\log n}.$

More precisely, it can be seen that the lower bound holds for $\log n_{0}\geq
535$, while the upper bound requires $\log n_{0}\geq\frac{36}{\epsilon^{2}}$.
Note that $R(\Lambda,Q_{n})\leq R(Q_{2},Q_{n})$, so Theorem 1 already implies
a bound for $R(\Lambda,Q_{n})$ which is weaker but asymptotically equal to the
upper bound of Theorem 3. In this paper we provide a duality statement that
allows us to prove both the lower and the improved upper bound on
$R(\Lambda,Q_{n})$. Theorem 1 and Theorem 2 also give a lower bound for
$R(Q_{2},Q_{n})$ which is asymptotically tight not only in the first but also
in the second summand.

######  Corollary 4.

$R(Q_{2},Q_{n})=n+\Theta\left(\frac{n}{\log(n)}\right).$

The structure of the paper is as follows. In Section 2 we introduce some
notations and a new type of poset and show some useful propositions. In
Section 2.4 we provide an alternative proof of the upper bound in Theorem 1.
This makes our paper self-contained since we need this result for Corollary 4.
In Section 3 we provide a structural duality statement, Theorem 12, which is
the key tool for the main proofs. In Section 4 we use a probabilistic
construction to find a coloring with “good” properties. Lastly, in Section 5
we complete the proofs of Theorem 3 and Theorem 2.

##  2 Preliminaries

###  2.1 Basic Notation

Let $\mathcal{X}$ and $\mathcal{Y}$ be disjoint sets. Then the vertices of the
Boolean lattice $\mathcal{Q}(\mathcal{X}\cup\mathcal{Y})$, i.e. the unordered
subsets of $\mathcal{X}\cup\mathcal{Y}$, can be partitioned with respect to
$\mathcal{X}$ and $\mathcal{Y}$ in the following manner. Every
$Z\subseteq\mathcal{X}\cup\mathcal{Y}$ has an $\mathcal{X}$-part
$X_{Z}=Z\cap\mathcal{X}$ and a $\mathcal{Y}$-part $Y_{Z}=Z\cap\mathcal{Y}$. In
this setting, we refer to $Z$ alternatively as the pair $(X_{Z},Y_{Z})$.
Conversely, for all $X\subseteq\mathcal{X}$, $Y\subseteq\mathcal{Y}$, the pair
$(X,Y)$ has a $1$-to-$1$ correspondence to the vertex $X\cup
Y\in\mathcal{Q}(\mathcal{X}\cup\mathcal{Y})$. One can think of such pairs as
elements of the Cartesian product $2^{\mathcal{X}}\times 2^{\mathcal{Y}}$
which has a canonic bijection to
$2^{\mathcal{X}\cup\mathcal{Y}}=\mathcal{Q}(\mathcal{X}\cup\mathcal{Y})$.
Observe that for $X_{i}\subseteq\mathcal{X},Y_{i}\subseteq\mathcal{Y}$,
$i\in[2]$, we have $(X_{1},Y_{1})\subseteq(X_{2},Y_{2})$ if and only if
$X_{1}\subseteq X_{2}$ and $Y_{1}\subseteq Y_{2}$. We omit floors and ceilings
where appropriate.

For any poset, we refer to vertices $Z_{1},Z_{2}$ which are incomparable as
$Z_{1}\nsim Z_{2}$. For a positive integer $n\in\mathbb{N}$, we use $[n]$ to
denote the set $\\{1,\dots,n\\}$. Given an integer $n\in\mathbb{N}$ and a set
$\mathcal{X}$, let $\binom{\mathcal{X}}{n}$ be the set of all $n$-element
subsets of $\mathcal{X}$. Throughout the paper, ‘$\log$’ always refers to the
logarithm with base $2$, while ‘$\ln$’ refers to the natural logarithm.

###  2.2 Structure of posets with forbidden $\Lambda$ or $V$

A poset $\mathcal{T}$ is an up-tree if there is a unique minimal vertex in
$\mathcal{T}$ and for every vertex $X\in\mathcal{T}$, the set
$\\{Y\in\mathcal{T}\colon Y\leq X\\}$ is a chain, i.e., its vertices are
pairwise comparable. We say that two posets are independent if they are
vertexwise incomparable. Furthermore, a collection of posets is independent if
they are pairwise independent.

We use this notation to describe posets which don’t contain a copy of
$\Lambda$ (or $V$).

######  Lemma 5.

Let $P$ be a poset. There is no copy of $\Lambda$ in $P$ if and only if $P$ is
an independent collection of up-trees.

###### Proof.

Observe that a poset $P$ is an independent collection of up-trees if and only
if for every vertex $X\in P$, $\\{Y\in P\colon Y\leq X\\}$ forms a chain.

Suppose that there is a copy of $\Lambda$ in $P$ on vertices $Z_{i}$,
$i\in[3]$ with $Z_{1}<Z_{3}$, $Z_{2}<Z_{3}$ and $Z_{1}\nsim Z_{2}$. Then
$Z_{1},Z_{2}$ witness that $\\{Y\in P\colon Y<Z_{3}\\}$ is not a chain, so $P$
is not an independent collection of up-trees.

Now assume that $P$ is not an independent collection of up-trees. Then there
exist some $X\in P$ and $Z_{1},Z_{2}\in\\{Y\in P\colon Y\leq X\\}$ such that
$Z_{1}\nsim Z_{2}$. Since $X$ is comparable to all vertices in $\\{Y\in
P\colon Y\leq X\\}$, $X>Z_{1},X>Z_{2}$. Now $X,Z_{1},Z_{2}$ form a copy of
$\Lambda$. ∎

By symmetry an analogous statement holds for posets with forbidden induced
copy of $V$. If we forbid both $V$ and $\Lambda$ simultaneously we obtain the
following structure.

######  Corollary 6.

Let $P$ be a poset such that there is neither a copy of $V$ nor of $\Lambda$.
Then $P$ is an independent collection of chains.

###  2.3 Embeddings of $Q_{n}$

When considering an embedding $\phi$ of a Boolean lattice $Q_{n}$ into a
larger Boolean lattice $\mathcal{Q}(\mathcal{Z})$, we can partition
$\mathcal{Z}$ such that it has the following nice property.

######  Lemma 7.

Let $n\in\mathbb{N}$. Let $\mathcal{Z}$ be a set with $|\mathcal{Z}|>n$ and
let $Q=\mathcal{Q}(\mathcal{Z})$. If there is an embedding $\phi\colon
Q_{n}\to Q$, then there exist a subset $\mathcal{X}\subset\mathcal{Z}$ with
$|\mathcal{X}|=n$, and an embedding
$\phi^{\prime}\colon\mathcal{Q}(\mathcal{X})\to Q$ such that
$\phi^{\prime}(X)\cap\mathcal{X}=X$ for all $X\subseteq\mathcal{X}$.

###### Proof.

Let the ground set of $Q_{n}$ be $\mathcal{X}^{\prime}$. We consider the
embedding of singletons of $Q_{n}$, i.e. $\phi(\\{a\\})$,
$a\in\mathcal{X}^{\prime}$. If
$\phi(\\{a\\})\subseteq\bigcup_{X^{\prime}\subseteq\mathcal{X}^{\prime}\backslash\\{a\\}}\phi(X^{\prime})$,
then
$\phi(\\{a\\})\subseteq\bigcup_{X^{\prime}\subseteq\mathcal{X}^{\prime}\backslash\\{a\\}}\phi(X^{\prime})\subseteq\phi(\mathcal{X}^{\prime}\backslash\\{a\\})$.
But $\\{a\\}\nsubseteq\mathcal{X}^{\prime}\backslash\\{a\\}$ and $\phi$ is an
embedding, a contradiction. Thus
$\phi(\\{a\\})\not\subseteq\bigcup_{X^{\prime}\subseteq\mathcal{X}^{\prime}\backslash\\{a\\}}\phi(X^{\prime})$.
For every $a\in\mathcal{X}^{\prime}$, pick an arbitrary

$b(a)\in\phi(\\{a\\})\backslash\bigcup_{X^{\prime}\subseteq\mathcal{X}^{\prime}\backslash\\{a\\}}\phi(X^{\prime}).$

Note that $b(a_{1})\notin\phi(\\{a_{2}\\})$ for any
$a_{1},a_{2}\in\mathcal{X}^{\prime}$, $a_{1}\neq a_{2}$, so all
representatives are distinct. Let $\mathcal{X}=\\{b(a)\colon
a\in\mathcal{X}^{\prime}\\}$. We see that the map
$b:\mathcal{X}^{\prime}\to\mathcal{X}$ is a bijection. For every
$B\subseteq\mathcal{X}$, let $A_{B}\subseteq\mathcal{X}^{\prime}$ be such that
$B=\\{b(a):a\in A_{B}\\}$. We define
$\phi^{\prime}\colon\mathcal{Q}(\mathcal{X})\to Q$ as follows:
$\phi^{\prime}(B)=\phi(A_{B})$, $B\in\mathcal{X}$. Then $\phi^{\prime}$ is an
embedding. Observe that for $X\subseteq\mathcal{X}$ and $b\in\mathcal{X}$,
$b\in\phi^{\prime}(X)$ if and only if $b\in X$. Thus
$\phi^{\prime}(X)\cap\mathcal{X}=X$ for all $X\subseteq\mathcal{X}$. This
concludes the proof. ∎

We call an embedding $\phi$ of $\mathcal{Q}(\mathcal{X})$ into
$\mathcal{Q}(\mathcal{X}\cup\mathcal{Y})$ for disjoint $\mathcal{X}$ and
$\mathcal{Y}$, $\mathcal{X}$-good if $\phi(X)\cap\mathcal{X}=X$ for all
$X\in\mathcal{X}$. We also call a copy $Q$ of $\mathcal{Q}(\mathcal{X})$ in
$\mathcal{Q}(\mathcal{X}\cup\mathcal{Y})$ $\mathcal{X}$-good if there is an
$\mathcal{X}$-good embedding of $\mathcal{Q}(\mathcal{X})$ into
$\mathcal{Q}(\mathcal{X}\cup\mathcal{Y})$.

Lemma 7 claims in particular that for any copy of $Q_{n}$ in a larger Boolean
lattice $Q$, there is a subset $\mathcal{X}$ of the ground set of $Q$ with
$|\mathcal{X}|=n$ such that there is an $\mathcal{X}$-good copy of
$\mathcal{Q}(\mathcal{X})$ in $Q$.

###  2.4 Red copy of $Q_{n}$ vs. blue chain

The main goal of this subsection is to present an alternative proof for the
upper bound of Theorem 1. Grósz, Methuku, and Tompkins [8] stated the
following lemma using a different formulation. While they used algorithmic
tools in their proof, we prove the statement recursively. Recall that for a
given partition $\mathcal{X}\cup\mathcal{Y}$ of the ground set of a Boolean
lattice we denote a vertex $X\cup
Y\in\mathcal{Q}(\mathcal{X}\cup\mathcal{Y})$, where
$X\subseteq\mathcal{X},Y\subseteq\mathcal{Y}$, as $(X,Y)$.

######  Lemma 8.

Let $\mathcal{X}$, $\mathcal{Y}$ be disjoint sets with $|\mathcal{X}|=n$ and
$|\mathcal{Y}|=k$, for some $n,k\in\mathbb{N}$. Let
$Q=\mathcal{Q}(\mathcal{X}\cup\mathcal{Y})$ be a blue/red colored Boolean
lattice. Fix some linear ordering $\pi=(y_{1},\dots,y_{k})$ of $\mathcal{Y}$
and define $Y(0),\ldots,Y(k)$ by $Y(0)=\varnothing$ and
$Y(i)=\\{y_{1},\dots,y_{i}\\}$ for $i\in[k]$. Then there exists at least one
of the following in $Q$:

  1. (a)

a red $\mathcal{X}$-good copy of $\mathcal{Q}(\mathcal{X})$, or

  2. (b)

a blue chain of length $k+1$ of the form $(X_{0},Y(0)),\dots,(X_{k},Y(k))$
where $X_{0}\subseteq X_{1}\subseteq\dots\subseteq X_{k}\subseteq\mathcal{X}$.

###### Proof.

Suppose that there is no blue chain as described in (b). For every
$X\subseteq\mathcal{X}$, we recursively define a label
$\ell_{X}\in\\{0,\dots,k\\}$ such that $\phi\colon\mathcal{Q}(\mathcal{X})\to
Q$, $\phi(X)=(X,Y(\ell_{X}))$, is an embedding with monochromatic red image.
We require $\ell_{X}$ to fulfill three properties:

  1. (1)

For any $X^{\prime}\subseteq X$, $\ell_{X^{\prime}}\leq\ell_{X}$.

  2. (2)

There is a blue chain of length $\ell_{X}$ contained in the Boolean lattice
with ground set $X\cup Y(\ell_{X})$, which we denote by $Q^{X}$.

  3. (3)

$(X,Y(\ell_{X}))$ is red.

First, consider the vertex $\varnothing$. Let $\ell_{\varnothing}$ be the
minimum $\ell$, $0\leq\ell\leq k$, such that $(\varnothing,Y(\ell))$ is red.
If such an $\ell$ does not exist, then
$(\varnothing,Y(0)),\dots,(\varnothing,Y(k))$ form a blue chain, a
contradiction. It is clear to see that Properties (1) and (3) hold. If
$\ell_{\varnothing}=0$, (2) is trivially true. If $\ell_{\varnothing}\geq 1$,
$(\varnothing,Y(0)),\dots,(\varnothing,Y(\ell_{\varnothing}-1))$ form a blue
chain of length $\ell_{\varnothing}$ and $(2)$ holds as well.

Consider an arbitrary $X\subseteq\mathcal{X}$ and suppose that for all
$X^{\prime}\subset X$ we already defined $\ell_{X^{\prime}}$ with Properties
(1)-(3). Let $\ell^{\prime}_{X}=\max_{\\{U\subset X\\}}\ell_{U}$. Then let
$\ell_{X}$ be the minimum $\ell$, $\ell^{\prime}_{X}\leq\ell\leq k$ such that
$(X,Y(\ell))$ is colored in red. If there is no such $\ell$, then
$(X,Y(\ell^{\prime}_{X})),\dots,(X,Y(k))$ is a blue chain of length
$k-\ell^{\prime}_{X}+1$. By definition of $\ell^{\prime}_{X}$ there is some
$U\subset X$ with $\ell_{U}=\ell^{\prime}_{X}$. In particular, $(2)$ holds for
$U$, so there is a blue chain of length $\ell^{\prime}_{X}$ in $Q^{U}$. Note
that $(U,Y(\ell_{U}))\subset(X,Y(\ell^{\prime}_{X}))$, so we obtain a blue
chain of length $k+1$. This is a contradiction, thus $\ell_{X}$ is well-
defined and fulfills Property (3).

If $\ell_{X}=\ell^{\prime}_{X}$, consider the aforementioned blue chain of
length $\ell^{\prime}_{X}$ in $Q^{U}$, and otherwise consider this chain
together with $(X,Y(\ell^{\prime}_{X})),\dots,(X,Y(\ell_{X}-1))$. In both
cases, we obtain a blue chain of length $\ell_{X}$, which proves $(2)$. For
$X^{\prime}\subset X\subseteq\mathcal{X}$,
$\ell_{X^{\prime}}\leq\ell^{\prime}_{X}\leq\ell_{X}$, thus (1) holds.

We define $\phi\colon\mathcal{Q}(\mathcal{X})\to Q$,
$\phi(X)=(X,Y(\ell_{X}))$. Note that $\phi(X)\cap\mathcal{X}=X$ for every
$X\subseteq\mathcal{X}$ and Property (3) implies that $\phi(X)$ is red. Let
$X_{1},X_{2}\subseteq\mathcal{X}$. If $\phi(X_{1})\subseteq\phi(X_{2})$, it is
immediate that $X_{1}\subseteq X_{2}$. Conversely, if $X_{1}\subseteq X_{2}$,
then by Property (1) we have $\ell_{X_{1}}\leq\ell_{X_{2}}$. Thus
$(X_{1},Y(\ell_{X_{1}}))\subseteq(X_{2},Y(\ell_{X_{2}}))$. As a consequence,
$\phi$ is an $\mathcal{X}$-good embedding of $\mathcal{Q}(\mathcal{X})$. ∎

This Lemma implies the following corollary which is already given in an
alternative form by Axenovich and Walzer, see Lemma 4 of [1].

######  Corollary 9.

Let $\mathcal{X},\mathcal{Y}$ be disjoint sets with $|\mathcal{X}|=n$ and
$|\mathcal{Y}|=k$. Let $\mathcal{P}$ be a subposet of a Boolean lattice
$Q=\mathcal{Q}(\mathcal{X}\cup\mathcal{Y})$ such that there is no chain of
length $k+1$ in $\mathcal{P}$. Then there exists a copy of $Q_{n}$ in $Q$
which contains no vertex of $\mathcal{P}$.

###### Proof.

Fix an arbitrary linear ordering of $\mathcal{Y}$. Furthermore, let
$c:Q\to\\{blue,red\\}$ be the coloring such that

$c(X)=\begin{cases}\text{blue},\hskip 19.91684pt\mbox{ if
}~{}~{}X\in\mathcal{P},\\\ \text{red},\hskip 22.76228pt\mbox{
otherwise.}\end{cases}$

There is no blue chain of length $k+1$ in $c$, so by Lemma 8 there is a
monochromatic red copy of $Q_{n}$ in $Q$. This copy does not contain any
vertex of $\mathcal{P}$. ∎

With the help of Lemma 8, we can now prove an upper bound for
$R(Q_{2},Q_{n})$. The concluding arguments are due to Grósz, Methuku, and
Tompkins [8].

###### Proof of Theorem 1.

For the lower bound, the reader is referred to [8]. For the upper bound, let
$k\in\mathbb{N}$ with $k=\tfrac{(2+\epsilon)n}{\log(n)}$. Let $\mathcal{X}$
and $\mathcal{Y}$ be disjoint sets with $|\mathcal{X}|=n$ and
$|\mathcal{Y}|=k$. Consider a blue/red coloring of
$Q=\mathcal{Q}(\mathcal{X}\cup\mathcal{Y})$ with no monochromatic red copy of
$Q_{n}$. Let $\pi=(y_{1}^{\pi},\dots,y_{k}^{\pi})$ be a linear ordering of
$\mathcal{Y}$. By Lemma 8, there exists a blue chain of length $k+1$ of the
form
$(X^{\pi}_{0},\varnothing),(X^{\pi}_{1},\\{y^{\pi}_{1}\\}),(X^{\pi}_{2},\\{y^{\pi}_{1},y^{\pi}_{2}\\}),\dots,(X^{\pi}_{k},\mathcal{Y})$
where $X^{\pi}_{i}\subseteq\mathcal{X}$.

Note that there are $k!$ distinct orderings of $\mathcal{Y}$. For each linear
ordering $\pi$ of $\mathcal{Y}$ we consider $X^{\pi}_{0}$ and $X^{\pi}_{k}$,
i.e. the minimal and maximal vertex of the aforementioned chain restricted to
$\mathcal{X}$. By the choice of $k$, we obtain $k!>2^{2n}$. In particular by
pigeonhole principle, there are distinct $\pi_{1},\pi_{2}$ with
$X^{\pi_{1}}_{0}=X^{\pi_{2}}_{0}$ and $X^{\pi_{1}}_{k}=X^{\pi_{2}}_{k}$. Since
$\pi_{1},\pi_{2}$ are distinct, there exists an index $1\leq i\leq k-1$ with
$\\{y^{\pi_{1}}_{1},\dots,y^{\pi_{1}}_{i}\\}\neq\\{y^{\pi_{2}}_{1},\dots,y^{\pi_{2}}_{i}\\}$.
Then the four vertices

$(X^{\pi_{1}}_{0},\varnothing),(X^{\pi_{1}}_{i},\\{y^{\pi_{1}}_{1},\dots,y^{\pi_{1}}_{i}\\}),(X^{\pi_{2}}_{i},\\{y^{\pi_{2}}_{1},\dots,y^{\pi_{2}}_{i}\\}),(X^{\pi_{1}}_{k},\mathcal{Y})$

form a blue copy of $Q_{2}$. ∎

###  2.5 Factorial trees and shrubs

Besides the Boolean lattice, there is another poset which plays a major role
in this paper, which we call the factorial tree.

Consider the set of ordered subsets of a fixed non-empty set $\mathcal{Y}$,
that also could be thought of as a set of strings with non-repeated letters
over the alphabet $\mathcal{Y}$. Note that we also allow the empty set as such
an ordered subset. Occasionally, if it is clear from the context, we refer to
the empty ordered set $(\varnothing,\leq)$ simply as $\varnothing$. For an
ordered subset $S$ of $\mathcal{Y}$, we refer to its underlying unordered set
as $\underline{S}$. Let $|S|=|\underline{S}|$ be the size of $S$. We also say
that $S$ is an ordering of $\underline{S}$.

Let $S$ be an ordered subset of $\mathcal{Y}$. A prefix of $S$ is an ordered
subset $T$ of $\mathcal{Y}$ consisting of the first $|T|$ elements of $S$ in
the ordering induced by $S$. If $T$ is a prefix of $S$, we write
$T\leq_{\mathcal{O}}S$. Note that the empty ordered set is a prefix of every
ordered set. If $T\neq S$, we say that a prefix $T$ of $S$ is strict, denoted
by $T<_{\mathcal{O}}S$. Observe that the prefix relation $\leq_{\mathcal{O}}$
is transitive, reflexive and antisymmetric. Let $\mathcal{O}(\mathcal{Y})$ be
the poset of all ordered subsets of $\mathcal{Y}$ equipped with
$\leq_{\mathcal{O}}$. We say that this poset is the factorial tree on ground
set $\mathcal{Y}$.

In a factorial tree $\mathcal{O}(\mathcal{Y})$ for every vertex
$S\in\mathcal{O}(\mathcal{Y})$, the set of prefixes
$\\{T\in\mathcal{O}(\mathcal{Y})\colon T\leq_{\mathcal{O}}S\\}$ induces a
chain. Furthermore, the vertex $\varnothing$ is the unique minimal vertex of
$\mathcal{Y}$, thus $\mathcal{O}(\mathcal{Y})$ is an up-tree.

Let $\mathcal{X}$ and $\mathcal{Y}$ be disjoint sets. Let
$Q=\mathcal{Q}(\mathcal{X}\cup\mathcal{Y})$ and $\mathcal{O}(\mathcal{Y})$ be
the factorial tree with ground set $\mathcal{Y}$. An embedding $\tau$ of
$\mathcal{O}(\mathcal{Y})$ into $Q$ is $\mathcal{Y}$-good if for every
$S\in\mathcal{O}(\mathcal{Y})$, $\tau(S)\cap\mathcal{Y}=\underline{S}$. We say
that a subposet $\mathcal{P}$ of $Q$ is a $\mathcal{Y}$-good copy of
$\mathcal{O}(\mathcal{Y})$ if there exists a $\mathcal{Y}$-good embedding
$\tau:\mathcal{O}(\mathcal{Y})\to Q$ with image $\mathcal{P}$. We refer to
such a copy also as a $\mathcal{Y}$-shrub.

Besides that, we also consider a related subposet with slightly weaker
conditions. A weak $\mathcal{Y}$-shrub is a subposet $\mathcal{P}$ of $Q$ such
that there is a function $\tau:\mathcal{O}(\mathcal{Y})\to Q$ with image
$\mathcal{P}$ such that for every $S\in\mathcal{O}(\mathcal{Y})$,
$\tau(S)\cap\mathcal{Y}=\underline{S}$ and for every
$S,T\in\mathcal{O}(\mathcal{Y})$ with $S<_{\mathcal{O}}T$,
$\tau(S)\subset\tau(T)$. In particular, a weak $\mathcal{Y}$-shrub might not
correspond to an injective embedding of $\mathcal{O}(\mathcal{Y})$.

Clearly a $\mathcal{Y}$-shrub is also a weak $\mathcal{Y}$-shrub.
Surprisingly, the converse statement is also true in Boolean lattices not
containing a copy of $\Lambda$.

######  Proposition 10.

Let $\mathcal{X}$ and $\mathcal{Y}$ be disjoint sets, let
$Q=\mathcal{Q}(\mathcal{X}\cup\mathcal{Y})$. Let $\mathcal{P}$ be a weak
$\mathcal{Y}$-shrub in $Q$ such that $\mathcal{P}$ contains no copy of
$\Lambda$. Then $\mathcal{P}$ is a $\mathcal{Y}$-shrub.

###### Proof.

Let $\tau:\mathcal{O}(\mathcal{Y})\to Q$ be a map such that for every
$S,T\in\mathcal{O}(\mathcal{Y})$ with $S<_{\mathcal{O}}T$, we have
$\tau(S)\subset\tau(T)$ and $\tau(S)\cap\mathcal{Y}=\underline{S}$, and let
$\mathcal{P}$ be its image. For all $S\in\mathcal{O}(\mathcal{Y})$, let
$X_{S}=\tau(S)\cap\mathcal{X}$, i.e. $\tau(S)=(X_{S},\underline{S})$. We shall
show that $\tau$ is an embedding, thus proving that $\mathcal{P}$ is a
$\mathcal{Y}$-shrub. For that we need to prove that the condition
$\tau(S)\subseteq\tau(T)$ implies that $S\leq_{\mathcal{O}}T$ for any ordered
subsets $S$ and $T$ of $\mathcal{Y}$.

Let $\tau(S)\subseteq\tau(T)$, i.e.
$(X_{S},\underline{S})\subseteq(X_{T},\underline{T})$. In particular,
$\underline{S}\subseteq\underline{T}$ and so $|S|\leq|T|$. Let $R$ be the
largest common prefix of $S$ and $T$. Such exists since $\varnothing$ is a
prefix of every ordered set. If $|R|=|S|$, then $S=R\leq_{\mathcal{O}}T$ and
we are done. So we can assume that $|S|\geq|R|+1$.

If $|T|\leq|R|+1$, then $|R|+1\leq|S|\leq|T|\leq|R|+1$. This implies $|S|=|T|$
and since $\underline{S}\subseteq\underline{T}$, we have
$\underline{S}=\underline{T}$. Let
$\\{y\\}=\underline{S}\backslash\underline{R}=\underline{T}\backslash\underline{R}$.
Then both $S,T$ have $R$ as prefix of size $|S|-1=|T|-1$ and $y$ as final
vertex. Thus $S=T$ and we are done as well.

From now on, we assume that $|S|\geq|R|+1$ and $|T|>|R|+1$. Consider prefixes
$S^{\prime}\leq_{\mathcal{O}}S$ and $T^{\prime}\leq_{\mathcal{O}}T$ of size
$|R|+1$. Then $R$ is a prefix of both $S^{\prime}$ and $T^{\prime}$. Let
$y_{S}$ such that $\underline{S^{\prime}}\backslash\underline{R}=\\{y_{S}\\}$
and let $y_{T}$ with
$\underline{T^{\prime}}\backslash\underline{R}=\\{y_{T}\\}$.

If $y_{S}=y_{T}$, we obtain $S^{\prime}=T^{\prime}$, which implies that $R$ is
not the largest common prefix of $S$ and $T$, a contradiction.

If $y_{S}\neq y_{T}$, the unordered sets $\underline{S^{\prime}}$ and
$\underline{T^{\prime}}$ are not comparable. In particular,
$(X_{T^{\prime}},\underline{T^{\prime}})$ and
$(X_{S^{\prime}},\underline{S^{\prime}})$ are incomparable. Because
$S^{\prime}\leq_{\mathcal{O}}S$, $T^{\prime}<_{\mathcal{O}}T$ and by our
initial assumption, we know that
$(X_{S^{\prime}},\underline{S^{\prime}})\subseteq(X_{S},\underline{S})\subseteq(X_{T},\underline{T})$
and $(X_{T^{\prime}},\underline{T^{\prime}})\subseteq(X_{T},\underline{T})$.
Since $|S^{\prime}|=|T^{\prime}|=|R|+1<|T|$, we obtain that both
$(X_{S^{\prime}},\underline{S^{\prime}})$ and
$(X_{T^{\prime}},\underline{T^{\prime}})$ are proper subsets of
$(X_{T},\underline{T})$. Then the three vertices
$(X_{T},\underline{T}),(X_{T^{\prime}},\underline{T^{\prime}})$ and
$(X_{S^{\prime}},\underline{S^{\prime}})$ form a copy of $\Lambda$ in $Q$, so
we reach a contradiction. ∎

###  2.6 Construction of an almost optimal shrub

Let $\mathcal{Y}$ be a $k$-element set. Note that a $\mathcal{Y}$-shrub has
$k!$ maximal vertices corresponding to all permutations of $\mathcal{Y}$.
These maximal vertices form an antichain, i.e. are pairwise incomparable.
Sperner’s theorem implies that a ground set of any $\mathcal{Y}$-shrub must
have size at least $q$, where $\binom{q}{\lfloor q/2\rfloor}\geq k!$, so
$q\geq k(\log k+\log e)+o(k)$. Next, we shall construct a $\mathcal{Y}$-shrub
which is almost optimal in the sense that $\mathcal{Y}$ has ground set of size
almost matching the lower bound above.

######  Proposition 11.

Let $\mathcal{Y}$ be a $k$-element set. Let $A$ be a set disjoint from
$\mathcal{Y}$ such that $|A|\geq k\cdot\min\\{\log k+\log\log k,11\\}$. Then
there is a $\mathcal{Y}$-shrub in $\mathcal{Q}(A\cup\mathcal{Y})$.

###### Proof.

Let $\mathcal{Y}=\\{y_{0},\ldots,y_{k-1}\\}$ and let
$Q=\mathcal{Q}(A\cup\mathcal{Y})$. We use addition of indices modulo $k$. Let
$A_{0},\ldots,A_{k-1}$ be pairwise disjoint subsets of $A$ such that
$|A_{i}|=\ell$ for the smallest integer $\ell$ satisfying
$\binom{\ell}{\lfloor\ell/2\rfloor}\geq k$. Since $\ell\leq\log k+\log\log k$
for $k\geq 256$ and $\ell\leq 11$ for $k\leq 256$, such $A_{i}$’s can be
chosen. Let $\big{\\{}A_{i}^{j}:j\in\\{0,\ldots,k-1\\}\big{\\}}$ be an
antichain in $\mathcal{Q}(A_{i})$, $i\in\\{0,\ldots,k-1\\}$. Such an antichain
exists by Sperner’s theorem.

Consider the factorial tree $\mathcal{O}(\mathcal{Y})$. We shall construct an
embedding $\tau$ of $\mathcal{O}(\mathcal{Y})$ into $Q$ as follows. Let
$\tau(\varnothing)=\varnothing$. Consider any non-empty ordered subset of
$\mathcal{Y}$, say $(y_{i_{1}},y_{i_{2}},\ldots,y_{i_{j}})$, $1\leq j\leq k$.
If $j=1$, let $\tau((y_{i_{1}}))=A_{i_{1}}\cup\\{y_{i_{1}}\\}$. If $j>1$, let

$\tau((y_{i_{1}},\ldots,y_{i_{j}}))=A_{i_{1}}\cup
A_{i_{1}+1}^{i_{2}}\cdots\cup
A_{i_{1}+j-1}^{i_{j}}\cup\\{y_{i_{1}},\ldots,y_{i_{j}}\\}.$

For example for $k=4$, $\tau((y_{0},y_{1},y_{2}))=A_{0}\cup A_{1}^{1}\cup
A_{2}^{2}\cup\\{y_{1},y_{2},y_{3}\\}$, $\tau((y_{2},y_{3},y_{1}))=A_{2}\cup
A_{3}^{3}\cup A_{0}^{1}\cup\\{y_{1},y_{2},y_{3}\\}$, and
$\tau((y_{3},y_{1}))=A_{3}\cup A_{0}^{1}\cup\\{y_{1},y_{3}\\}$.

Note that the image of $\mathcal{O}(\mathcal{Y})$ under $\tau$ is an up-tree,
$\mathcal{T}$, whose minimum vertex is $\varnothing$, see Figures 1 and 2. We
see that each maximum vertex of $\mathcal{T}$ is joined to $\varnothing$ by a
unique chain, a maximal chain. Furthermore, non-zero vertices that belong to
distinct maximal chains are incomparable. Observe that $\tau$ is a
$\mathcal{Y}$-good embedding of $\mathcal{O}(\mathcal{Y})$ into $Q$. Indeed,
for any ordered sequence of distinct vertices $(y_{i_{1}},\ldots,y_{i_{j}})$,
we have
$\tau((y_{i_{1}},\ldots,y_{i_{j}}))\cap\mathcal{Y}=\\{y_{i_{1}},\ldots,y_{i_{j}}\\}$.
In addition
$(y_{i_{1}},\ldots,y_{i_{q}})<_{\mathcal{O}}(y_{i_{1}},\ldots,y_{i_{p}})$ if
and only if $\tau((y_{i_{1}},\ldots,y_{i_{q}}))$ and
$\tau((y_{i_{1}},\ldots,y_{i_{p}}))$ are in the same maximal chain of $T$ in
the corresponding order. ∎

Figure 1: A diagram illustrating how the $A_{i}^{j}$’s are being assigned to
the elements of the $\\{y_{0},y_{1},y_{2},y_{3}\\}$-shrub constructed in
Proposition 11. Figure 2: Segment of a shrub highlighted in Figure 1. Here the
union signs are omitted because of the spacing, for example
$A_{2}A_{3}^{1}A_{0}^{0}y_{2}y_{1}y_{0}$ corresponds to the shrub vertex
$A_{2}\cup A_{3}^{1}\cup A_{0}^{0}\cup\\{y_{2},y_{1},y_{0}\\}$.

##  3 Duality theorem

In this section, we show a duality statement which is the key argument for the
proof of Theorem 3. Recall the following definitions. We call an embedding
$\phi$ of $\mathcal{Q}(\mathcal{X})$ into
$\mathcal{Q}(\mathcal{X}\cup\mathcal{Y})$ for disjoint $\mathcal{X}$ and
$\mathcal{Y}$,  $\mathcal{X}$-good if $\phi(X)\cap\mathcal{X}=X$ for all
$X\subseteq\mathcal{X}$. We also call a copy of $\mathcal{Q}(\mathcal{X})$ in
$\mathcal{Q}(\mathcal{X}\cup\mathcal{Y})$ $\mathcal{X}$-good if there is an
$\mathcal{X}$-good embedding of $\mathcal{Q}(\mathcal{X})$ into
$\mathcal{Q}(\mathcal{X}\cup\mathcal{Y})$. An embedding $\tau$ of
$\mathcal{O}(\mathcal{Y})$ into $\mathcal{Q}(\mathcal{X}\cup\mathcal{Y})$ is
$\mathcal{Y}$-good if $\tau(S)\cap\mathcal{Y}=\underline{S}$ for all
$S\in\mathcal{O}(\mathcal{Y})$. We say that a copy of
$\mathcal{O}(\mathcal{Y})$ is a $\mathcal{Y}$-shrub if there exists a
$\mathcal{Y}$-good embedding of $\mathcal{O}(\mathcal{Y})$ into
$\mathcal{Q}(\mathcal{X}\cup\mathcal{Y})$.

######  Theorem 12 (Duality Theorem).

For two disjoint sets $\mathcal{X}$ and $\mathcal{Y}$, let
$Q=\mathcal{Q}(\mathcal{X}\cup\mathcal{Y})$ be a blue/red colored Boolean
lattice which contains no blue copy of $\Lambda$. Then there is exactly one of
the following in $Q$:

  * •

a red $\mathcal{X}$-good copy of $\mathcal{Q}(\mathcal{X})$, or

  * •

a blue $\mathcal{Y}$-good copy of $\mathcal{O}(\mathcal{Y})$, i.e. a blue
$\mathcal{Y}$-shrub.

Informally speaking, this duality statement claims that for any bipartition
$\mathcal{X}\cup\mathcal{Y}$ of the ground set of a Boolean lattice there
exists either a red copy of $\mathcal{Q}(\mathcal{X})$ that is restricted to
$\mathcal{X}$ or a blue copy of the factorial tree $\mathcal{O}(\mathcal{Y})$
restricted to $\mathcal{Y}$. This result can be seen as a strengthening of
Lemma 8 in the special case when we forbid a blue copy of $\Lambda$. The
Duality Theorem implies a criterion for blue/red colored Boolean lattices $Q$
to have neither a blue copy of $\Lambda$ nor a red copy of $Q_{n}$.

######  Corollary 13.

Let $n,k\in\mathbb{N}$ and $N=n+k$. Let $Q=\mathcal{Q}([N])$ be a blue/red
colored Boolean lattice with no blue copy of $\Lambda$. There is no red copy
of $Q_{n}$ in $Q$ if and only if for every $\mathcal{Y}\in\binom{[N]}{k}$
there exists a blue $\mathcal{Y}$-shrub in $Q$.

###### Proof.

Lemma 7 provides that there is a red copy of $Q_{n}$ in $Q$ if and only if
there exists a partition $[N]=\mathcal{X}\cup\mathcal{Y}$ of the ground set of
$Q$ with $|\mathcal{X}|=n$ and $|\mathcal{Y}|=k$ as well as an
$\mathcal{X}$-good embedding $\phi$ of $Q(\mathcal{X})$ into $Q$ with a
monochromatic red image.

If there is a red copy of $Q_{n}$ in $Q$, then for $\mathcal{X},\mathcal{Y}$
from Lemma 7 there is also an $\mathcal{X}$-good copy of
$\mathcal{Q}(\mathcal{X})$. Thus by Theorem 12 there is no blue
$\mathcal{Y}$-shrub.

On the other hand, if there is no red copy of $Q_{n}$ in $Q$, there is no red
$\mathcal{X}$-good copy of $\mathcal{Q}(\mathcal{X})$ for any
$\mathcal{X}\in\binom{[N]}{n}$. Then for an arbitrary $n$-element subset
$\mathcal{X}$ of $[N]$, let $\mathcal{Y}=[N]\setminus\mathcal{X}$. Now Theorem
12 implies that there exists a blue $\mathcal{Y}$-shrub. In particular, there
is a blue $\mathcal{Y}$-shrub for any $k$-element subset $\mathcal{Y}$ of
$[N]$. ∎

Throughout the section, let $\mathcal{X}$ and $\mathcal{Y}$ be fixed disjoint
sets. Let $Q=\mathcal{Q}(\mathcal{X}\cup\mathcal{Y})$ be a Boolean lattice on
ground set $\mathcal{X}\cup\mathcal{Y}$. We fix an arbitrary blue/red coloring
of $Q$ with no blue copy of $\Lambda$. We always let $n,k\in\mathbb{N}$ such
that $|\mathcal{X}|=n$, $|\mathcal{Y}|=k$ and let $N=n+k$. For
$X\subseteq\mathcal{X}$, $Y\subseteq\mathcal{Y}$, we usually denote the vertex
$X\cup Y$ by $(X,Y)$.

In order to characterize colorings of $Q$ which do not contain an embedding
$\phi$ of $\mathcal{Q}(\mathcal{X})$ into $Q$ such that for every
$X\in\mathcal{Q}(\mathcal{X})$, $\phi(X)$ is red and
$\phi(X)\cap\mathcal{X}=X$, we introduce the following notation.

For $X\subseteq\mathcal{X}$ and $Y\subseteq\mathcal{Y}$, we say that the
vertex $(X,Y)\in Q$ is embeddable if there is an embedding
$\phi:\mathcal{Q}(\mathcal{X})\cap\\{X^{\prime}\subseteq\mathcal{X}\colon
X^{\prime}\supseteq X\\}\to Q$ with a monochromatic red image, such that
$\phi(X^{\prime})\cap\mathcal{X}=X^{\prime}$ for all $X^{\prime}$ and
$\phi(X)\supseteq(X,Y)$. We say that $\phi$ witnesses that $(X,Y)$ is
embeddable.

This definition immediately implies:

######  Observation 14.

$(\varnothing,\varnothing)$ is not embeddable if and only if there is no
embedding $\phi:\mathcal{Q}(\mathcal{X})\to Q$ such that for every
$X^{\prime}\subseteq\mathcal{X}$, $\phi(X^{\prime})$ red and
$\phi(X^{\prime})\cap\mathcal{X}=X^{\prime}$.

The key ingredient for the proof of the Duality Theorem, Theorem 12, is the
following characterization of embeddable vertices.

######  Lemma 15.

Let $X\subseteq\mathcal{X}$, $Y\subseteq\mathcal{Y}$. Let
$Q=\mathcal{Q}(\mathcal{X}\cup\mathcal{Y})$ be a blue/red colored Boolean
lattice with no blue copy of $\Lambda$. Then $(X,Y)$ is embeddable if and only
if either

  1. (i)

$(X,Y)$ is blue and there is a $Y^{\prime}\subseteq\mathcal{Y}$ with
$Y^{\prime}\supsetneq Y$ such that $(X,Y^{\prime})$ is embeddable, or

  2. (ii)

$(X,Y)$ is red and for all $X^{\prime}\subseteq\mathcal{X}$ with
$X^{\prime}\supsetneq X$, $(X^{\prime},Y)$ is embeddable.

Note that if $X\subseteq\mathcal{X}$ and $(X,\mathcal{Y})$ is blue, then
$(X,\mathcal{Y})$ is not embeddable.

###### Proof.

First suppose that $(X,Y)$ is embeddable. Let $\phi$ be an embedding of
$\mathcal{Q}(\mathcal{X})\cap\\{X^{\prime}\subseteq\mathcal{X}\colon
X^{\prime}\supseteq X\\}$ into $Q$ witnessing that $(X,Y)$ is embeddable.

If $(X,Y)$ is blue, then $\phi(X)\supsetneq(X,Y)$ because $\phi$ has a
monochromatic red image. Thus there exists $Y^{\prime}\subseteq\mathcal{Y}$
with $Y^{\prime}\supsetneq Y$ such that $\phi(X)=(X,Y^{\prime})$. But then
$\phi$ also witnesses that $(X,Y^{\prime})$ is embeddable, so Condition (i) is
fulfilled.

If $(X,Y)$ is red, pick some arbitrary $X^{*}\subseteq\mathcal{X}$ such that
$X^{*}\supsetneq X$. Then the function
$\phi^{*}:\mathcal{Q}(\mathcal{X})\cap\\{X^{\prime}\subseteq\mathcal{X}\colon
X^{\prime}\supseteq X^{*}\\}\to Q$, $\phi^{*}(X^{\prime})=\phi(X^{\prime})$ is
a restriction of $\phi$ and therefore an embedding with a monochromatic red
image such that $\phi^{*}(X^{\prime})\cap\mathcal{X}=X^{\prime}$ for all
$X^{\prime}$ and $\phi^{*}(X^{*})\supseteq(X^{*},Y)$. Thus for every
$X^{*}\subseteq\mathcal{X}$ with $X^{*}\supsetneq X$, the vertex $(X^{*},Y)$
is embeddable, i.e., Condition (ii) is fulfilled.

Now, suppose that Condition (i) or Condition (ii) hold. If (i) holds, then
$(X,Y)$ is blue and there is some $Y^{\prime}\supsetneq Y$ such that
$(X,Y^{\prime})$ is embeddable. Then the embedding witnessing that also
verifies that $(X,Y)$ is embeddable.

For the rest of the proof we assume that (ii) holds, i.e., that $(X,Y)$ is red
and for any $X^{\prime}\subseteq\mathcal{X}$ with $X^{\prime}\supsetneq X$ the
vertex $(X^{\prime},Y)$ is embeddable. We define the required embedding
$\phi:\mathcal{Q}(\mathcal{X})\cap\\{X^{\prime}\subseteq\mathcal{X}\colon
X^{\prime}\supseteq X\\}\to Q$ for every $X^{\prime}$ with $X\subseteq
X^{\prime}\subseteq\mathcal{X}$ depending on the number of minimal $X^{*}$’s,
$X\subseteq X^{*}\subseteq X^{\prime}$ such that $(X^{*},Y)$ is blue as
follows. Let $X^{\prime}$ with $X\subseteq X^{\prime}\subseteq\mathcal{X}$ be
arbitrary.

  1. (1)

If for all $X^{*}$ with $X\subseteq X^{*}\subseteq X^{\prime}$, the vertex
$(X^{*},Y)$ is red, let $\phi(X^{\prime})=(X^{\prime},Y)$. Note that this case
includes $X^{\prime}=X$.

  2. (2)

If there is a unique minimal $X^{*}$ such that $X\subseteq X^{*}\subseteq
X^{\prime}$ and $(X^{*},Y)$ is blue, then $(X^{*},Y)$ is embeddable by
Condition (ii). Let $\phi_{X^{*}}$ be an embedding witnessing that. Then set
$\phi(X^{\prime})=\phi_{X^{*}}(X^{\prime})$.

  3. (3)

Otherwise, let $\phi(X^{\prime})=(X^{\prime},\mathcal{Y})$.

Cases (1)-(3) determine a partition of the set
$\\{X^{\prime}\subseteq\mathcal{X}\colon X^{\prime}\supseteq X\\}$ into three
pairwise disjoint parts. Let $\mathcal{M}_{j}$, $j\in[3]$, be the set of those
vertices $X^{\prime}$ for which $\phi$ was assigned in Case (j). Note that
$\mathcal{M}_{1}\cup\mathcal{M}_{2}\cup\mathcal{M}_{3}=\\{X^{\prime}\subseteq\mathcal{X}\colon
X^{\prime}\supseteq X\\}$.

Claim. The function $\phi$ witnesses that $(X,Y)$ is embeddable.

  * •

Clearly, for every $X^{\prime}\subseteq\mathcal{X}$ with $X^{\prime}\supseteq
X$, $\phi(X^{\prime})\cap\mathcal{X}=X^{\prime}$.

  * •

$(X,Y)$ is red, so $X\in\mathcal{M}_{1}$. Thus $\phi(X)=(X,Y)$.

  * •

The argument verifying that $\phi(X^{\prime})$ is red for every
$X^{\prime}\subseteq\mathcal{X}$ with $X^{\prime}\supseteq X$ depends on $i$
such that $X^{\prime}\in\mathcal{M}_{i}$. If $X^{\prime}\in\mathcal{M}_{1}$,
it is immediate that $\phi(X^{\prime})$ is red. If
$X^{\prime}\in\mathcal{M}_{2}$, $\phi_{X^{*}}$ has a monochromatic red image,
thus $\phi(X^{\prime})=\phi_{X^{*}}(X^{\prime})$ is also red. Now consider the
case that $X^{\prime}\in\mathcal{M}_{3}$, i.e. there are
$X_{1},X_{2}\subseteq\mathcal{X}$ with $X_{1}\neq X_{2}$ and $X\subseteq
X_{i}\subseteq X^{\prime}$, $i\in[2]$, such that $(X_{i},Y)$ are blue and
$X_{i}$ are both minimal with this property. The latter condition implies that
$X_{1}$ and $X_{2}$ are incomparable, in particular $(X_{1},Y)$ and
$(X_{2},Y)$ are incomparable as well. Moreover, observe that $X_{i}\neq
X^{\prime}$, $i\in[2]$, because $X^{\prime}$ is by definition comparable to
both $X_{1}$ and $X_{2}$. Now assume for a contradiction that
$\phi(X^{\prime})=(X^{\prime},\mathcal{Y})$ is blue. Recall that $(X_{1},Y)$
and $(X_{2},Y)$ are blue. We know that $X_{i}\subset X^{\prime}$ and
$Y\subseteq\mathcal{Y}$, thus $(X_{i},Y)\subset(X^{\prime},\mathcal{Y})$. As a
consequence, $(X_{1},Y)$, $(X_{2},Y)$ and $(X^{\prime},\mathcal{Y})$ induce a
blue copy of $\Lambda$ in $Q$, which is a contradiction. Thus $\phi$ has a
monochromatic red image.

  * •

It remains to show that $\phi$ is an embedding. Let
$X_{1},X_{2}\subseteq\mathcal{X}$ be arbitrary with $X\subseteq X_{i}\subseteq
X^{\prime}$, $i\in[2]$. We shall show that $X_{1}\subseteq X_{2}$ if and only
if $\phi(X_{1})\subseteq\phi(X_{2})$. One direction is easy to prove: If
$\phi(X_{1})\subseteq\phi(X_{2})$, then
$X_{1}=\phi(X_{1})\cap\mathcal{X}\subseteq\phi(X_{2})\cap\mathcal{X}=X_{2}$.
Now suppose that $X_{1}\subseteq X_{2}$. Let $Y_{1},Y_{2}\subseteq\mathcal{Y}$
such that $\phi(X_{1})=(X_{1},Y_{1})$ and $\phi(X_{2})=(X_{2},Y_{2})$. Then we
shall show that $Y_{1}\subseteq Y_{2}$. Note that $Y\subseteq
Y_{i}\subseteq\mathcal{Y}$ for $i\in[2]$.

Assume that at least one of $X_{1}$ or $X_{2}$ is in
$\mathcal{M}_{1}\cup\mathcal{M}_{3}$. If $X_{1}\in\mathcal{M}_{1}$, then
$Y_{1}=Y$ and we are done as $Y\subseteq Y_{2}$. Furthermore, if
$X_{2}\in\mathcal{M}_{3}$, then $Y_{2}=\mathcal{Y}$ and we are done as well
since $Y_{1}\subseteq\mathcal{Y}$. If $X_{1}\in\mathcal{M}_{3}$, then
$X_{1}\subseteq X_{2}$ implies that $X_{2}$ is also in $\mathcal{M}_{3}$.
Conversely, if $X_{2}\in\mathcal{M}_{1}$, the fact that $X_{2}\supseteq X_{1}$
yields that $X_{1}\in\mathcal{M}_{1}$ and we are done as before.

As a final step, suppose that $X_{1},X_{2}\in\mathcal{M}_{2}$. This implies
that for each $i\in[2]$, there is a unique minimal vertex $X^{*}_{i}$ such
that $X\subseteq X^{*}_{i}\subseteq X_{i}$ and $(X^{*}_{i},Y)$ is blue.
Applying the initial assumption, $X^{*}_{1}\subseteq X_{1}\subseteq X_{2}$. By
minimality of $X^{*}_{2}$, we obtain that $X^{*}_{2}\subseteq X^{*}_{1}$. Now
this provides that $X^{*}_{2}\subseteq X^{*}_{1}\subseteq X_{1}$. Using the
minimality of $X^{*}_{1}$, we see that $X^{*}_{1}\subseteq X^{*}_{2}$, so
$X^{*}_{1}=X^{*}_{2}$.

Recall that $(X^{*}_{1},Y)=(X^{*}_{2},Y)$ is embeddable since
$X_{1},X_{2}\in\mathcal{M}_{2}$. Consider the function
$\phi_{X^{*}_{1}}=\phi_{X^{*}_{2}}$ witnessing that. Because
$\phi_{X^{*}_{1}}$ is an embedding and $X^{*}_{1}\subseteq X_{1}\subseteq
X_{2}$, we obtain $\phi_{X^{*}_{1}}(X_{1})\subseteq\phi_{X^{*}_{1}}(X_{2})$.
Combining the given conditions,

$\phi(X_{1})=\phi_{X^{*}_{1}}(X_{1})\subseteq\phi_{X^{*}_{1}}(X_{2})=\phi_{X^{*}_{2}}(X_{2})=\phi(X_{2}),$

that implies that $Y_{1}\subseteq Y_{2}$.

This concludes the proof of the Claim and the Lemma. ∎

######  Corollary 16.

Let $X\subseteq\mathcal{X}$ and $S\in\mathcal{O}(\mathcal{Y})$ such that
$(X,\underline{S})$ is not embeddable. Then there exists some
$X^{\prime}\subseteq\mathcal{X}$, $X^{\prime}\supseteq X$, such that
$(X^{\prime},\underline{S})$ is blue and not embeddable.

###### Proof.

If $(X,\underline{S})$ is blue, we are done. Otherwise Lemma 15 yields an
$X_{1}\subseteq\mathcal{X}$, $X_{1}\supsetneq X$ such that
$(X_{1},\underline{S})$ is not embeddable. By repeating this argument, we find
an $X^{\prime}\subseteq\mathcal{X}$, $X^{\prime}\supseteq X$, with
$(X^{\prime},\underline{S})$ is blue and not embeddable. ∎

Next we show a connection between embeddable vertices and the existence of a
weak $\mathcal{Y}$-shrub. Recall that a weak $\mathcal{Y}$-shrub is a subposet
$\mathcal{P}$ of $Q$ such that there is a function
$\tau:\mathcal{O}(\mathcal{Y})\to Q$ with image $\mathcal{P}$ such that for
every $S\in\mathcal{O}(\mathcal{Y})$, $\tau(S)\cap\mathcal{Y}=\underline{S}$,
and for every $S,T\in\mathcal{O}(\mathcal{Y})$ with $S<_{\mathcal{O}}T$,
$\tau(S)\subset\tau(T)$.

######  Lemma 17.

If $(\varnothing,\varnothing)$ is not embeddable, then there is a
monochromatic blue weak $\mathcal{Y}$-shrub.

###### Proof.

We construct $\tau:\mathcal{O}(\mathcal{Y})\to Q$ iteratively and increasingly
with respect to the order of $\mathcal{O}(\mathcal{Y})$. Suppose that
$(\varnothing,\varnothing)$ is not embeddable. By Corollary 16 there is some
$X_{\varnothing}\subseteq\mathcal{X}$ such that
$(X_{\varnothing},\varnothing)$ is blue and not embeddable. Let
$\tau(\varnothing)=(X_{\varnothing},\varnothing)$. From here, we continue
iteratively. Suppose that for $S\in\mathcal{O}(\mathcal{Y})$,
$\underline{S}\neq\mathcal{Y}$, we have defined $X_{S}\subseteq\mathcal{X}$
such that

  1. (1)

$X_{S}\supseteq X_{T}$ for every $T\leq_{\mathcal{O}}S$ and

  2. (2)

$\tau(S)=(X_{S},\underline{S})$ is blue and not embeddable.

Consider an arbitrary $S^{\prime}\in\mathcal{O}(\mathcal{Y})$ such that
$S<_{\mathcal{O}}S^{\prime}$ and $|S^{\prime}|=|S|+1$. By Lemma 15 applied for
$X_{S}$ and $\underline{S}$, we obtain that $(X_{S},\underline{S^{\prime}})$
is not embeddable. Then Corollary 16 yields that there is some
$X_{S^{\prime}}\subseteq\mathcal{X}$, $X_{S^{\prime}}\supseteq X_{S}$, such
that $(X_{S^{\prime}},\underline{S^{\prime}})$ is blue and not embeddable.
Observe that for $T\in\mathcal{O}(\mathcal{Y})$ with
$T\leq_{\mathcal{O}}S^{\prime}$, either $T=S^{\prime}$ and so
$X_{T}=X_{S^{\prime}}$, or $T\leq_{\mathcal{O}}S$ and so by $(1)$
$X_{T}\subseteq X_{S}\subseteq X_{S^{\prime}}$. Let
$\tau(S^{\prime})=(X_{S^{\prime}},\underline{S^{\prime}})$.

Using this procedure, we define $\tau$ for all $S\in\mathcal{O}(\mathcal{Y})$.
Let $\mathcal{P}$ be the subposet of $Q$ induced by the image of $\tau$. We
shall show that $\mathcal{P}$ is a weak $\mathcal{Y}$-shrub witnessed by the
function $\tau$. By (2), for every $S\in\mathcal{O}(\mathcal{Y})$, $\tau(S)$
is blue and $\tau(S)\cap\mathcal{Y}=\underline{S}$.

Let $S,T\in\mathcal{O}(\mathcal{Y})$ with $S<_{\mathcal{O}}T$. Let
$X_{S},X_{T}\subseteq\mathcal{X}$ such that $\tau(S)=(X_{S},\underline{S})$
and $\tau(T)=(X_{T},\underline{T})$. Clearly,
$\underline{S}\subset\underline{T}$. Moreover, item $(1)$ implies that
$X_{S}\subseteq X_{T}$. Consequently, $\tau(S)\subset\tau(T)$.

∎

Combining the previously presented Lemmas, we can now prove the Duality
Theorem.

###### Proof of Theorem 12.

Let $\mathcal{X}$ and $\mathcal{Y}$ be disjoint sets. Let
$Q=Q(\mathcal{X}\cup\mathcal{Y})$ be a blue/red colored Boolean lattice which
contains no blue copy of $\Lambda$.
First suppose that there is no red $\mathcal{X}$-good copy of
$\mathcal{Q}(\mathcal{X})$. By Observation 14, $(\varnothing,\varnothing)$ is
not embeddable and Lemma 17 provides that there is a blue weak
$\mathcal{Y}$-shrub in $Q$. Using Proposition 10 we obtain a blue
$\mathcal{Y}$-shrub in $Q$. This shows that there is either a red
$\mathcal{X}$-good copy of $\mathcal{Q}(\mathcal{X})$ or a blue
$\mathcal{Y}$-shrub.

Next we show that both events could not happen simultaneously. Let
$n=|\mathcal{X}|$, $k=|\mathcal{Y}|$ and $N=n+k$. Assume that there exist both
an $\mathcal{X}$-good embedding $\phi\colon\mathcal{Q}(\mathcal{X})\to Q$ with
monochromatic red image as well as a $\mathcal{Y}$-good embedding
$\tau\colon\mathcal{O}(\mathcal{Y})\to Q$ with a monochromatic blue image.

We apply an iterative argument in order to find a contradiction. Let
$Y_{0}=\varnothing$ and let $S_{0}=(Y_{0},\leq)$ be the empty ordered set. Now
let $X_{1}\subseteq\mathcal{X}$ such that
$\tau(S_{0})=(X_{1},\underline{S_{0}})$ and let $Y_{1}\in\mathcal{Y}$ such
that $\phi(X_{1})=(X_{1},Y_{1})$. Since $\phi(X_{1})$ is red but $\tau(S_{0})$
is blue, we know that $\phi(X_{1})\neq\tau(S_{0})$ and thus
$Y_{1}\neq\underline{S_{0}}=\varnothing$, so $|Y_{1}|\geq 1$.

Now say that we already defined $X_{1},\dots,X_{i}$, $Y_{0},\ldots,Y_{i}$,
$S_{0},\dots,S_{i-1}$ for some $i\in[k]$ such that

  * •

$S_{i-1}\in\mathcal{O}$ and $\underline{S_{i-1}}=Y_{i-1}$,

  * •

$\tau(S_{i-1})=(X_{i},\underline{S_{i-1}})$,

  * •

$\phi(X_{i})=(X_{i},Y_{i})$, and

  * •

$Y_{i-1}\subset Y_{i}\subseteq\mathcal{Y}$ and $|Y_{i}|\geq i$.

Fix any ordering $S_{i}$ of $Y_{i}$ such that $S_{i-1}<_{\mathcal{O}}S_{i}$.
Such $S_{i}$ exists because $\underline{S_{i-1}}=Y_{i-1}\subset Y_{i}$.

Then let $X_{i+1}$ be such that $\tau(S_{i})=(X_{i+1},\underline{S_{i}})$.
Since $S_{i-1}<_{\mathcal{O}}S_{i}$ and $\tau$ is an embedding,
$(X_{i},\underline{S_{i-1}})=\tau(S_{i-1})\subseteq\tau(S_{i})=(X_{i+1},\underline{S_{i}})$,
therefore $X_{i}\subseteq X_{i+1}$. Note that
$\phi(X_{i})=(X_{i},\underline{S_{i}})$ is colored red but
$\tau(S_{i})=(X_{i+1},\underline{S_{i}})$ is blue. Therefore $X_{i}\neq
X_{i+1}$, consequently $X_{i}\subset X_{i+1}$ and in particular
$\phi(X_{i})\subset\phi(X_{i+1})$ because $\phi$ is an embedding.

Next let $Y_{i+1}\subseteq\mathcal{Y}$ such that
$\phi(X_{i+1})=(X_{i+1},Y_{i+1})$. Then $Y_{i+1}\supseteq Y_{i}$ and
furthermore, because $(X_{i+1},Y_{i})$ is blue but $\phi(X_{i+1})$ is red,
$Y_{i+1}\neq Y_{i}$. Consequently $Y_{i+1}\supsetneq Y_{i}$, and in particular
$|Y_{i+1}|\geq|Y_{i}|+1\geq i+1$.

Iteratively, we obtain $Y_{k+1}\subseteq\mathcal{Y}$ with $|Y_{i}|\geq k+1$, a
contradiction to $|\mathcal{Y}|=k$. ∎

##  4 Random coloring with many blue shrubs

We shall provide a coloring that will give us a lower bound on
$R(\Lambda,Q_{n})$. Note that we do not provide an explicit construction but
only prove the existence of such a coloring.

######  Theorem 18.

Let $N\in\mathbb{N}$ be sufficiently large and
$k=\frac{10}{216}\frac{N}{\ln(N)}$. Consider the Boolean lattice
$Q=\mathcal{Q}([N])$. Then for sufficiently large $N$, there exists a blue/red
coloring of $Q$ which contains no blue copy of $\Lambda$ and such that for
each $\mathcal{Y}\in\binom{[N]}{k}$, there is a blue $\mathcal{Y}$-shrub in
$Q$.

###### Proof of Theorem 18.

Let $\alpha=21.6$ and $\beta=0.134$. Let $N\in\mathbb{N}$ and
$k=\frac{1}{\alpha}\frac{N}{\ln(N)}$, let $Q=\mathcal{Q}([N])$.

The idea of the proof is to construct a $\mathcal{Y}$-shrub, denoted
$\mathcal{P}_{\mathcal{Y}}$, for every $\mathcal{Y}\in\binom{[N]}{k}$, with an
additional property so that the selected shrubs are independent. Since each
shrub does not contain a copy of $\Lambda$, it implies that the independent
union of all the $\mathcal{P}_{\mathcal{Y}}$’s also does not contain a copy of
$\Lambda$. We obtain these shrubs by randomly choosing a
$\mathcal{Y}$-framework for every $\mathcal{Y}\in\binom{[N]}{k}$ and then
constructing a $\mathcal{Y}$-shrub based on each of them. Afterwards we define
a coloring where every vertex in each constructed shrub is colored blue and
the remaining vertices red.

A $\mathcal{Y}$-framework of $\mathcal{Y}\in\binom{[N]}{k}$ is a $4$-tuple
$(\mathcal{Y},A_{\mathcal{Y}},Z_{\mathcal{Y}},X_{\mathcal{Y}})$ such that

  * •

$\mathcal{Y}$, $A_{\mathcal{Y}}$ $Z_{\mathcal{Y}}$ are pairwise disjoint and
$\mathcal{Y}\cup A_{\mathcal{Y}}\cup Z_{\mathcal{Y}}=[N]$,

  * •

$|A_{\mathcal{Y}}|=\tfrac{3}{2}k\ln k-k$,

  * •

$X_{\mathcal{Y}}\subseteq Z_{\mathcal{Y}}$.

A $\mathcal{Y}$-framework is random if

  * •

$A_{\mathcal{Y}}\in\binom{[N]\backslash\mathcal{Y}}{\tfrac{3}{2}k\ln k-k}$ is
chosen uniformly at random, and

  * •

each element of $Z_{\mathcal{Y}}=[N]\backslash(\mathcal{Y}\cup
A_{\mathcal{Y}})$ is included in $X_{\mathcal{Y}}$ independently at random
with probability $\frac{1}{2}$.

Now draw a random $\mathcal{Y}$-framework for every
$\mathcal{Y}\in\binom{[N]}{k}$. Observe that by choice of $k$, $k\ln
k=\frac{N}{\alpha}\cdot\frac{\ln(N)-\ln(\alpha)-\ln\ln(N)}{\ln(N)}$, so
$\frac{20N}{21\alpha}\leq k\ln k\leq\frac{N}{\alpha}$. Since
$|Z_{\mathcal{Y}}|=N-\tfrac{3}{2}k\ln k$, we have
$(1-\frac{3}{2\alpha})N\leq|Z_{\mathcal{Y}}|\leq(1-\frac{10}{7\alpha})N$.

Claim 1. W.h.p. for every $\mathcal{Y}_{1},\mathcal{Y}_{2}\in\binom{[N]}{k}$
with $\mathcal{Y}_{1}\neq\mathcal{Y}_{2}$, $|X_{\mathcal{Y}_{1}}\cap
Z_{\mathcal{Y}_{2}}|\geq\beta N$.
Consider some arbitrary $\mathcal{Y}_{1},\mathcal{Y}_{2}\in\binom{[N]}{k}$,
$\mathcal{Y}_{1}\neq\mathcal{Y}_{2}$. Observe that
$(1-\frac{3}{\alpha})N\leq|Z_{\mathcal{Y}_{1}}\cap
Z_{\mathcal{Y}_{2}}|\leq|Z_{\mathcal{Y}}|\leq(1-\frac{10}{7\alpha})N$. In a
random $\mathcal{Y}$-framework, each element of $Z_{\mathcal{Y}_{1}}\cap
Z_{\mathcal{Y}_{2}}$ is contained in $X_{\mathcal{Y}_{1}}\cap
Z_{\mathcal{Y}_{2}}$ independently with probability $\frac{1}{2}$.
Consequently, $|X_{\mathcal{Y}_{1}}\cap
Z_{\mathcal{Y}_{1}}|\sim\text{Bin}(|Z_{\mathcal{Y}_{1}}\cap
Z_{\mathcal{Y}_{2}}|,\frac{1}{2})$ and $\mathbb{E}(|X_{\mathcal{Y}_{1}}\cap
Z_{\mathcal{Y}_{1}}|)=\frac{1}{2}|Z_{\mathcal{Y}_{1}}\cap
Z_{\mathcal{Y}_{2}}|$. We have $1-\frac{3}{\alpha}\geq 2\beta$. In addition,
$\frac{\big{(}\frac{1}{2}-\frac{3}{2\alpha}-\beta\big{)}^{2}}{1-\frac{10}{7\alpha}}>\frac{2}{\alpha}$,
thus there exist some $\epsilon>0$ such that
$\frac{\big{(}\frac{1}{2}-\frac{3}{2\alpha}-\beta\big{)}^{2}}{1-\frac{10}{7\alpha}}\geq\epsilon+\frac{2}{\alpha}$.
Applying Chernoff’s inequality gives

$\displaystyle\mathbb{P}(|X_{\mathcal{Y}_{1}}\cap
Z_{\mathcal{Y}_{2}}|\leq\beta N)$ $\displaystyle=$
$\displaystyle\mathbb{P}\left(|X_{\mathcal{Y}_{1}}\cap
Z_{\mathcal{Y}_{2}}|\leq\frac{|Z_{\mathcal{Y}_{1}}\cap
Z_{\mathcal{Y}_{2}}|}{2}-\left(\frac{|Z_{\mathcal{Y}_{1}}\cap
Z_{\mathcal{Y}_{2}}|}{2}-\beta N\right)\right)$ $\displaystyle\leq$
$\displaystyle\exp\left(-\frac{\big{(}\frac{|Z_{\mathcal{Y}_{1}}\cap
Z_{\mathcal{Y}_{2}}|}{2}-\beta N\big{)}^{2}}{|Z_{\mathcal{Y}_{1}}\cap
Z_{\mathcal{Y}_{2}}|}\right)$ $\displaystyle\leq$
$\displaystyle\exp\left(-\frac{\big{(}(\frac{1}{2}-\frac{3}{2\alpha})-\beta\big{)}^{2}}{(1-\frac{10}{7\alpha})}\cdot
N\right)$ $\displaystyle\leq$
$\displaystyle\exp\left(-\left(\frac{2}{\alpha}+\epsilon\right)\cdot
N\right).$

Let $E_{1}$ be the event that for some distinct
$\mathcal{Y}_{1},\mathcal{Y}_{2}\in\binom{[N]}{k}$, $|X_{\mathcal{Y}_{1}}\cap
Z_{\mathcal{Y}_{2}}|\leq\beta N$. Then

$\displaystyle\mathbb{P}(E_{1})$ $\displaystyle=$
$\displaystyle\binom{N}{k}\left(\binom{N}{k}-1\right)\mathbb{P}(|X_{\mathcal{Y}_{1}}\cap
Z_{\mathcal{Y}_{2}}|\leq\beta N)$ $\displaystyle\leq$ $\displaystyle
N^{2k}\exp\left(-\left(\frac{2}{\alpha}+\epsilon\right)\cdot N\right)$
$\displaystyle\leq$
$\displaystyle\exp\left(\frac{2N\ln(N)}{\alpha\ln(N)}-\left(\frac{2}{\alpha}+\epsilon\right)\cdot
N\right)$ $\displaystyle=$ $\displaystyle\exp(-\epsilon N)\to 0,\mbox{ as
}N\to\infty.$

This proves Claim 1.

Claim 2. W.h.p. for every $\mathcal{Y}_{1},\mathcal{Y}_{2}\in\binom{[N]}{k}$
with $\mathcal{Y}_{1}\neq\mathcal{Y}_{2}$, $X_{\mathcal{Y}_{1}}\cap
Z_{\mathcal{Y}_{2}}\not\subseteq X_{\mathcal{Y}_{2}}$.
We can suppose that the collection of random frameworks fulfills the property
of Claim 1. Let $\mathcal{Y}_{1},\mathcal{Y}_{2}\in\binom{[N]}{k}$ be such
that $\mathcal{Y}_{1}\neq\mathcal{Y}_{2}$. Note that each element of
$X_{\mathcal{Y}_{1}}\cap Z_{\mathcal{Y}_{2}}$ is contained in
$X_{\mathcal{Y}_{2}}$ with probability $\frac{1}{2}$. Thus,

$\mathbb{P}(X_{\mathcal{Y}_{1}}\cap Z_{\mathcal{Y}_{2}}\subseteq
X_{\mathcal{Y}_{2}})=\left(\frac{1}{2}\right)^{|X_{\mathcal{Y}_{1}}\cap
Z_{\mathcal{Y}_{2}}|}\leq 2^{-\beta N}.$

Let $E_{2}$ be the event that there exist
$\mathcal{Y}_{1},\mathcal{Y}_{2}\in\binom{[N]}{k}$ with
$\mathcal{Y}_{1}\neq\mathcal{Y}_{2}$ such that $X_{\mathcal{Y}_{1}}\cap
Z_{\mathcal{Y}_{2}}\not\subseteq X_{\mathcal{Y}_{2}}$. Since
$\frac{2}{\alpha}<\ln(2)\beta$, we have

$\mathbb{P}(E_{2})\leq N^{2k}\mathbb{P}(X_{\mathcal{Y}_{1}}\cap
Z_{\mathcal{Y}_{2}}\subseteq X_{\mathcal{Y}_{2}})\leq N^{2k}\cdot 2^{-\beta
N}=\exp\left(\frac{2}{\alpha}N-\ln(2)\beta N\right)\to 0,\mbox{ as
}N\to\infty.$

This proves Claim 2.

In particular, there exists a collection of $\mathcal{Y}$-frameworks
$(\mathcal{Y},A_{\mathcal{Y}},Z_{\mathcal{Y}},X_{\mathcal{Y}})$,
$\mathcal{Y}\in\binom{[N]}{k}$, such that for every
$\mathcal{Y}_{1},\mathcal{Y}_{2}\in\binom{[N]}{k}$ with
$\mathcal{Y}_{1}\neq\mathcal{Y}_{2}$, $X_{\mathcal{Y}_{1}}\cap
Z_{\mathcal{Y}_{2}}\not\subseteq X_{\mathcal{Y}_{2}}$.

Note that $|A_{\mathcal{Y}}|=\tfrac{3}{2}k\ln k-k\geq k(\log k+\log\log k)$.
Let $\mathcal{P}^{\prime}_{\mathcal{Y}}$ be a $\mathcal{Y}$-shrub in
$\mathcal{Q}(A_{\mathcal{Y}}\cup\mathcal{Y})$ as guaranteed by Lemma 11. Note
that $\mathcal{P}_{\mathcal{Y}}$’s are not necessarily independent. Let
$\mathcal{P}_{\mathcal{Y}}$ be obtained from
$\mathcal{P}^{\prime}_{\mathcal{Y}}$ by replacing each vertex $W$ of
$\mathcal{P}^{\prime}_{\mathcal{Y}}$ with $W\cup X_{\mathcal{Y}}$. Then
$\mathcal{P}_{\mathcal{Y}}$ is a $\mathcal{Y}$-shrub in $Q$.

Claim 3. Let $\mathcal{Y}_{1},\mathcal{Y}_{2}$ be two distinct $k$-element
subsets of $[N]$. Then $\mathcal{P}_{\mathcal{Y}_{1}}$ and
$\mathcal{P}_{\mathcal{Y}_{2}}$ are independent.
Consider arbitrary elements $U_{i}\in\mathcal{P}_{\mathcal{Y}_{i}}$,
$i\in[2]$. Recall that $X_{\mathcal{Y}_{1}}\cap
Z_{\mathcal{Y}_{2}}\not\subseteq X_{\mathcal{Y}_{2}}$, which implies that
there exists some $z\in(X_{\mathcal{Y}_{1}}\cap Z_{\mathcal{Y}_{2}})\backslash
X_{\mathcal{Y}_{2}}$. Note that $z\in U_{1}$ since
$X_{\mathcal{Y}_{1}}\subseteq U_{1}$. Moreover $z\not\in U_{2}$ since $z\in
Z_{\mathcal{Y}_{2}}\setminus X_{\mathcal{Y}_{2}}$ and
$(Z_{\mathcal{Y}_{2}}\setminus X_{\mathcal{Y}_{2}})\cap U_{2}=\varnothing$. In
particular, $z\in U_{1}\backslash U_{2}$. Similarly, there is an element $w\in
U_{2}\backslash U_{1}$. Thus $U_{1}\not\sim U_{2}$. ∎

We consider the following coloring $c:Q\to\\{\text{blue, red}\\}$. For
$X\subseteq[N]$, let

$c(X)=\begin{cases}\text{blue},\hskip 21.33955pt\mbox{ if
}~{}~{}X\in\bigcup_{\mathcal{Y}\in\binom{[N]}{k}}\mathcal{P}_{\mathcal{Y}},\\\
\text{red},\hskip 22.76228pt\mbox{ otherwise.}\end{cases}$

Note that for every $\mathcal{Y}\in\binom{[N]}{k}$,
$\mathcal{P}_{\mathcal{Y}}$ witnesses that there is a blue $\mathcal{Y}$-shrub
in $Q$. Recall that a $\mathcal{Y}$-shrub is an up-tree. Applying Claim 3 the
blue subposet of $Q$ is a collection of independent up-trees. Then Lemma 5
provides that the coloring $c$ does not contain a blue copy of $\Lambda$. ∎

##  5 Proof of Theorem 3 and Theorem 2

###### Proof of Theorem 3.

Upper Bound:  Let $k=(1+\epsilon)\frac{n}{\log(n)}$ and consider an arbitrary
blue/red colored Boolean lattice $Q$ on ground set $[n+k]$ with no blue copy
of $\Lambda$. Pick any $\mathcal{Y}\in\binom{[n+k]}{k}$ and assume that there
is a blue $\mathcal{Y}$-shrub in $Q$. Recall that the maximal elements of the
$\mathcal{Y}$-shrub form an antichain of size $k!$. Sperner’s theorem provides
that the largest antichain in $Q$ has size
$\binom{n+k}{\lfloor\frac{n+k}{2}\rfloor}$, so
$k!\leq\binom{n+k}{\lfloor\frac{n+k}{2}\rfloor}\leq 2^{n+k}$.

We also have that $k!>\left(\tfrac{k}{e}\right)^{k}=2^{k(\log k-\log e)}.$ By
the choice of $k$, we obtain for sufficiently large $n$,

$k\log k\geq\tfrac{(1+\epsilon)n}{\log
n}\big{(}\log(n)-\log\log(n)\big{)}>\big{(}1+\tfrac{\epsilon}{2}\big{)}n.$

In particular for sufficiently large $n$, $k\log k-k\log e>n+k,$ a
contradiction. Thus $Q$ does not contain a blue $\mathcal{Y}$-shrub for this
fixed $\mathcal{Y}$. Then Corollary 13 yields that there is a red copy of
$Q_{n}$ in $Q$. Consequently, each blue/red colored Boolean lattice of
dimension $n+k$ contains either a blue copy of $\Lambda$ or a red copy of
$Q_{n}$.

Lower Bound:  Let $N$ sufficiently large, let
$k=\frac{10}{216}\frac{N}{\ln(N)}$ and $n=N-k$. Note that $k\leq\frac{N}{2}$,
thus $n\leq N\leq 2n$. Let $Q=\mathcal{Q}([N])$. By Theorem 18 there exists a
coloring of $Q$ with no blue copy of $\Lambda$ such that for every
$\mathcal{Y}\in\binom{[N]}{k}$, there is a blue $\mathcal{Y}$-shrub. By
Corollary 13, there is no red copy of $Q_{n}$ in this coloring, thus
$R(\Lambda,Q_{n})\geq N=n+k$. It remains to bound $k$ in terms of $n$. Indeed,

$k=\frac{10}{216}\cdot\frac{N}{\ln(N)}\geq\frac{10}{216}\cdot\frac{n}{\ln(2n)}=\frac{10}{216}\cdot\frac{\log(e)n}{\log(2n)}\geq\frac{1}{15}\cdot\frac{n}{\log(n)},$

which concludes the proof. ∎

###### Proof of Theorem 2.

The lower bound on $R(P,Q_{n})$ for $P$ containing either $\Lambda$ or $V$
follows from Theorem 3.

Consider now a poset $P$ that contains neither a copy of $\Lambda$ nor a copy
of $V$. By Corollary 6, $P$ is a union of independent chains. Assume that $P$
has $k$ independent chains on at most $\ell$ vertices each. Let $K$ be an even
integer such that $\binom{K}{K/2}\geq k$. Let $\mathcal{Y}$ be a set of size
$K$ and let $\mathcal{X}$ be a set, disjoint from $\mathcal{Y}$ of size
$n+\ell$. Consider an arbitrary coloring of
$\mathcal{Q}(\mathcal{X}\cup\mathcal{Y})$. Assume that there is no red copy of
$Q_{n}$. We shall show that there is a blue copy of $P$.

Let $Y_{1},\ldots,Y_{k}$ form an antichain in $\mathcal{Q}(\mathcal{Y})$, its
existence is guaranteed by Sperner’s theorem. Let $Q^{i}$ be a copy of
$\mathcal{Q}(\mathcal{X})$ obtained as an image of an embedding
$\phi_{i}:\mathcal{Q}(\mathcal{X})\to\mathcal{Q}(\mathcal{X}\cup Y_{i})$,
$\phi_{i}(X)=X\cup Y_{i}$ for any $X\subseteq\mathcal{X}$. Consider the blue
vertices in $Q^{i}$. If there is no blue chain on $\ell$ vertices in $Q^{i}$,
Corollary 9 implies the existence of a red copy of $Q_{n}$ in $Q^{i}$, a
contradiction. Thus for every $i\in[k]$, there is a blue copy $P_{i}$ of a
chain on $\ell$ vertices in $Q^{i}$. Note that for any $A\in Q^{i},B\in
Q^{j}$, $i\neq j$, $A\not\sim B$, since $A\cap\mathcal{Y}=Y_{i}\not\sim
Y_{j}=B\cap\mathcal{Y}$. Thus the $P_{i}$’s are independent chains on $\ell$
vertices each. Their union contains a copy of $P$. This shows that
$R(P,Q_{n})\leq n+K+\ell=n+f(P)$. ∎

Acknowledgments: The authors would like to thank Alexander Riasanovsky for
comments on the manuscript. The research was partially supported by DFG grant
FKZ AX 93/2-1.

## References

  * [1] M. Axenovich, and S. Walzer. Boolean lattices: Ramsey properties and embeddings. Order 34(2), 287–298 (2017).
  * [2] T. Bohman, and F. Peng. A Construction for Cube Ramsey. Preprint, available at arXiv:2102.00317v1, 2021.
  * [3] T. Carroll, and G. Katona. Bounds on Maximal Families of Sets Not Containing Three Sets with $A\cap B\subset C$, $A\not\subset B$. Order 25, 229–236, 2008.
  * [4] F.-H. Chang, D. Gerbner, W.-T. Li, A. Methuku, D. Nagy, B. Patkós, and M. Vizer. Rainbow Ramsey problems for the Boolean lattice. Submitted, preprint available at arXiv:1809.08629v2, 2020.
  * [5] H.-B. Chen, W.-H. Chen, Y.-J. Cheng, W.-T. Li, and C.-A. Liu. Ramsey Properties for V-shaped Posets in the Boolean Lattices. Preprint, available at arXiv:2108.08033v1, 2021.
  * [6] H.-B. Chen, Y.-J. Cheng, W.-T. Li, and C.-A. Liu. The Boolean Rainbow Ramsey Number of Antichains, Boolean Posets and Chains. Electronic Journal of Combinatorics 27(4), 2020.
  * [7] C. Cox, and D. Stolee, Ramsey Numbers for Partially-Ordered Sets. Order 35(3), 557–579, 2018.
  * [8] D. Grósz, A. Methuku, and C. Tompkins. Ramsey numbers of Boolean lattices. Submitted, preprint available at arXiv:2104.02002v1, 2021.
  * [9] B. Keszegh, N. Lemons, R. R. Martin, D. Pálvölgyi, and B. Patkós. Induced and non-induced poset saturation problems. Journal of Combinatorial Theory, Series A (2021).
  * [10] L. Lu, and K. Milans. Set families with forbidden subposets. Journal of Combinatorial Theory, Series A, 136, 126–142, 2015.
  * [11] L. Lu, and C. Thompson. Poset Ramsey Numbers for Boolean Lattices. Order (2021).
  * [12] A. Méroueh. A LYM inequality for induced posets. Journal of Combinatorial Theory, Series A, 155, 398–417, 2018.
  * [13] A. Methuku, and D. Pálvölgyi. Forbidden hypermatrices imply general bounds on induced forbidden subposet problems. Combinatorics, Probability and Computing 26(4), 593–602, 2017.
  * [14] A. Methuku, and C. Tompkins. Exact Forbidden Subposet Results using Chain Decompositions of the Cycle. Electronic Journal of Combinatorics 22(4), 2015.
  * [15] I. Tomon. Forbidden induced subposets of given height. Journal of Combinatorial Theory, Series A, 161, 537–562, 2019.
  * [16] S. Walzer. Ramsey Variant of the 2-Dimension of Posets. In: Master Thesis (2015).