# Poset Ramsey number $R(P,Q_{n})$. II. N-shaped poset

Maria Axenovich 111Karlsruhe Institute of Technology, Karlsruhe, Germany.
Christian Winter 222Karlsruhe Institute of Technology, Karlsruhe, Germany.
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\colon P\rightarrow P^{\prime}$ and for
any $A,B\in P$, $A\leq_{P}B$ if and only if $f(A)\leq_{P^{\prime}}f(B)$. 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 the poset Ramsey number $R(P,Q_{n})$ for a fixed poset $P$ and an
$n$-dimensional Boolean lattice $Q_{n}$, as $n$ grows large. It is known that
$n+c_{1}(P)\leq R(P,Q_{n})\leq c_{2}(P)n$, for positive constants $c_{1}$ and
$c_{2}$. However, there is no poset $P$ known, for which
$R(P,Q_{n})>(1+\epsilon)n$, for $\epsilon>0$. This paper is devoted to a new
method for finding upper bounds on $R(P,Q_{n})$ using a duality between copies
of $Q_{n}$ and sets of elements that cover them, referred to as blockers. We
prove several properties of blockers and their direct relation to the Ramsey
numbers. Using these properties we show that
$R(\mathcal{N},Q_{n})=n+\Theta(n/\log n)$, for a poset $\mathcal{N}$ with four
elements $A,B,C,$ and $D$, such that $A<C$, $B<D$, $B<C$, and the remaining
pairs of elements are incomparable.

##  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{Z}$, let $\mathcal{Q}(\mathcal{Z})$ be the Boolean
lattice of dimension $|\mathcal{Z}|$ on a ground set $\mathcal{Z}$, i.e. the
poset consisting of all subsets of $\mathcal{Z}$ 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$. When
clear from context, we shall write $A\leq B$ instead of $A\leq_{P}B$, and
$A<B$ when $A\leq B$ and $A\neq B$. When $A$ and $B$ are not comparable, we
write $A\parallel B$. The elements of $P$ are often called vertices.

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 (induced) copy of a poset $P_{1}$ in $P_{2}$ is
an induced subposet $P^{\prime}$ of $P_{2}$, isomorphic to $P_{1}$. We shall
be considering three special posets: $\mathcal{V}$,
$\mathrel{\rotatebox[origin={c}]{180.0}{$\mathcal{V}$}}$, and $\mathcal{N}$,
see Figure 1. The poset $\mathcal{V}$ has three vertices $A,B,$ and $C$,
$C<A$, $C<B$, and $A\parallel B$. The poset
$\mathrel{\rotatebox[origin={c}]{180.0}{$\mathcal{V}$}}$ has three vertices
$A,B,$ and $C$, $C>A$, $C>B$, and $A\parallel B$. The poset $\mathcal{N}$ has
four vertices $A,B,C,D$ and relations $A<C$, $B<D$, $B<C$, $A\parallel B$,
$A\parallel D$, and $C\parallel D$.

Figure 1:  Hasse diagrams of posets $\mathcal{V}$,
$\mathrel{\rotatebox[origin={c}]{180.0}{$\mathcal{V}$}}$, and $\mathcal{N}$

Extremal properties of posets and their induced subposets have been
investigated in recent years and mirror similar concepts in graphs. Carroll
and Katona [4] initiated the consideration of so called Turán-type problems
for induced subposets. Most notable is a result by Methuku and Pálvölgyi [15]
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 [12], and Méroueh [14]. Further Turán-type results are, for
example, given by Methuku and Tompkins [16], and Tomon [18]. 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. [11].

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 [20], Axenovich and Walzer [1], Cox and
Stolee [8], Lu and Thompson [13], Bohman and Peng [3]. It should be
highlighted that the upper bound on $R(Q_{n},Q_{n})$ shows that $R(P,Q)$ is
well-defined for any $P$ and $Q$ because any poset is contained as a copy in a
Boolean lattice $Q_{n}$ for sufficiently large $n$.

One subject of research on poset Ramsey numbers is the off-diagonal setting
$R(P,Q_{n})$ for a fixed poset $P$ and large $n$. As general bounds the first
author and Walzer [1] showed the following. The height $h(P)$ of a poset $P$
is defined as the size of the longest chain in $P$. The $2$-dimension
$\dim_{2}(P)$ of a poset $P$ is the dimension of the smallest Boolean lattice
containing a copy of $P$. It is an easy observation that the $2$-dimension is
well-defined for any $P$.

######  Proposition 1 (Axenovich-Walzer [1]).

Let $P$ be a fixed poset. Then

$n+h(P)-1\leq R(P,Q_{n})\leq h(P)n+\dim_{2}(P).$

Here, the lower bound is trivial and is obtained by a coloring of
$Q_{n+h(P)-1}$ in which all vertices in each layer $\\{X\in
Q_{n+h(P)-1}:|X|=\ell\\}$, $\ell\leq n+h(P)-1$, have the same color, red or
blue, and there are $n$ red layers and $h(P)-1$ blue layers.

For the off-diagonal setting $R(Q_{m},Q_{n})$ with $m$ fixed and $n$ large, an
exact result is only known if $m=1$. It is easy to see that
$R(Q_{1},Q_{n})=n+1$. For $m=2$, it was shown in [1] that $R(Q_{2},Q_{n})\leq
2n+2$. This was improved by Lu and Thompson [13] to
$R(Q_{2},Q_{n})\leq(5/3)n+2$, and by Grósz, Methuku, and Tompkins [10] who
showed for $\epsilon>0$ and $n\in\mathbb{N}$ being sufficiently large:
$n+3\leq R(Q_{2},Q_{n})\leq n+\frac{(2+\epsilon)n}{\log n}.$ Finally, the
present authors [2] proved a lower bound asymptotically matching the upper
one:

######  Theorem 2 (Grosz-Methuku-Tompkins [10], Axenovich-Winter [2]).

$R(Q_{2},Q_{n})=n+\Theta\big{(}\tfrac{n}{\log n}\big{)}.$

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

It is unknown whether there exists a poset $P$ such that
$R(P,Q_{n})\geq(1+c)n$ for some $c>0$. Therefore it is natural to consider the
value of $R(P,Q_{n})-n$ and determine its asymptotic behaviour. We say that a
tight bound on $R(P,Q_{n})$ is a function $f(n)$ such that
$R(P,Q_{n})=n+\Theta(f(n))$. A tight bound is only known for a handful of
posets, see for example Theorem 2, and Winter [21].

A poset is trivial if it does not contain a copy of either $\mathcal{V}$ or
$\mathrel{\rotatebox[origin={c}]{180.0}{$\mathcal{V}$}}$. Otherwise we refer
to it as non-trivial. For trivial posets $P$ the trivial lower bound is
asymptotically tight.

######  Theorem 3 (Axenovich-Winter [2]).

If $P$ is a trivial poset, then $R(P,Q_{n})=n+c(P)$ where $c(P)$ is a constant
only depending on $P$. If $P$ is a non-trivial poset, then $R(P,Q_{n})\geq
R(\mathcal{V},Q_{n})\geq n+\frac{n}{15\log n}$.

For non-trivial posets $P$, there are only two known approaches to find the
upper bound of a tight bound on $R(P,Q_{n})$. The first was introduced by
Grosz, Methuku and Tompkins [10] for an upper bound on $R(Q_{2},Q_{n})$ and is
based on the following idea. In a blue/red coloring of the host lattice, there
is either a red copy of $Q_{n}$ (and we are done) or there are many blue
chains. Then using these chains counting arguments can be applied to force a
particular monotonically blue structure.

An alternative approach is given in [2] by the present authors for proving an
upper bound on $R(\mathcal{V},Q_{n})$. With a careful analysis of the blue
subposet of a hosting lattice with forbidden red $Q_{n}$ one can obtain much
more information than the existence of many chains. In this paper we will
elaborate on the second approach and formulate the central, intermediate step
as a theorem for general $P$. This approach involves so-called blockers,
posets that contain a vertex from each copy of $Q_{n}$ from a special, easier
to analyse subclass. We show in Theorem 9 that extremal properties of $P$-free
blockers immediately give an upper bound on $R(P,Q_{n})$. Our result on
$\mathcal{N}$-poset then follows:

######  Theorem 4.

$n+\frac{n}{15\log n}\leq R(\mathcal{N},Q_{n})\leq n+\frac{(1+o(1))n}{\log
n}.$

Here, the lower bound follows immediately from Theorem 3, so the focus of this
paper is on the upper bound.

The paper is structured as follows. In Section 2 main definitions and basic
results are given. Section 3 deals with the main tool used - blockers. In
Section 4 a proof of Theorem 4 is given.

##  2 Main definitions and tools

A vertex $Z$ of a poset $\mathcal{F}$ is a minimum of $\mathcal{F}$ if it is
the unique minimal element of $\mathcal{F}$, i.e. $Z\leq F$ for every
$F\in\mathcal{F}$. Similarly, a maximum of $\mathcal{F}$ is a unique maximal
vertex of $\mathcal{F}$. Given a fixed poset $P$, a poset $\mathcal{F}$ is
$P$-free if it contains no (induced) copy of $P$. Let $\mathcal{X}$ and
$\mathcal{Y}$ be disjoint sets. For a subposet
$\mathcal{F}\subseteq\mathcal{Q}(\mathcal{Y})$, the $\mathcal{X}$-shift of
$\mathcal{F}$ is the poset $\mathcal{F}^{\prime}$ with vertices
$\\{Y\cup\mathcal{X}:Y\in\mathcal{F}\\}$ ordered by inclusion. Note that
$\mathcal{F}^{\prime}$ is isomorphic to $\mathcal{F}$.

Let $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ be two disjoint posets. The
parallel composition of $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ is the poset
on vertices $\mathcal{F}_{1}\cup\mathcal{F}_{2}$ such that pairs of vertices
in $\mathcal{F}_{1}$, as well as pairs of vertices in $\mathcal{F}_{2}$ are
comparable if and only if they are likewise comparable in $\mathcal{F}_{1}$ or
$\mathcal{F}_{2}$, respectively, and any two $F_{1}\in\mathcal{F}_{1}$ and
$F_{2}\in\mathcal{F}_{2}$ are incomparable. In the literature this poset is
also referred to as the independent union of $\mathcal{F}_{1}$ and
$\mathcal{F}_{2}$. If for a poset $\mathcal{F}$ there exists a partition
$\mathcal{F}=\mathcal{F}_{1}\cup\mathcal{F}_{2}$ into non-empty subposets
$\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ such that $\mathcal{F}$ is the
parallel composition of $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$, we say that
$\mathcal{F}$ is disconnected. Otherwise we say that $\mathcal{F}$ is
connected.

A weak homomorphism of a poset $\mathcal{F}_{1}$ into another poset
$\mathcal{F}_{2}$ is a function $\phi\colon\mathcal{F}_{1}\to\mathcal{F}_{2}$
such that for any two $A,B\in\mathcal{F}_{1}$ with $A\leq_{\mathcal{F}_{1}}B$,
we have $\phi(A)\leq_{\mathcal{F}_{2}}\phi(B)$. Similarly, a function
$\phi\colon\mathcal{F}_{1}\to\mathcal{F}_{2}$ is a strong homomorphism if for
any $A,B\in\mathcal{F}_{1}$, $A\leq_{\mathcal{F}_{1}}B$ if and only if
$\phi(A)\leq_{\mathcal{F}_{2}}\phi(B)$. An injective weak [strong]
homomorphism is a weak [strong] embedding of $\mathcal{F}_{1}$ into
$\mathcal{F}_{2}$. Here we exclusively consider strong embeddings and weak
homomorphisms, so we usually simply refer to them as “embeddings” and
“homomorphisms”, respectively.

Throughout this paper, we consider a set $\mathcal{Z}$ as the ground set of
our hosting lattice $\mathcal{Q}(\mathcal{Z})$ where $|\mathcal{Z}|=N$ for
some integer $N$. We then partition $\mathcal{Z}$ into two disjoint sets
$\mathcal{X}$ and $\mathcal{Y}$, $|\mathcal{Y}|\neq\varnothing$, such that
$|\mathcal{X}|=n$ and $|\mathcal{Y}|=k$ for some integers $n$ and $k$, i.e.
$N=n+k$. A (strong) embedding
$\psi\colon\mathcal{Q}(\mathcal{X})\to\mathcal{Q}(\mathcal{Z})$ is
$\mathcal{X}$-good if for every $X\subseteq\mathcal{X}$,
$\psi(X)\cap\mathcal{X}=X$. We say that a copy $Q$ of $Q_{n}$ in
$\mathcal{Q}(\mathcal{Z})$ is $\mathcal{X}$-good if there exists an
$\mathcal{X}$-good embedding of $\mathcal{Q}(\mathcal{X})$ with image $Q$. See
Figure 2 (a) for a $\\{1,2\\}$-good copy of $Q_{2}$ in
$\mathcal{Q}(\\{1,2,x_{1},x_{2}\\})$. Moreover, we say that $\mathcal{X}$ is a
defining set for a copy of $Q_{n}$ if this copy is $\mathcal{X}$-good. One of
the main structural observations we have is the following:

######  Lemma 5 (Axenovich-Walzer [1]).

Let $n\in\mathbb{N}$. Any copy of $Q_{n}$ in $\mathcal{Q}(\mathcal{Z})$ is
$\mathcal{X}$-good for some subset $\mathcal{X}\subseteq\mathcal{Z}$ with
$|\mathcal{X}|=n$.

We shall also need some definitions to describe $\mathcal{N}$-free posets. Let
$\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ be two disjoint posets. The series
composition of $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$, $\mathcal{F}_{1}$
below $\mathcal{F}_{2}$, is the poset on vertices
$\mathcal{F}_{1}\cup\mathcal{F}_{2}$, where pairs of vertices in
$\mathcal{F}_{1}$, as well as pairs of vertices in $\mathcal{F}_{2}$ are
comparable if and only if they are likewise comparable in $\mathcal{F}_{1}$ or
$\mathcal{F}_{2}$, respectively, and $F_{1}<F_{2}$ for any
$F_{1}\in\mathcal{F}_{1}$ and $F_{2}\in\mathcal{F}_{2}$. We usually refer to
this poset as the series decomposition of $\mathcal{F}_{1}$ below
$\mathcal{F}_{2}$. A poset is series-parallel if either it is a $1$-element
poset or it is obtained by series composition or parallel composition of two
series-parallel posets. Valdes [19] showed the following characterization.

######  Theorem 6 (Valdes [19]).

A non-empty poset is $\mathcal{N}$-free if and only if it is series-parallel.

##  3 $\mathcal{Y}$-blockers

###  3.1 Definition and examples of $\mathcal{Y}$-blockers

Outline of the main idea. The definition of $R(P,Q_{n})$ implies that there is
a coloring of $Q(\mathcal{Z})$, $|\mathcal{Z}|\leq R(P,Q_{n})-1$, in blue and
red such that the blue vertices “cover” all copies of $Q_{n}$, i.e. there is a
blue vertex in each copy of $Q_{n}$ and there is no copy of $P$ having only
blue vertices, i.e. the set of blue vertices is $P$-free. We shall classify
all copies of $Q_{n}$ according to their defining sets and consider the set of
only those blue vertices that “cover” copies of $Q_{n}$ with a specific fixed
defining set $\mathcal{X}$. We refer to the poset induced by blue vertices as
a $\mathcal{Y}$-blocker, where $\mathcal{Y}=\mathcal{Z}\setminus\mathcal{X}$.
We shall derive several properties of $\mathcal{Y}$-blockers in general and
those that are $P$-free and will bound $R(P,Q_{n})$ in terms of blockers. This
generalises an approach used in [2], where
${\mathrel{\rotatebox[origin={c}]{180.0}{$\mathcal{V}$}}}$-free
$\mathcal{Y}$-blockers were considered and called $\mathcal{Y}$-shrubs.

######  Definition 7.

Let $\mathcal{Y}$ and $\mathcal{Z}$ be two non-empty sets such that
$\mathcal{Y}\subseteq\mathcal{Z}$. A $\mathcal{Y}$-blocker in
$\mathcal{Q}(\mathcal{Z})$ is a subposet $\mathcal{F}$ in
$\mathcal{Q}(\mathcal{Z})$ which contains a vertex from every
$\mathcal{X}$-good copy of $\mathcal{Q}(\mathcal{X})$, where
$\mathcal{X}=\mathcal{Z}\setminus\mathcal{Y}$. We say that a
$\mathcal{Y}$-blocker $\mathcal{F}$ in $\mathcal{Q}(\mathcal{Z})$ is critical
if for any vertex $F\in\mathcal{F}$ the subposet $\mathcal{F}\setminus\\{F\\}$
is not a $\mathcal{Y}$-blocker in $\mathcal{Q}(\mathcal{Z})$.

Note that for any $\mathcal{Y}\subseteq\mathcal{Z}$, a $\mathcal{Y}$-blocker
in $\mathcal{Q}(\mathcal{Z})$ exists, for example take
$\mathcal{F}=\mathcal{Q}(\mathcal{Z})$. Later on we consider “thinner”
$\mathcal{Y}$-blockers satisfying special properties, in particular being
$P$-free.

######  Example.

Let $\mathcal{Z}=\\{1,2,x_{1},x_{2}\\}$, $\mathcal{Y}=\\{1,2\\}$ and
$\mathcal{X}=\\{x_{1},x_{2}\\}$. Let $\mathcal{F}$ be the $\\{x_{1}\\}$-shift
of $\mathcal{Q}(\mathcal{Y})$, see Figure 2 (a). Consider an arbitrary
$\mathcal{X}$-good copy $Q$ of $\mathcal{Q}(\mathcal{X})$ in
$\mathcal{Q}(\mathcal{Z})$, with a corresponding $\mathcal{X}$-good embedding
$\psi\colon\mathcal{Q}(\mathcal{X})\to\mathcal{Q}(\mathcal{Z})$. Then
$\psi(\\{x_{1}\\})=\\{x_{1}\\}\cup Y$ for some $Y\subseteq\mathcal{Y}$, and
hence $\psi(\\{x_{1}\\})\in\mathcal{F}$. Thus $\mathcal{F}$ is a
$\mathcal{Y}$-blocker in $\mathcal{Q}(\mathcal{X}\cup\mathcal{Y})$. Figure 2
(b) also depicts a $\mathcal{Y}$-blocker, we shall verify this using Theorem
11.

Figure 2:  Two $\\{1,2\\}$-blockers in $\mathcal{Q}(\\{1,2,x_{1},x_{2}\\})$

###  3.2 General properties of $\mathcal{Y}$-blockers

######  Lemma 8.

  * (i)

A blue/red colored Boolean lattice $\mathcal{Q}(\mathcal{Z})$ contains no red
copy of $Q_{n}$ if and only if for each $\mathcal{X}\subseteq\mathcal{Z}$ of
size $|\mathcal{X}|=n$, there is a $\mathcal{Z}\setminus\mathcal{X}$-blocker
with all vertices blue.

  * (ii)

Let $\mathcal{F}$ be a $\mathcal{Y}$-blocker where
$\mathcal{Y}\neq\varnothing$ and let $Y\subseteq\mathcal{Y}$. Then there is a
vertex $Z\in\mathcal{F}$ with $Z\cap\mathcal{Y}=Y$. In particular, if $Z$ is a
minimum of $\mathcal{F}$, then $Z\cap\mathcal{Y}=\varnothing$; and if $Z$ is a
maximum of $\mathcal{F}$, then $Z\cap\mathcal{Y}=\mathcal{Y}$.

  * (iii)

If $\mathcal{F}$ is a $\mathcal{Y}$-blocker, then $|\mathcal{F}|\geq
2^{|\mathcal{Y}|}$.

###### Proof.

Part $(i)$ follows immediately from Lemma 5 and the definition of a
$\mathcal{Y}$-blocker. For $(ii)$, let $\mathcal{F}$ be a
$\mathcal{Y}$-blocker in $\mathcal{Q}(\mathcal{Z})$ and
$\mathcal{X}=\mathcal{Z}\setminus\mathcal{Y}$. Observe that $\mathcal{F}$
contains a vertex $U$ with $U\cap\mathcal{Y}=Y$ for every
$Y\subseteq\mathcal{Y}$, because otherwise the $\\{Y\\}$-shift of
$\mathcal{Q}(\mathcal{X})$ is an $\mathcal{X}$-good copy of
$\mathcal{Q}(\mathcal{X})$ that does not contain a vertex from $\mathcal{F}$.
Considering $Y=\varnothing$, we have that there is $U\in\mathcal{F}$ such that
$U\cap\mathcal{Y}=\varnothing$. Then a minimum $Z$ of $\mathcal{F}$ has
$\mathcal{Y}$-part $Z\cap\mathcal{Y}\subseteq U\cap\mathcal{Y}=\varnothing$.
Similarly, a maximum $Z$ of $\mathcal{F}$ has $\mathcal{Y}$-part
$Z\cap\mathcal{Y}=\mathcal{Y}$. For $(iii)$, since there are
$2^{|\mathcal{Y}|}$ subsets of $\mathcal{Y}$, part $(ii)$ immediately implies
that $|\mathcal{F}|\geq 2^{|\mathcal{Y}|}$. ∎

######  Theorem 9.

Let $P$ be a poset and let $n\in\mathbb{N}$ be an integer. Then

$R(P,Q_{n})\leq\min\\{N:~{}\text{there is no
}\text{P-free}~{}\text{$\mathcal{Y}$\\!-blocker in }\mathcal{Q}([N])\text{ for
some }\mathcal{Y}\subseteq[N],|\mathcal{Y}|=N-n\\}.$

###### Proof.

Let $N$ be the smallest integer such that for some $\mathcal{Y}\subseteq[N]$,
$|\mathcal{Y}|=N-n$, there is no $P$-free $\mathcal{Y}$-blocker in
$\mathcal{Q}([N])$.

Consider an arbitrarily blue/red colored Boolean lattice $\mathcal{Q}([N])$
and let $\mathcal{B}$ be the induced subposet of $\mathcal{Q}([N])$ consisting
of all blue vertices. We shall show that there is either a blue copy of $P$ or
a red copy of $Q_{n}$ in the coloring of $\mathcal{Q}([N])$. Let
$\mathcal{X}=[N]\setminus\mathcal{Y}$. If in $\mathcal{Q}([N])$ there is a
monochromatic red copy of $Q_{n}$ which is $\mathcal{X}$-good, the proof is
complete. Otherwise each $\mathcal{X}$-good copy of $Q_{n}$ contains a blue
vertex, i.e. the blue subposet $\mathcal{B}$ is a $\mathcal{Y}$-blocker. By
the definition of $N$, $\mathcal{B}$ is not $P$-free. Thus there is a blue
copy of $P$ in $\mathcal{Q}([N])$.

It remains to show that this minimum is well-defined, i.e. we shall find an
integer $N$ such that there is no $P$-free $\mathcal{Y}$-blocker in
$\mathcal{Q}([N])$, where $\mathcal{Y}\subseteq[N]$ with $|\mathcal{Y}|=N-n$.
In order to show this, we bound the size $|\mathcal{F}|$ of a $P$-free
$\mathcal{Y}$-blocker $\mathcal{F}$ in $\mathcal{Q}([N])$ from above and from
below. On the one hand, by a result of Methuku and Pálvölgyi [15] we find that
the size of the $P$-free subposet $\mathcal{F}\subseteq\mathcal{Q}([N])$ is
bounded by

$|\mathcal{F}|\leq c(P)\binom{N}{N/2}\leq\frac{c^{\prime}(P)\cdot
2^{N}}{\sqrt{N/2}},$

where $c$ and $c^{\prime}$ are constants depending only on $P$. On the other
hand, Lemma 8 provides that

$|\mathcal{F}|\geq 2^{|\mathcal{Y}|}=2^{N-n}.$

For sufficiently large $N$, we have that
$\frac{\sqrt{N/2}}{c^{\prime}(P)}>2^{n}$, which implies that there is no
$P$-free $\mathcal{Y}$-blocker $|\mathcal{F}|$ in $\mathcal{Q}([N])$. ∎

######  Definition 10.

For a subposet $\mathcal{F}$ of $\mathcal{Q}(\mathcal{Z})$ and
$\mathcal{Y}\subseteq\mathcal{Z}$, we say that a (weak) homomorphism
$\phi\colon\mathcal{F}\to\mathcal{Q}(\mathcal{Y})$ is $\mathcal{Y}$-hitting if
there exists some $F\in\mathcal{F}$ with $\phi(F)=F\cap\mathcal{Y}$.
Conversely, $\phi$ is $\mathcal{Y}$-avoiding if $\phi(F)\neq F\cap\mathcal{Y}$
for every $F\in\mathcal{F}$.

Remark.  In the following we show an equivalence between the existence of a
$\mathcal{Y}$-blocker and the existence of a $\mathcal{Y}$-avoiding
homomorphism. One can think of the homomorphism
$\phi\colon\mathcal{F}\to\mathcal{Q}(\mathcal{Y})$ as a “recipe” encoding an
embedding function $\psi$ which corresponds to an $\mathcal{X}$-good copy of
$Q_{n}$ in $\mathcal{Q}(\mathcal{X}\cup\mathcal{Y})$. Recall that a
$\mathcal{Y}$-blocker is defined as a poset which has a vertex in common with
every $\mathcal{X}$-good copy of $Q_{n}$, therefore every “recipe” $\phi$
forces a “collision” with $\mathcal{F}$ in a vertex $F\in\mathcal{F}$ with
$\phi(F)=F\cap\mathcal{Y}$. However, there is no $1$-to-$1$ correspondence
between functions $\phi$ and $\psi$, and the presented constructions building
$\psi$ from $\phi$ as well as $\phi$ from $\psi$ are not inverse of each
other.

######  Theorem 11.

Let $\mathcal{Y}$ be a non-empty subset of a set $\mathcal{Z}$. A subposet
$\mathcal{F}$ of a Boolean lattice $\mathcal{Q}(\mathcal{Z})$ is a
$\mathcal{Y}$-blocker if and only if every (weak) homomorphism
$\phi\colon\mathcal{F}\to\mathcal{Q}(\mathcal{Y})$ is $\mathcal{Y}$-hitting.

######  Example.

Let $\mathcal{Z}=\\{1,2,x_{1},x_{2}\\}$ and $\mathcal{Y}=\\{1,2\\}$. In the
Boolean lattice $\mathcal{Q}(\\{1,2,x_{1},x_{2}\\})$ consider the subposet
$\mathcal{F}$ on vertices
$\varnothing,\\{1,x_{1}\\},\\{1,2,x_{1}\\},\\{2,x_{2}\\},\\{1,2,x_{2}\\}$, see
Figure 2 (b). Then $\mathcal{F}$ is a $\\{1,2\\}$-blocker. In order to prove
this, we can use Theorem 11. Assume towards a contradiction that there is a
homomorphism $\phi\colon\mathcal{F}\to\mathcal{Q}(\mathcal{Y})$ such that for
every $F\in\mathcal{F}$ we have $\phi(F)\neq F\cap\mathcal{Y}$. Then
$\phi(\varnothing)\cap\mathcal{Y}\neq\varnothing$, say without loss of
generality $1\in\phi(\varnothing)\cap\mathcal{Y}$. Since $\phi$ is a
homomorphism $\phi(\varnothing)\subseteq\phi(\\{1,x_{1}\\})$, so
$1\in\phi(\\{1,x_{1}\\})\cap\mathcal{Y}$. Now, because
$\phi(\\{1,x_{1}\\})\cap\mathcal{Y}\neq\\{1\\}$, we obtain that
$\phi(\\{1,x_{1}\\})\cap\mathcal{Y}=\\{1,2\\}$. Then using that
$\phi(\\{1,x_{1}\\})\subseteq\phi(\\{1,2,x_{1}\\})$, we obtain
$\phi(\\{1,2,x_{1}\\})\cap\mathcal{Y}=\\{1,2\\}$, a contradiction.

###### Proof of Theorem 11.

Let $\mathcal{Y}\subseteq\mathcal{Z}$ be a non-empty subset and let
$\mathcal{X}=\mathcal{Z}\setminus\mathcal{Y}$. For the first part of the proof
let $\mathcal{F}$ be a subposet in $\mathcal{Q}(\mathcal{Z})$ such that every
homomorphism $\phi\colon\mathcal{F}\to\mathcal{Q}(\mathcal{Y})$ is
$\mathcal{Y}$-hitting. We shall show that $\mathcal{F}$ is a
$\mathcal{Y}$-blocker. Let $Q$ be an arbitrary $\mathcal{X}$-good copy of
$\mathcal{Q}(\mathcal{X})$ in $\mathcal{Q}(\mathcal{Z})$ with a corresponding
$\mathcal{X}$-good embedding
$\psi\colon\mathcal{Q}(\mathcal{X})\to\mathcal{Q}(\mathcal{Z})$. Consider the
function $\phi\colon\mathcal{F}\to\mathcal{Q}(\mathcal{Y})$ given by
$\phi(F):=\psi(F\cap\mathcal{X})\cap\mathcal{Y}$ for each $F\in\mathcal{F}$.
Using the properties of $\psi$, it is easy to see that if $F\subseteq
F^{\prime}$ for $F,F^{\prime}\in\mathcal{F}$, then
$\phi(F)\subseteq\phi(F^{\prime})$, so $\phi$ is a homomorphism. Thus $\phi$
is $\mathcal{Y}$-hitting and we find some $Z\in\mathcal{F}$ with
$\phi(Z)=Z\cap\mathcal{Y}$. Then
$\psi(Z\cap\mathcal{X})\cap\mathcal{Y}=\phi(Z)=Z\cap\mathcal{Y}$. Since $\psi$
is $\mathcal{X}$-good, we know that
$\psi(Z\cap\mathcal{X})\cap\mathcal{X}=Z\cap\mathcal{X}$. Therefore
$\psi(Z\cap\mathcal{X})=Z$. Since the image of $\psi$ is $Q$, we obtain
$Z=\psi(Z\cap\mathcal{X})\in Q$, thus $\mathcal{F}$ and $Q$ have the vertex
$Z$ in common.

From now on let $\mathcal{F}$ be a subposet in $\mathcal{Q}(\mathcal{Z})$ for
which there exists a $\mathcal{Y}$-avoiding homomorphism
$\phi\colon\mathcal{F}\to\mathcal{Q}(\mathcal{Y})$. We shall show that
$\mathcal{F}$ is not a $\mathcal{Y}$-blocker. For that we shall construct an
$\mathcal{X}$-good embedding
$\psi\colon\mathcal{Q}(\mathcal{X})\to\mathcal{Q}(\mathcal{Z})$ such that the
image of $\psi$ does not contain a vertex from $\mathcal{F}$. Fix some
$X\in\mathcal{Q}(\mathcal{X})$, now we define $\psi(X)$ using an iteration:
Informally spoken, in step $i$ we introduce a set
$f_{i}(X)\subseteq\mathcal{Y}$ and check whether $X\cup f_{i}(X)$ is a
“feasible” choice for $\psi(X)$; and if not, we extend $f_{i}(X)$ to its
strict superset $f_{i+1}(X)$ and repeat.

Let $f_{0}(X)=\varnothing$. For $i\in\mathbb{N}$, let
$\mathcal{F}_{i}(X)=\\{Z\in\mathcal{F}:Z\subseteq X\cup f_{i-1}(X)\\}$ be the
down-set of $X\cup f_{i-1}(X)$ and let
$f_{i}(X)=\bigcup_{Z\in\mathcal{F}_{i}(X)}\phi(Z)$. Clearly
$f_{i}(X)\subseteq\mathcal{Y}$. Note that $\varnothing=f_{0}(X)\subseteq
f_{1}(X)$, thus $\mathcal{F}_{1}(X)\subseteq\mathcal{F}_{2}(X)$ and so
$f_{1}(X)\subseteq f_{2}(X)$. Iteratively, we obtain that
$\mathcal{F}_{i}(X)\subseteq\mathcal{F}_{i+1}(X)$ and $f_{i}(X)\subseteq
f_{i+1}(X)\subseteq\mathcal{Y}$, see Figure 3 (a). Thus after finitely many
steps $f_{j}(X)=f_{j+1}(X)$ for some $j\in\mathbb{N}$, i.e. this set is
“feasible”, and let $j(X)$ be the minimal such index $j$. Observe that
$f_{j(X)}(X)=f_{j(X)+1}(X)=f_{j(X)+2}(X)=\dots$ as
$\mathcal{F}_{j(X)+1}(X)=\mathcal{F}_{j(X)+2}(X)=\dots$. We set
$\psi(X):=X\cup f_{j(X)}(X).$

Figure 3: (a) Construction of $\psi(X)$, (b) Iteration in Claim 1.

Claim 1. $\psi$ is an $\mathcal{X}$-good embedding of
$\mathcal{Q}(\mathcal{X})$.
Proof of Claim 1. Note that for every $X\in\mathcal{Q}(\mathcal{X})$, we have
$f_{j(X)}(X)\subseteq\mathcal{Y}$ and so $\psi(X)\cap\mathcal{X}=X$. Thus it
remains to show that $\psi$ is an embedding in order to prove the claim. Let
$X_{1},X_{2}\in\mathcal{Q}(\mathcal{X})$. We shall show that $X_{1}\subseteq
X_{2}$ if and only if $\psi(X_{1})\subseteq\psi(X_{2})$.

First suppose that $X_{1}\subseteq X_{2}$. Then $X_{1}\cup
f_{0}(X)=X_{1}\subseteq X_{2}=X_{2}\cup f_{0}(X)$, so
$\mathcal{F}_{1}(X_{1})\subseteq\mathcal{F}_{1}(X_{2})$. This implies that
$f_{1}(X_{1})\subseteq f_{1}(X_{2})$, so $X_{1}\cup f_{1}(X)\subseteq
X_{2}\cup f_{1}(X)$, see Figure 3 (b). Iteratively,
$\mathcal{F}_{i}(X_{1})\subseteq\mathcal{F}_{i}(X_{2})$ and
$f_{i}(X_{1})\subseteq f_{i}(X_{2})$. We obtain that

$f_{j(X_{1})}(X_{1})=f_{\max\\{j(X_{1}),j(X_{2})\\}}(X_{1})\subseteq
f_{\max\\{j(X_{1}),j(X_{2})\\}}(X_{2})=f_{j(X_{2})}(X_{2}),$

thus $\psi(X_{1})\subseteq\psi(X_{2})$. Now suppose that
$\psi(X_{1})\subseteq\psi(X_{2})$. Then in particular
$X_{1}=\psi(X_{1})\cap\mathcal{X}\subseteq\psi(X_{2})\cap\mathcal{X}=X_{2}$,
so $X_{1}\subseteq X_{2}$.

Claim 2. The image of $\psi$ contains no vertex from $\mathcal{F}$.
Proof of Claim 2. Let $X\in\mathcal{X}$ and assume that
$\psi(X)\in\mathcal{F}$. We shall find a contradiction by considering
$\phi(\psi(X))$. Observe that $\psi(X)=X\cup
f_{j(X)}(X)\in\mathcal{F}_{j(X)+1}(X)$ and so $\phi(\psi(X))\subseteq
f_{j(X)+1}(X)$. Since $\phi$ is $\mathcal{Y}$-avoiding,
$\phi(\psi(X))\neq\psi(X)\cap\mathcal{Y}=f_{j(X)}(X)=f_{j(X)+1}(X)$.
Consequently, there exists an element $a\in
f_{j(X)+1}(X)\setminus\phi(\psi(X))$. By definition of $f_{i}(X)$, we find a
vertex $Z\in\mathcal{F}_{j(X)}(X)\subseteq\mathcal{F}$ with $a\in\phi(Z)$.
Now, since $Z\in\mathcal{F}_{j(X)}(X)$, we obtain that $Z\subseteq X\cup
f_{j(X)}(X)=\psi(X)$ whereas element $a$ witnesses
$\phi(Z)\not\subseteq\phi(\psi(X))$. This contradicts the fact that $\phi$ is
a homomorphism. So, indeed, $\mathcal{F}$ is not a $\mathcal{Y}$-blocker.

This concludes the proof of Theorem 11. ∎

In the following we use the characterization from Theorem 11 to analyse
properties of critical blockers. Recall that for
$\mathcal{Y}\subseteq\mathcal{Z}$, a $\mathcal{Y}$-blocker $\mathcal{F}$ in
$\mathcal{Q}(\mathcal{Z})$ is critical if for any vertex $F\in\mathcal{F}$ the
subposet $\mathcal{F}\setminus\\{F\\}$ is not a $\mathcal{Y}$-blocker in
$\mathcal{Q}(\mathcal{Z})$.

######  Lemma 12.

Let $\mathcal{F}$ be a critical $\mathcal{Y}$-blocker for a non-empty set
$\mathcal{Y}$. Then $\mathcal{F}$ is a connected poset.

###### Proof.

Assume that $\mathcal{F}$ is the parallel composition of two non-empty posets
$\mathcal{F}_{1}$ and $\mathcal{F}_{2}$, i.e. $\mathcal{F}_{1}$ and
$\mathcal{F}_{2}$ are vertex-wise incomparable in $\mathcal{F}$. Then each of
$\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ is not a $\mathcal{Y}$-blocker by
criticality of $\mathcal{F}$. Thus there are $\mathcal{Y}$-avoiding
homomorphisms $\phi_{1}\colon\mathcal{F}_{1}\to\mathcal{Q}(\mathcal{Y})$ and
$\phi_{2}\colon\mathcal{F}_{2}\to\mathcal{Q}(\mathcal{Y})$. Now the function
$\psi:\mathcal{F}\to\mathcal{Q}(\mathcal{Y})$,

$\psi(F)=\begin{cases}\phi_{1}(F)\text{, if }F\in\mathcal{F}_{1}\\\
\phi_{2}(F)\text{, if }F\in\mathcal{F}_{2}.\end{cases}$

is a homomorphism of $\mathcal{F}$ and $\mathcal{Y}$-avoiding. Recall that
$\mathcal{F}$ is a $\mathcal{Y}$-blocker, so this is a contradiction to
Theorem 11. ∎

######  Lemma 13.

Let $\mathcal{F}$ be a critical $\mathcal{Y}$-blocker for a non-empty set
$\mathcal{Y}$. Let $U_{1},U_{2}\in\mathcal{F}$ with $U_{1}\neq U_{2}$. If
either $U_{1}\cap\mathcal{Y}=\varnothing=U_{2}\cap\mathcal{Y}$ or
$U_{1}\cap\mathcal{Y}=\mathcal{Y}=U_{2}\cap\mathcal{Y}$, then $U_{1}$ and
$U_{2}$ are not comparable.

###### Proof.

Assume that $U_{1}\cap\mathcal{Y}=\varnothing=U_{2}\cap\mathcal{Y}$ and
$U_{1}\subseteq U_{2}$. As $\mathcal{F}$ is a critical $\mathcal{Y}$-blocker,
the poset $\mathcal{F}^{\prime}=\mathcal{F}\setminus\\{U_{2}\\}$ is not a
$\mathcal{Y}$-blocker, so by Theorem 11 we find a $\mathcal{Y}$-avoiding
homomorphism $\phi:\mathcal{F}^{\prime}\to\mathcal{Q}(\mathcal{Y})$. Let
$\mathcal{U}=\\{U\in\mathcal{F}^{\prime}\colon U\subseteq U_{2},\ U\neq
U_{2}\\}$, note that $\mathcal{U}\neq\varnothing$, see Figure 4 (a). We extend
$\phi$ to a function $\psi\colon\mathcal{F}\to\mathcal{Q}(\mathcal{Y})$ by
defining

$\psi(F)=\begin{cases}\phi(F),&\text{ if }F\neq U_{2}\\\
\bigcup_{U\in\mathcal{U}}\phi(U),\quad&\text{ if }F=U_{2}.\end{cases}$

In order to reach a contradiction, it remains to show that $\psi$ is a
$\mathcal{Y}$-avoiding homomorphism. We shall show that $\psi$ is a
homomorphism by considering any two $F_{1},F_{2}\in\mathcal{F}$ such that
$F_{1}\subseteq F_{2}$ and verifying that $\psi(F_{1})\subseteq\psi(F_{2})$.
We need to consider cases whether either of $F_{1}$ or $F_{2}$ is equal to
$U_{2}$. We repeatedly use the fact that $\phi$ is a homomorphism:

$\circ$ If $F_{1}\neq U_{2}$ and $F_{2}\neq U_{2}$, then
$\psi(F_{1})=\phi(F_{1})\subseteq\phi(F_{2})=\psi(F_{2})$.

$\circ$ If $F_{1}=U_{2}$, then
$\psi(F_{1})=\psi(U_{2})=\bigcup_{U\in\mathcal{U}}\phi(U)\subseteq\bigcup_{U\in\mathcal{U}}\phi(F_{2})\subseteq\phi(F_{2})=\psi(F_{2})$.
Here we used the property that for any $U\in\mathcal{U}$, $U\subseteq
U_{2}\subseteq F_{2}$.

$\circ$ If $F_{2}=U_{2}$, then
$\psi(F_{1})=\phi(F_{1})\subseteq\bigcup_{U\in\mathcal{U}}\phi(U)=\psi(U_{2})=\psi(F_{2})$.
Here, we used that $F_{1}\in\mathcal{U}$ and thus
$F_{1}\subseteq\bigcup_{U\in\mathcal{U}}U$. Therefore, $\psi$ is a
homomorphism.

To show that $\psi$ is $\mathcal{Y}$-avoiding, we need to show that for any
$F\in\mathcal{F}$, $\psi(F)\neq F\cap\mathcal{Y}$. Consider first
$F\in\mathcal{F}$ with $F\neq U_{2}$, i.e. $F\in\mathcal{F}^{\prime}$. Since
$\phi$ is $\mathcal{Y}$-avoiding, $\phi(F)\neq F\cap\mathcal{Y}$. Since
$\psi(F)=\phi(F)$, we have that $\psi(F)\neq F\cap\mathcal{Y}$. Now, let
$F=U_{2}$. Since $\psi(U_{2})\supseteq\phi(U_{1})$ where $\phi(U_{1})\neq
U_{1}\cap\mathcal{Y}=\varnothing$, we find that
$\psi(U_{2})\neq\varnothing=U_{2}\cap\mathcal{Y}$. We conclude that $\psi$ is
$\mathcal{Y}$-avoiding. This contradicts Theorem 11 and the fact that
$\mathcal{F}$ is a $\mathcal{Y}$-blocker.

Under the assumption that
$U_{1}\cap\mathcal{Y}=\mathcal{Y}=U_{2}\cap\mathcal{Y}$ and $U_{1}\subseteq
U_{2}$, a symmetric proof holds for
$\mathcal{U}=\\{U\in\mathcal{F}\setminus\\{U_{1}\\}\colon U\supseteq U_{1},\
U\neq U_{1}\\}$ and $\psi\colon\mathcal{F}\to\mathcal{Q}(\mathcal{Y})$ with

$\psi(F)=\begin{cases}\phi(F),&\text{ if }F\neq U_{1}\\\
\bigcap_{U\in\mathcal{U}}\phi(U),\quad&\text{ if }F=U_{1}.\end{cases}$

∎

Figure 4: (a) Setting in Lemma 13, (b) Setting in Lemma 14.

######  Lemma 14.

Let $\mathcal{F}$ be a critical $\mathcal{Y}$-blocker where
$\mathcal{Y}\neq\varnothing$. Let
$\mathcal{F}_{1}\subseteq\\{U\in\mathcal{F}:U\cap\mathcal{Y}=\varnothing\\}$
such that $\mathcal{F}$ is a series composition of $\mathcal{F}_{1}$ below
$\mathcal{F}\setminus\mathcal{F}_{1}$, then $|\mathcal{F}_{1}|\leq 1$.
Similarly, let
$\mathcal{F}_{2}\subseteq\\{U\in\mathcal{F}:U\cap\mathcal{Y}=\mathcal{Y}\\}$
such that $\mathcal{F}$ is a series composition of
$\mathcal{F}\setminus\mathcal{F}_{2}$ below $\mathcal{F}_{2}$, then
$|\mathcal{F}_{2}|\leq 1$.

###### Proof.

For the first part, assume towards a contradiction that there are two distinct
vertices $U_{1},U_{2}\in\mathcal{F}_{1}$. Since $\mathcal{F}$ is a critical
$\mathcal{Y}$-blocker, there is a $\mathcal{Y}$-avoiding homomorphism
$\phi\colon\mathcal{F}\setminus\\{U_{2}\\}\to\mathcal{Q}(\mathcal{Y})$. Let
$\psi\colon\mathcal{F}\to\mathcal{Q}(\mathcal{Y})$ such that

$\psi(F)=\begin{cases}\phi(F),\quad&\text{ if }F\neq U_{2}\\\
\phi(U_{1}),&\text{ if }F=U_{2}.\end{cases}$

We shall prove that $\psi$ is a $\mathcal{Y}$-avoiding homomorphism of
$\mathcal{F}$. By Lemma 13, $\mathcal{F}_{1}$ is an antichain. In order to
show that $\psi$ is a homomorphism, we consider two arbitrary
$F_{1},F_{2}\in\mathcal{F}$ with $F_{1}\subseteq F_{2}$ and show that
$\psi(F_{1})\subseteq\psi(F_{2})$.

$\circ$ If $F_{2}=U_{2}$, then in particular $F_{2}\in\mathcal{F}_{1}$ and so
$F_{1}\in\mathcal{F}_{1}$, because $\mathcal{F}$ is a series composition of
$\mathcal{F}_{1}$ below $\mathcal{F}\setminus\mathcal{F}_{1}$. Since
$\mathcal{F}_{1}$ is an antichain, we obtain that $F_{1}=U_{2}=F_{2}$. Then
trivially $\psi(F_{1})=\psi(U_{2})=\psi(F_{2})$.

$\circ$ If $F_{1}=U_{2}$ and $F_{2}\neq U_{2}$, we know that
$F_{2}\in\mathcal{F}\setminus\mathcal{F}_{1}$ because $\mathcal{F}_{1}$ is an
antichain. Then $U_{1}\subseteq F_{2}$. Because $\phi$ is a homomorphism and
by definition of $\psi$, we obtain that
$\psi(U_{2})=\phi(U_{1})\subseteq\phi(F_{2})$.

$\circ$ If $F_{1}\neq U_{2}$ and $F_{2}\neq U_{2}$, then
$\psi(F_{1})=\phi(F_{1})\subseteq\phi(F_{2})=\psi(F_{2})$. Thus $\psi$ is a
homomorphism of $\mathcal{F}$.

For every $F\in\mathcal{F}\setminus\\{U_{2}\\}$, we know that
$\psi(F)=\phi(F)\neq F\cap\mathcal{Y}$. Furthermore,
$\psi(U_{2})=\phi(U_{1})\neq
U_{1}\cap\mathcal{Y}=\varnothing=U_{2}\cap\mathcal{Y}$. Thus $\psi$ is
$\mathcal{Y}$-avoiding, a contradiction.

If we assume that there are distinct $U_{1},U_{2}\in\mathcal{F}_{2}$, a
symmetric argument considering the same function
$\psi\colon\mathcal{F}\to\mathcal{Q}(\mathcal{Y})$,

$\psi(F)=\begin{cases}\phi(F),\quad&\text{ if }F\neq U_{2}\\\
\phi(U_{1}),&\text{ if }F=U_{2}.\end{cases}$

yields a contradiction. ∎

######  Lemma 15.

Let $\mathcal{X}$ and $\mathcal{Y}$ be two disjoint sets with
$|\mathcal{Y}|=1$. Let $\mathcal{F}$ be a critical $\mathcal{Y}$-blocker in
$\mathcal{Q}(\mathcal{X}\cup\mathcal{Y})$. Then $\mathcal{F}$ is a chain
consisting of two vertices $X_{1},X_{2}\cup\mathcal{Y}$, where $X_{1}\subseteq
X_{2}\subseteq\mathcal{X}$.

###### Proof.

Since $|\mathcal{Y}|=1$, we find that for every $Z\in\mathcal{F}$ either
$Z\cap\mathcal{Y}=\varnothing$ or $Z\cap\mathcal{Y}=\mathcal{Y}$. Consider
subposets
$\mathcal{F}_{1}=\\{Z\in\mathcal{F}:~{}Z\cap\mathcal{Y}=\varnothing\\}$ and
$\mathcal{F}_{2}=\\{Z\in\mathcal{F}:~{}Z\cap\mathcal{Y}=\mathcal{Y}\\}$
partitioning $\mathcal{F}$. Lemma 8 provides that
$\mathcal{F}_{1}\neq\varnothing$ and $\mathcal{F}_{2}\neq\varnothing$. By
Lemma 12, $\mathcal{F}$ is connected, so in particular there are two vertices
from $\mathcal{F}_{1}$ and from $\mathcal{F}_{2}$ which are comparable. Let
these vertices be $X_{1}\in\mathcal{F}_{1}$ and
$X_{2}\cup\mathcal{Y}\in\mathcal{F}_{2}$, where
$X_{1},X_{2}\subseteq\mathcal{X}$. Then $X_{1}\subseteq X_{2}\cup\mathcal{Y}$,
so $X_{1}\subseteq X_{2}$.

Next we need to show that $\mathcal{F}=\\{X_{1},X_{2}\cup\mathcal{Y}\\}$.
Consider the subposet
$\mathcal{F}^{\prime}=\\{X_{1},X_{2}\cup\mathcal{Y}\\}\subseteq\mathcal{F}$.
We show that $\mathcal{F}^{\prime}$ is a $\mathcal{Y}$-blocker in
$\mathcal{Q}(\mathcal{X}\cup\mathcal{Y})$, i.e. by Theorem 11 we shall show
that there is no $\mathcal{Y}$-avoiding homomorphism from
$\mathcal{F}^{\prime}$ to $\mathcal{Q}(\mathcal{Y})$. A homomorphism
$\phi:\mathcal{F}^{\prime}\to\mathcal{Q}(\mathcal{Y})$ is
$\mathcal{Y}$-avoiding only if $\phi(X_{1})=\mathcal{Y}$ and
$\phi(X_{2}\cup\mathcal{Y})=\varnothing$, but such a homomorphism does not
exist, since $\phi(X_{1})\subseteq\phi(X_{2}\cup\mathcal{Y})$ because of
$X_{1}\subseteq X_{2}\cup\mathcal{Y}$. We obtain that $\mathcal{F}^{\prime}$
is a $\mathcal{Y}$-blocker, therefore
$\mathcal{F}=\\{X_{1},X_{2}\cup\mathcal{Y}\\}$ since $\mathcal{F}$ is
critical. ∎

######  Lemma 16.

Let $\mathcal{Y}$ be a set of size at least $2$ and let $a\in\mathcal{Y}$. Let
$\mathcal{F}$ be a $\mathcal{Y}$-blocker. Then the induced subposets
$\\{F\in\mathcal{F}\colon a\in F\\}$ and $\\{F\in\mathcal{F}\colon a\notin
F\\}$ are $(\mathcal{Y}\setminus\\{a\\})$-blockers.

###### Proof.

Let $\mathcal{F}^{\prime}=\\{F\in\mathcal{F}\colon a\in F\\}$. Assume that
$\mathcal{F}^{\prime}$ is not a $(\mathcal{Y}\setminus\\{a\\})$-blocker, i.e.
by Theorem 11 there is a $(\mathcal{Y}\setminus\\{a\\})$-avoiding homomorphism
$\phi\colon\mathcal{F}^{\prime}\to\mathcal{Q}(\mathcal{Y}\setminus\\{a\\})$.
We find a $\mathcal{Y}$-avoiding homomorphism of $\mathcal{F}$ in order to
reach a contradiction. Let $\psi\colon\mathcal{F}\to\mathcal{Q}(\mathcal{Y})$
with

$\psi(F)=\begin{cases}\phi(F)\cup\\{a\\},&\text{ if
}F\in\mathcal{F}^{\prime}\\\ \\{a\\},&\text{ if
}F\notin\mathcal{F}^{\prime}.\end{cases}$

Observe that $\psi$ is a homomorphism, because
$\\{a\\}\subseteq\phi(F)\cup\\{a\\}$ for all $F\in\mathcal{F}^{\prime}$ and
$\phi$ is a homomorphism.

For every $F\in\mathcal{F}\setminus\mathcal{F}^{\prime}$, note that
$a\in\psi(F)$ but $a\notin F\cap\mathcal{Y}$, thus $\psi(F)\neq
F\cap\mathcal{Y}$. On the other hand, recall that $\phi$ is
$(\mathcal{Y}\setminus\\{a\\})$-avoiding. Hence for every
$F\in\mathcal{F}^{\prime}$ we know that $\phi(F)\neq
F\cap(\mathcal{Y}\setminus\\{a\\})$ where $a\notin\phi(F)$ and $a\notin
F\cap(\mathcal{Y}\setminus\\{a\\})$. This implies

$\psi(F)=\phi(F)\cup\\{a\\}\neq
F\cap(\mathcal{Y}\setminus\\{a\\})\cup\\{a\\}=F\cap\mathcal{Y}.$

As a result, $\psi$ is a $\mathcal{Y}$-avoiding homomorphism of $\mathcal{F}$,
which is a contradiction.

The second part of the lemma follows from a symmetric argument for
$\mathcal{F}^{\prime\prime}=\\{F\in\mathcal{F}\colon a\notin F\\}$ using the
function $\psi\colon\mathcal{F}\to\mathcal{Q}(\mathcal{Y})$,

$\psi(F)=\begin{cases}\phi(F),&\text{ if }F\in\mathcal{F}^{\prime\prime}\\\
\mathcal{Y}\setminus\\{a\\},&\text{ if
}F\notin\mathcal{F}^{\prime\prime}.\end{cases}$

∎

###  3.3 Properties of $\mathcal{N}$-free $\mathcal{Y}$-blockers

######  Theorem 17.

Let $\mathcal{X}$ and $\mathcal{Y}$ be disjoint sets with
$\mathcal{Y}\neq\varnothing$. Let $\mathcal{F}$ be an $\mathcal{N}$-free,
critical $\mathcal{Y}$-blocker in $\mathcal{Q}(\mathcal{X}\cup\mathcal{Y})$.
Then $\mathcal{F}$ has at least one of a minimum vertex or a maximum vertex.

###### Proof of Theorem 17.

Since $\mathcal{Y}\neq\varnothing$, Lemma 8 implies that $|\mathcal{F}|\geq
2^{1}$. By Theorem 6, $\mathcal{F}$ is series-parallel, so it can be
partitioned into two disjoint, non-empty posets $\mathcal{F}_{1}$ and
$\mathcal{F}_{2}$ such that $\mathcal{F}$ is either the parallel composition
of $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ or the series composition of
$\mathcal{F}_{1}$ below $\mathcal{F}_{2}$. The former could not happen by
Lemma 12. Thus $\mathcal{F}$ can be partitioned into two disjoint, non-empty
posets $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ such that for every
$F_{1}\in\mathcal{F}_{1}$ and $F_{2}\in\mathcal{F}_{2}$, $F_{1}\subseteq
F_{2}$.

Let $Y_{1}=(\bigcup_{F\in\mathcal{F}_{1}}F)\cap\mathcal{Y}$ be the
$\mathcal{Y}$-part of the union of all vertices in $\mathcal{F}_{1}$ and let
$Y_{2}=(\bigcap_{F\in\mathcal{F}_{2}}F)\cap\mathcal{Y}$ be the
$\mathcal{Y}$-part of the intersection of all vertices in $\mathcal{F}_{2}$.
Clearly, $Y_{1}\subseteq Y_{2}\subseteq\mathcal{Y}$.

First assume that $Y_{1}\notin\\{\varnothing,\mathcal{Y}\\}$. Then there are
$a\in Y_{1}$ and $b\in\mathcal{Y}\setminus Y_{1}$. Lemma 8 provides that the
$\mathcal{Y}$-blocker $\mathcal{F}$ contains a vertex $U$ with
$U\cap\mathcal{Y}=\\{b\\}$. Then $U\notin\mathcal{F}_{1}$ since $b\in U$ while
$b\notin Y_{1}$, but also $U\notin\mathcal{F}_{2}$ as $a\notin U$ while $a\in
Y_{1}\subseteq Y_{2}$. We arrive at a contradiction, hence
$Y_{1}\in\\{\varnothing,\mathcal{Y}\\}$. Symmetrically,
$Y_{2}\in\\{\varnothing,\mathcal{Y}\\}$. Take an arbitrary $\mathcal{Y}$-part
$Y\subseteq\mathcal{Y}$ such that $Y\notin\\{\varnothing,\mathcal{Y}\\}$. By
Lemma 8 there is a vertex $Z\in\mathcal{F}$ with $Z\cap\mathcal{Y}=Y$. Then
$Z\in\mathcal{F}_{1}$ or $Z\in\mathcal{F}_{2}$. In the first case we obtain
that $Y_{1}\neq\varnothing$, thus $Y_{1}=\mathcal{Y}$ and hence
$Y_{2}=\mathcal{Y}$ (because $Y_{1}\subseteq Y_{2}\subseteq\mathcal{Y}$). In
the second case $Y_{2}\neq\mathcal{Y}$, so $Y_{1}=Y_{2}=\varnothing$.

Thus either $Y_{1}=Y_{2}=\varnothing$ or $Y_{1}=Y_{2}=\mathcal{Y}$. For the
rest of the proof we suppose that $Y_{1}=Y_{2}=\varnothing$. If
$Y_{1}=Y_{2}=\mathcal{Y}$, a symmetric argument holds.

Because $Y_{1}=(\bigcup_{F\in\mathcal{F}_{1}}F)\cap\mathcal{Y}=\varnothing$,
we obtain $F\cap\mathcal{Y}=\varnothing$ for every $F\in\mathcal{F}_{1}$. By
Lemma 14, there is at most one vertex in $\mathcal{F}_{1}$. The unique vertex
$Z\in\mathcal{F}_{1}$ is the unique minimal vertex of $\mathcal{F}$ and
$Z\cap\mathcal{Y}=Y_{1}=\varnothing$. In the case that
$Y_{1}=Y_{2}=\mathcal{Y}$, we can argue symmetrically and obtain that $Z$ is a
maximum of $\mathcal{F}$ and $Z\cap\mathcal{Y}=Y_{2}=\mathcal{Y}$. ∎

###  3.4 Construction of the family
$\\{(\mathcal{F}_{S},Z_{S},A_{S},B_{S}):~{}S\in\mathcal{S}\\}$

In the following proof we will define posets and vertices indexed by ordered
sets.

######  Definition 18.

An ordered set $S$ is a sequence $S=(y_{1},\dots,y_{m})$ of distinct elements
$y_{i}$, $i\in[m]$. Given a set $\mathcal{Y}$, $S$ is an ordered subset of
$\mathcal{Y}$ if $y_{i}\in\mathcal{Y}$ for all $i\in[m]$. We denote the empty
ordered set by $\varnothing_{o}=()$. The underlying unordered set of $S$ is
denoted by $\underline{S}$ and $|S|=|\underline{S}|$ is the size of $S$. For
an ordered set $S=(y_{1},\ldots,y_{m})$ and an element
$y_{m+1}\notin\underline{S}$, we write $(S,y_{m+1})$ for an ordered set
$(y_{1},\ldots,y_{m},y_{m+1})$. We say that an ordered set $S^{\prime}$ is a
prefix of $S$ if $|S|\geq|S^{\prime}|$ and each of the first $|S^{\prime}|$
members of $S$ coincides with the respective member of $S^{\prime}$. Note that
$\varnothing_{o}$ is a prefix of every ordered set. For
$i\in\\{0,\dots,|S|\\}$, we denote by $S[i]$ the unique prefix of $S$ of size
$i$. A prefix $S^{\prime}$ of $S$ is strict if $S^{\prime}\neq S$. For a set
$\mathcal{Y}$ and an ordered subset $S$ of $\mathcal{Y}$, we denote the set of
all elements of $\mathcal{Y}$ that are not in $S$ by
$\mathcal{Y}-S=\mathcal{Y}\setminus\underline{S}$.

In the following we analyse the structure of an $\mathcal{N}$-free critical
$\mathcal{Y}$-blocker by selecting smaller and smaller subposets which are
critical $\mathcal{Y}^{\prime}$-blockers for some
$\mathcal{Y}^{\prime}\subseteq\mathcal{Y}$. Recall that Theorem 17 implies
that any critical $\mathcal{Y}^{\prime}$-blocker has either a minimum or a
maximum vertex, we call such a vertex a root of the blocker. Note that the
blocker could have both a minimum vertex and a maximum vertex. In this case we
select on of them to be the assigned root of the blocker and ignore the second
root.

######  Construction 19.

Let $\mathcal{Y}$ be a set with $|\mathcal{Y}|=k$. Let $\mathcal{F}$ be an
$\mathcal{N}$-free, critical $\mathcal{Y}$-blocker in
$\mathcal{Q}(\mathcal{Z})$, $\mathcal{Y}\subseteq\mathcal{Z}$. Let
$\mathcal{S}$ be the set of all ordered subsets of $\mathcal{Y}$ of size at
most $k-1$. In the following we recursively construct a family
$\\{(\mathcal{F}_{S},Z_{S},A_{S},B_{S}):~{}S\in\mathcal{S}\\}$, where
$\mathcal{F}_{S}$ is a critical $(\mathcal{Y}-S)$-blocker,
$\mathcal{F}_{S}\subseteq\mathcal{F}$, and $Z_{S}$ is the root of
$\mathcal{F}_{S}$. In addition $A_{S}\cup B_{S}=\underline{S}$, where each
element of $A_{S}$ is included in each vertex of $\mathcal{F}_{S}$ and each
element of $B_{S}$ is excluded from each vertex of $\mathcal{F}_{S}$. The sets
$A_{S}$ and $B_{S}$ are used as tools to encode crucial information on the
blocker $\mathcal{F}_{S}$ and its root $Z_{S}$ as well as
$\mathcal{F}_{S^{\prime}}$ and $Z_{S^{\prime}}$ for prefixes $S^{\prime}$ of
$S$. If the root $Z_{S}$ is a minimum vertex in $\mathcal{F}_{S}$, we say that
$S$ is min-type, otherwise we say that $S$ is max-type.

Initial step.  Let $S={\varnothing_{o}}$. In this case let
$\mathcal{F}_{S}=\mathcal{F}$. Let $Z_{S}$ be an arbitrarily chosen root of
$\mathcal{F}$, i.e. a minimum or maximum of $\mathcal{F}$, which exists due to
Theorem 17. Let $A_{S}=B_{S}=\varnothing$.

General iterative step.  Consider an arbitrary non-empty ordered subset $S$ of
$\mathcal{Y}$ with $|S|\leq k-1$. Let $S^{\prime}$ be the prefix of $S$ such
that $(S^{\prime},a)=S$ for some $a\in\mathcal{Y}$. Given
$(\mathcal{F}_{S^{\prime}},Z_{S^{\prime}},A_{S^{\prime}},B_{S^{\prime}})$ such
that $\mathcal{F}_{S^{\prime}}$ is a critical
$(\mathcal{Y}-{S^{\prime}})$-blocker, $Z_{S^{\prime}}$ is a root of
$\mathcal{F}_{S^{\prime}}$, and $A_{S^{\prime}},B_{S^{\prime}}$ are disjoint
sets partitioning $A_{S^{\prime}}\cup B_{S^{\prime}}=\underline{S^{\prime}}$,
we shall construct $\mathcal{F}_{S}$, $Z_{S}$, $A_{S}$, and $B_{S}$. By Lemma
16 and since $(\mathcal{Y}-{S^{\prime}})\setminus\\{a\\}=\mathcal{Y}-S$, the
sets $\\{F\in\mathcal{F}_{S^{\prime}}:a\in F\\}$ and
$\\{F\in\mathcal{F}_{S^{\prime}}:a\notin F\\}$ induce
$(\mathcal{Y}-S)$-blockers.

If ${S^{\prime}}$ is min-type, we define $\mathcal{F}_{S}$ to be an arbitrary
critical $(\mathcal{Y}-S)$-blocker which is an induced subposet of
$\\{F\in\mathcal{F}_{S^{\prime}}:a\in F\\}$. Note that $a\in F$ for every
$F\in\mathcal{F}_{S}$. Let $A_{S}=A_{S^{\prime}}\cup\\{a\\}$ and
$B_{S}=B_{S^{\prime}}$.

If ${S^{\prime}}$ is max-type, we define $\mathcal{F}_{S}$ to be an arbitrary
critical $(\mathcal{Y}-S)$-blocker which is an induced subposet of
$\\{F\in\mathcal{F}_{S^{\prime}}:a\notin F\\}$. Note that in this case
$a\notin F$ for every $F\in\mathcal{F}_{S}$. Let $A_{S}=A_{S^{\prime}}$ and
$B_{S}=B_{S^{\prime}}\cup\\{a\\}$.

It remains to select $Z_{S}$. Theorem 17 provides the existence of a root in
$\mathcal{F}_{S}$. If $|{S}|\leq k-2$, let $Z_{S}$ be an arbitrary root of
$\mathcal{F}_{S}$. If $|S|=k-1$, we need to be more careful in choosing
$Z_{S}$. We have that $\mathcal{F}_{S}$ is a critical
$(\mathcal{Y}-S)$-blocker, for $|\mathcal{Y}-S|=1$. By Lemma 15,
$\mathcal{F}_{S}$ has exactly two vertices, a minimum and a maximum. If
${S^{\prime}}$ is min-type, let $Z_{S}$ be the minimum of $\mathcal{F}_{S}$,
i.e. ${S}$ is min-type. If ${S^{\prime}}$ is max-type, let $Z_{S}$ be the
maximum of $\mathcal{F}_{S}$, here ${S}$ is max-type.

Figure 5: Exemplary construction of $\mathcal{F}_{(1,3)}$ and
$\mathcal{F}_{(1,2)}$ for $\mathcal{Y}=\\{1,2,3\\}$.

The construction terminates after all ordered subsets of $\mathcal{Y}$ of size
at most $k-1$ have been considered. The family
$\\{(\mathcal{F}_{S},Z_{S},A_{S},B_{S}):~{}S\in\mathcal{S}\\}$ gives a
recursive structural decomposition of $\mathcal{F}$ into “up” and “down”
components, i.e. max-type and min-type blockers, as illustrated in Figure 5.
Note that blockers $\mathcal{F}_{S}$ may heavily overlap. Several properties
follow immediate from the construction.

######  Lemma 20.

Let $S$ be an ordered subset of $\mathcal{Y}$ of size at most $k-1$ and let
$S^{\prime}$ be a prefix of $S$. Then

  1. (i)

$\mathcal{F}_{S^{\prime}}\subseteq\mathcal{F}_{S}$,
$A_{S^{\prime}}=A_{S}\cap\underline{S^{\prime}}$ and
$B_{S^{\prime}}=B_{S}\cap\underline{S^{\prime}}$.

  2. (ii)

The size of the set $A_{S}$ is equal to the number of min-type strict prefixes
$S^{\prime}$ of $S$. The size of $B_{S}$ is equal to the number of max-type
strict prefixes $S^{\prime}$ of $S$.

  3. (iii)

If $S$ is min-type, $\mathcal{Y}\cap Z_{{S}}=\\{y\in\mathcal{Y}:y\in
Z_{S}\\}=A_{S}$. If $S$ is max-type, $\mathcal{Y}\setminus
Z_{{S}}=\\{y\in\mathcal{Y}:y\notin Z_{S}\\}=B_{S}$.

###### Proof.

$(i)$ and $(ii)$ are easy to see. For part $(iii)$, recall that
$\mathcal{F}_{S}$ is a $(\mathcal{Y}-S)$-blocker. If ${S}$ is min-type, then
$Z_{S}$ is a minimum of $\mathcal{F}_{S}$, so
$Z_{S}\cap(\mathcal{Y}-S)=\varnothing$ by Lemma 8. Thus

$Z_{{S}}\cap\mathcal{Y}=Z_{S}\cap\underline{S}=A_{S}.$

Similarly, if $\mathcal{F}_{S}$ is max-type, then Lemma 8 provides
$Z_{S}\cap(\mathcal{Y}-S)=(\mathcal{Y}-S)$. Hence

$Z_{{S}}\cap\mathcal{Y}=\big{(}Z_{S}\cap\underline{S}\big{)}\cup(\mathcal{Y}-S)=A_{S}\cup(\mathcal{Y}-S)=\mathcal{Y}\setminus
B_{S},$

therefore $\mathcal{Y}\setminus Z_{{S}}=B_{S}$. ∎

######  Lemma 21.

Let $S$ be an ordered subset of $\mathcal{Y}$ of size $k-1$ and let
$S^{\prime}$ be a strict prefix of $S$. Then
$Z_{S}\cap(\mathcal{Y}-S^{\prime})\notin\\{\varnothing,\mathcal{Y}-S^{\prime}\\}$.

###### Proof.

Note that $|\mathcal{Y}-S|=1$, so let $\mathcal{Y}-S=\\{b\\}$. First we
consider the case that $|S^{\prime}|=k-2$, i.e. $S=(S^{\prime},a)$ for some
$a\in\mathcal{Y}$. Note that $\mathcal{Y}-S^{\prime}=\\{a,b\\}$. We shall show
that one of the two elements $a,b$ is in $Z_{S}$ while the other is not.

If $S$ is min-type, we obtain from the construction that $a\in A_{S}$. By
Lemma 20 $(iii)$, $A_{S}=Z_{S}\cap\mathcal{Y}$, so in particular $a\in
Z_{S}\cap(\mathcal{Y}-S^{\prime})$. On the other hand,
$A_{S}\subseteq\underline{S}$, so $b\notin A_{S}=Z_{S}\cap\mathcal{Y}$ and
thus $b\notin Z_{S}\cap(\mathcal{Y}-S^{\prime})$.

If $S$ is max-type we can argue similarly. Note that $a\in B_{S}$. By Lemma 20
$(iii)$, $B_{S}=\mathcal{Y}\setminus Z_{S}$, so $a\notin
Z_{S}\cap(\mathcal{Y}-S^{\prime})$. Furthermore,
$B_{S}\subseteq\underline{S}$, so $b\notin B_{S}=\mathcal{Y}\setminus Z_{S}$.
Thus $b\in Z_{S}\cap\mathcal{Y}$ and hence $b\in
Z_{S}\cap(\mathcal{Y}-S^{\prime})$.

It remains to consider the case $|S^{\prime}|<k-2$. Let
$S^{\prime\prime}=S[k-2]$ be the prefix of $S$ of size $k-2$, then
$S^{\prime}$ is a prefix of $S^{\prime\prime}$. Observe that
$\mathcal{Y}-S^{\prime\prime}\subseteq\mathcal{Y}-S^{\prime}$. We already
showed that
$Z_{S}\cap(\mathcal{Y}-S^{\prime\prime})\notin\\{\varnothing,\mathcal{Y}-S^{\prime\prime}\\}$,
so in particular
$Z_{S}\cap(\mathcal{Y}-S^{\prime})\notin\\{\varnothing,\mathcal{Y}-S^{\prime}\\}$.
∎

##  4 Proof of Theorem 4

###### Proof of Theorem 4.

Let $k$ and $N$ be arbitrary integers with $N\geq k$, let $n$ such that
$N=n+k$. Let $\mathcal{Y}$ be a set on $|\mathcal{Y}|=k$ elements, say without
loss of generality $\mathcal{Y}=\\{1,\ldots,k\\}$. Fix $\mathcal{Z}$ with
$\mathcal{Y}\subseteq\mathcal{Z}$ and $|\mathcal{Z}|=N$. Suppose that there is
an $\mathcal{N}$-free, critical $\mathcal{Y}$-blocker $\mathcal{F}$ in
$\mathcal{Q}(\mathcal{Z})$. In other words, suppose that the integer $N$ is
sufficiently large with respect to $k$ such that there exists an $\mathcal{F}$
with these properties in $\mathcal{Z}$.

In the following we show that $\mathcal{F}$ contains an antichain of size at
least $k!2^{-k-1}$. Applying Sperner’s theorem we obtain that
$n+k=N=|\mathcal{Z}|\geq k\log k$, which implies that $k\leq(1+o(1))n/{\log
n}$, i.e. $N=n+k\leq n+(1+o(1))n/{\log n}$. Then Theorem 9 provides the
required bound. Next we argue that in $\mathcal{F}$ there exists such a large
antichain.

Let $\mathcal{S}$ be the set of all ordered subsets of $\mathcal{Y}$ of size
at most $k-1$. Consider the family
$\\{(\mathcal{F}_{S},Z_{S},A_{S},B_{S}):~{}S\in\mathcal{S}\\}$ given by
Construction 19. Let $\mathcal{S}_{1}$ be the family of all ordered subsets of
$\mathcal{Y}$ of size exactly $k-1$. We introduce two kinds of equivalence
between elements in $\mathcal{S}_{1}$, type-equivalence and intersection-
equivalence. In the following we will show the existence of a large subfamily
$\mathcal{S}_{3}\subseteq\mathcal{S}_{1}$ such that its elements are pairwise
type-equivalent but not intersection-equivalent. We further prove that the
vertices $\\{Z_{S}:S\in\mathcal{S}_{3}\\}$ induce a large antichain in
$\mathcal{Q}(\mathcal{X}\cup\mathcal{Y})$.

Let $S_{1},S_{2}\in\mathcal{S}_{1}$ be two ordered subsets of $\mathcal{Y}$ of
size $k-1$. We say that $S_{1}$ and $S_{2}$ are type-equivalent if for any
prefixes $S^{\prime}_{1}$ of $S_{1}$ and $S^{\prime}_{2}$ of $S_{2}$ of the
same size, ${S^{\prime}_{1}}$ is min-type if and only if ${S^{\prime}_{2}}$ is
min-type. Equivalently, ${S^{\prime}_{1}}$ is max-type if and only if
${S^{\prime}_{2}}$ is max-type. The ordered sets $S_{1}$ and $S_{2}$ are
intersection-equivalent if for any same-sized prefixes $S^{\prime}_{1}$ of
$S_{1}$ and $S^{\prime}_{2}$ of $S_{2}$,
$Z_{S^{\prime}_{1}}\cap\mathcal{Y}=Z_{S^{\prime}_{2}}\cap\mathcal{Y}$. It is
obvious that both notions define equivalence relations on $\mathcal{S}_{1}$.
Note that intersection-equivalence of two ordered sets in $\mathcal{S}_{1}$ is
a very strong property. It provides a good intuition to think of intersection-
equivalent ordered sets as equal. Several technical parts of the proof, in
particular in Claim 1, arise from the fact that there might be intersection-
equivalent ordered sets which are distinct.

Claim 1. There exists a subfamily $\mathcal{S}_{3}\subseteq\mathcal{S}_{1}$ of
size at least $2^{-k-1}k!$ such that any two distinct ordered sets
$S_{1},S_{2}\in\mathcal{S}_{3}$, are type-equivalent but not intersection-
equivalent.
Proof of Claim 1. Recall that $|\mathcal{S}_{1}|=k!$. For every
$i\in\\{0,\dots,k-1\\}$ and for every $S\in\mathcal{S}_{1}$, the prefix $S[i]$
of $S$ of size $i$ is either min-type or max-type. By pigeonhole principle for
fixed $i$, there are at least $|\mathcal{S}_{1}|/2$ ordered subsets
$S\in\mathcal{S}_{1}$ such that all prefixes $S[i]$ are of the same type.
Inductively, we find a subfamily $\mathcal{S}_{2}\subseteq\mathcal{S}_{1}$ of
size at least $2^{-k}|\mathcal{S}_{1}|$ such that for any fixed
$i\in\\{0,\dots,k-1\\}$, all prefixes $S[i]$, $S\in\mathcal{S}_{2}$ have the
same type. Equivalently, the elements of $\mathcal{S}_{2}$ are pairwise type-
equivalent.

In the following we show that each intersection-equivalence class in
$\mathcal{S}_{2}$ has size at most $2$. Thus by selecting a representative of
each equivalence class we obtain a subfamily $\mathcal{S}_{3}$ as required.

Given an arbitrary fixed $S_{1}\in\mathcal{S}_{2}$, consider an ordered set
$S_{2}\in\mathcal{S}_{2}$ such that $S_{1}$ and $S_{2}$ are intersection-
equivalent, i.e.
$Z_{S^{\prime}_{1}}\cap\mathcal{Y}=Z_{S^{\prime}_{2}}\cap\mathcal{Y}$ for
every two same-sized prefixes $S^{\prime}_{1}$ of $S_{1}$ and $S^{\prime}_{2}$
of $S_{2}$. Without loss of generality suppose that $S_{1}=(1,2,\dots,k-1)$
and $\mathcal{Y}-S_{1}=\\{k\\}$. Let $S_{2}=(y_{1},\dots,y_{k-1})$ and
$\mathcal{Y}-S_{2}=\\{y_{k}\\}$. We shall show that $y_{i}=i$ for all but at
most two indices $i\in[k]$, which implies that $S_{2}$ is either equal to
$S_{1}$ or obtained from $S_{1}$ by interchanging the two differing members,
and therefore the intersection-equivalence class of $S_{1}$ consists of at
most $2$ members.

Since $S_{1}$ and $S_{2}$ are both in $\mathcal{S}_{2}$, i.e. type-equivalent,
we know that for every $i\in\\{0,\dots,k-1\\}$ either both ${S_{1}[i]}$ and
${S_{2}[i]}$ are min-type or both ${S_{1}[i]}$ and ${S_{2}[i]}$ are max-type.
We enumerate the index set $\\{0,\dots,k-1\\}$ as follows. Let
$i_{1},\dots,i_{p}$ be the indices $i\in\\{0,\dots,k-1\\}$ such that
${S_{1}[i]}$ and ${S_{2}[i]}$ are min-type in increasing order. Similarly, let
$j_{1},\dots,j_{q}$ enumerate in increasing order the indices
$j\in\\{0,\dots,k-1\\}$ where ${S_{1}[j]}$ and ${S_{2}[j]}$ are max-type. Note
that $\\{i_{1},\dots,i_{p}\\}\cup\\{j_{1},\dots,j_{q}\\}=\\{0,\dots,k-1\\}$.

Now consider any two consecutive indices $i=i_{\ell}$ and
$i^{\prime}=i_{\ell+1}$ for some fixed $\ell\in[p-1]$. We know from Lemma 20
$(iii)$ that $Z_{S_{1}[i]}\cap\mathcal{Y}=A_{S_{1}[i]}\text{ and
}Z_{S_{1}[i^{\prime}]}\cap\mathcal{Y}=A_{S_{1}[i^{\prime}]}.$ Our next step is
to show that $i+1$ is the unique element in the set difference of those two
sets.

Recall that $S_{1}[i]$ is min-type. In Construction 19 in the iterative step
for $S_{1}[i+1]=(S_{1}[i],i+1)$, we defined
$A_{S_{1}[i+1]}=A_{S_{1}[i]}\cup\\{i+1\\}$. Note that $i+1\in
A_{S_{1}[i+1]}\subseteq A_{S_{1}[i^{\prime}]}$, while $i+1\notin A_{S_{1}[i]}$
because $A_{S_{1}[i]}\subseteq\underline{S_{1}[i]}=\\{1,\dots,i\\}$ by Lemma
20 $(i)$. Furthermore, Lemma 20 $(ii)$ provides that $|A_{S_{1}[i]}|=\ell$ and
$|A_{S_{1}[i^{\prime}]}|=\ell+1$, thus $|A_{S_{1}[i^{\prime}]}\setminus
A_{S_{1}[i]}|=1$ and so

$(Z_{S_{1}[i^{\prime}]}\cap\mathcal{Y})\setminus(Z_{S_{1}[i]}\cap\mathcal{Y})=A_{S_{1}[i^{\prime}]}\setminus
A_{S_{1}[i]}=\\{i+1\\}.$

Similarly for $S_{2}$ we obtain

$(Z_{S_{2}[i^{\prime}]}\cap\mathcal{Y})\setminus(Z_{S_{2}[i]}\cap\mathcal{Y})=A_{S_{2}[i^{\prime}]}\setminus
A_{S_{2}[i]}=\\{y_{i+1}\\}.$

Since $S_{1}$ and $S_{2}$ are intersection-equivalent, we find that
$y_{i+1}=i+1$.

We obtain that $y_{i_{\ell}+1}=i_{\ell}+1$ for every $\ell\in[p-1]$. For
$j_{1},\dots,j_{q}$ a symmetric argument for $j=j_{\ell}$ and
$j^{\prime}=j_{\ell+1}$ considering the set difference

$(Z_{S_{1}[j]}\cap\mathcal{Y})\setminus(Z_{S_{1}[j^{\prime}]}\cap\mathcal{Y})=(\mathcal{Y}\setminus
B_{S_{1}[j]})\setminus(\mathcal{Y}\setminus
B_{S_{1}[j^{\prime}]})=B_{S_{1}[j^{\prime}]}\setminus B_{S_{1}[j]}=\\{j+1\\}$

yields that $y_{j_{\ell+1}}=j_{\ell+1}$ for every $\ell\in[q-1]$. Thus
$y_{i+1}=i+1$ for all indices
$i\in\\{0,\dots,k-1\\}\setminus\\{i_{p},j_{q}\\}$, so $S_{1}$ and $S_{2}$
coincide in all but at most two members. As a consequence, $S_{2}$ is either
equal to $S_{1}$ or obtained from $S_{1}$ by interchanging the two differing
members. Therefore the intersection-equivalence class of $S_{1}$ consists of
at most $2$ ordered sets. As $S_{1}$ was chosen arbitrary, every intersection-
equivalence class of $\mathcal{S}_{2}$ has size at most $2$. Select
$\mathcal{S}_{3}\subseteq\mathcal{S}_{2}$ by choosing an arbitrary
representative from each intersection-equivalence class, i.e. let
$\mathcal{S}_{3}$ be the largest subfamily of $\mathcal{S}_{2}$ where every
two distinct $S_{2},S_{3}\in\mathcal{S}_{3}$ are not intersection-equivalent.
Then

$|\mathcal{S}_{3}|\geq|\mathcal{S}_{2}|/2\geq
2^{-k-1}|\mathcal{S}_{1}|=2^{-k-1}k!,$

which concludes the proof of Claim 1.

Claim 2. The set $\\{Z_{S}:S\in\mathcal{S}_{3}\\}$ induces an antichain in
$\mathcal{Q}(\mathcal{Z})$ of size $|\mathcal{S}_{3}|=k!2^{-k-1}$.

Remark.  Although not necessary for the proof of Theorem 4, Claim 2 holds in
greater generality. Analogously to the following proof, one can obtain that
for every family $\mathcal{S}^{\prime}$ of ordered sets such that any two
distinct members of $\mathcal{S}^{\prime}$ are type-equivalent and not
intersection-equivalent, the vertices $\\{Z_{S}:S\in\mathcal{S}^{\prime}\\}$
induce an antichain in $\mathcal{Q}(\mathcal{Z})$ of size
$|\mathcal{S}^{\prime}|$.

Proof of Claim 2. Recall that any two distinct, ordered sets in
$\mathcal{S}_{3}$ are type-equivalent but not intersection-equivalent. We
shall show that for every two distinct $S_{1},S_{2}\in\mathcal{S}_{3}$, the
vertices $Z_{S_{1}}$ and $Z_{S_{2}}$ are incomparable. Assume towards a
contradiction that $Z_{S_{1}}\subseteq Z_{S_{2}}$. Since $S_{1}$ and $S_{2}$
are not intersection-equivalent, there are same-sized prefixes
$S^{\prime}_{1}$ of $S_{1}$ and $S^{\prime}_{2}$ of $S_{2}$ such that
$Z_{S^{\prime}_{1}}\cap\mathcal{Y}\neq Z_{S^{\prime}_{2}}\cap\mathcal{Y}$.
Since $S_{1}$ and $S_{2}$ are type-equivalent, both ${S^{\prime}_{1}}$ and
${S^{\prime}_{2}}$ have the same type, suppose that they are min-type.

First we argue that the sets $Z_{S^{\prime}_{1}}\cap\mathcal{Y}$ and
$Z_{S^{\prime}_{2}}\cap\mathcal{Y}$ are not comparable. Lemma 20 $(iii)$ shows
that $Z_{S^{\prime}_{1}}\cap\mathcal{Y}=A_{S^{\prime}_{1}}$ and
$Z_{S^{\prime}_{2}}\cap\mathcal{Y}=A_{S^{\prime}_{2}}$. Type-equivalence
implies that pairs of same-sized prefixes of $S^{\prime}_{1}$ and
$S^{\prime}_{2}$ always have the same type. Thus Lemma 20 $(ii)$ yields that
$|A_{S^{\prime}_{1}}|=|A_{S^{\prime}_{2}}|$. We obtain that
$Z_{S^{\prime}_{1}}\cap\mathcal{Y}=A_{S^{\prime}_{1}}$ and
$Z_{S^{\prime}_{2}}\cap\mathcal{Y}=A_{S^{\prime}_{2}}$ are distinct but of the
same size, consequently $Z_{S^{\prime}_{1}}\cap\mathcal{Y}$ and
$Z_{S^{\prime}_{2}}\cap\mathcal{Y}$ are not comparable.

If $S^{\prime}_{1}=S_{1}$ and $S^{\prime}_{2}=S_{2}$, then
$Z_{S_{1}}\cap\mathcal{Y}$ and $Z_{S_{2}}\cap\mathcal{Y}$ are incomparable,
and so $Z_{S_{1}}||Z_{S_{2}}$, a contradiction to our assumption that
$Z_{S_{1}}\subseteq Z_{S_{2}}$. For the remaining proof suppose that the size
$|S^{\prime}_{1}|=|S^{\prime}_{2}|$ is strictly less than $k-1$. We will show
that there is a copy of $\mathcal{N}$ in $\mathcal{F}$ contradicting the
definition of $\mathcal{F}$ to be an $\mathcal{N}$-free poset. Let
$\mathcal{Y}^{\prime}=\mathcal{Y}-S^{\prime}_{2}$, note that
$\mathcal{F}_{S^{\prime}_{2}}$ is a $\mathcal{Y}^{\prime}$-blocker. Since
$Z_{S^{\prime}_{1}}\cap\mathcal{Y}$ and $Z_{S^{\prime}_{2}}\cap\mathcal{Y}$
are not comparable, there exists an element $a\in
Z_{S^{\prime}_{1}}\cap\mathcal{Y}$ with $a\notin Z_{S^{\prime}_{2}}$. Lemma 8
$(ii)$ yields the existence of a vertex $U\in\mathcal{F}_{S^{\prime}_{2}}$
with $U\cap\mathcal{Y}^{\prime}=\mathcal{Y}^{\prime}\setminus\\{a\\}$.

Figure 6: Copy of $\mathcal{N}$ constructed in the proof of Claim 2.

Now we verify that $Z_{S^{\prime}_{1}}$, $Z_{S_{2}}$, $Z_{S^{\prime}_{2}}$ and
$U$ form a copy of $\mathcal{N}$ in $\mathcal{F}$, see Figure 6.

  * •

$Z_{S^{\prime}_{2}}\subseteq Z_{S_{2}}$ because $Z_{S^{\prime}_{2}}$ is a
minimum of $\mathcal{F}_{S^{\prime}_{2}}$ and
$Z_{S_{2}}\in\mathcal{F}_{S_{2}}\subseteq\mathcal{F}_{S^{\prime}_{2}}$ by
Lemma 20 $(i)$.

  * •

$Z_{S^{\prime}_{1}}\subseteq Z_{S_{1}}\subseteq Z_{S_{2}}$ as
$Z_{S^{\prime}_{1}}$ is a minimum of $\mathcal{F}_{S^{\prime}_{1}}$ and
$Z_{S_{1}}\in\mathcal{F}_{S_{1}}\subseteq\mathcal{F}_{S^{\prime}_{1}}$ by
Lemma 20 $(i)$.

  * •

$Z_{S^{\prime}_{1}}||Z_{S^{\prime}_{2}}$ because
$Z_{S^{\prime}_{1}}\cap\mathcal{Y}$ and $Z_{S^{\prime}_{2}}\cap\mathcal{Y}$
are not comparable.

  * •

$Z_{S^{\prime}_{2}}\subseteq U$ because $Z_{S^{\prime}_{2}}$ is a minimum of
$\mathcal{F}_{S^{\prime}_{2}}$ and by definition
$U\in\mathcal{F}_{S^{\prime}_{2}}$.

  * •

Note that $a\notin U$ and $a\in Z_{S^{\prime}_{1}}$, so
$Z_{S^{\prime}_{1}}\not\subseteq U$. Since $Z_{S^{\prime}_{2}}\not\subseteq
Z_{S^{\prime}_{1}}$ but $Z_{S^{\prime}_{2}}\subseteq U$, transitivity yields
$U\not\subseteq Z_{S^{\prime}_{1}}$. Therefore $U$ and $Z_{S^{\prime}_{1}}$
are incomparable.

  * •

We know that $a\notin U$ but $a\in Z_{S_{2}}$, thus $Z_{S_{2}}\not\subseteq
U$. Note that
$Z_{S_{2}}\cap\mathcal{Y}^{\prime}\neq\mathcal{Y}^{\prime}\setminus\\{a\\}$
since $a\in Z_{S_{2}}$. Furthermore, Lemma 20 provides that
$Z_{S_{2}}\cap\mathcal{Y}^{\prime}\neq\mathcal{Y}^{\prime}$. Thus
$Z_{S_{2}}\cap\mathcal{Y}^{\prime}$ is not a superset of
$\mathcal{Y}^{\prime}\setminus\\{a\\}=U\cap\mathcal{Y}^{\prime}$, therefore
$U\not\subseteq Z_{S_{2}}$. We obtain that $U||Z_{S_{2}}$.

  * •

The four vertices are distinct because otherwise we find an immediate
contradiction to one of the above relations.

Thus, there is a copy of $\mathcal{N}$ in $\mathcal{F}$, which is a
contradiction to the fact that $\mathcal{F}$ is $\mathcal{N}$-free.

If $S^{\prime}_{1}$ and $S^{\prime}_{2}$ are max-type, a symmetric argument
can be applied: As a first step, it follows similarly that
$Z_{S^{\prime}_{1}}\cap\mathcal{Y}$ and $Z_{S^{\prime}_{2}}\cap\mathcal{Y}$
are incomparable, and then for
$\mathcal{Y}^{\prime}=\mathcal{Y}-S^{\prime}_{1}$ and for a vertex
$U\in\mathcal{F}_{S^{\prime}_{1}}$ with $U\cap\mathcal{Y}^{\prime}=\\{a\\}$ we
find a copy of $\mathcal{N}$ on vertices $Z_{S^{\prime}_{1}}$, $Z_{S_{1}}$,
$Z_{S^{\prime}_{2}}$ and $U$, which is a contradiction as before. This
concludes the proof of Claim 2.

Claims 2 implies the existence of an antichain of size at least $k!2^{-k-1}$
in $\mathcal{F}\subseteq\mathcal{Q}(\mathcal{Z})$. We define the Sperner
number $\alpha(t)$ as the smallest $m\in\mathbb{N}$ such that
$\binom{m}{\lfloor m/2\rfloor}\geq t$. It is folklore that
$\alpha(t)\geq\log(t)$. By Sperner’s theorem [17],
$|\mathcal{Z}|\geq\alpha(k!2^{-k-1})$, so

$N=|\mathcal{Z}|\geq\alpha\left(\frac{k!}{2^{k+1}}\right)\geq\log\left(\frac{k!}{2^{k+1}}\right)\geq\log\left(\frac{k^{k}}{2^{k+1}e^{k}}\right)\geq
k(\log(k)-c),$

for a fixed constant $c>0$. Recall that $N=n+k$, so we obtain that $n\geq
k\log k-\big{(}1+c\big{)}k$, which implies that
$k\leq\big{(}1-o(1)\big{)}\frac{n}{\log n}$. Then Theorem 9 provides that

$R(\mathcal{N},Q_{n})\leq N=n+k\leq n+\big{(}1+o(1)\big{)}\frac{n}{\log n}.$

The lower bound on $R(\mathcal{N},Q_{n})$ follows from Theorem 3.

∎

##  5 Concluding remarks

In this paper we showed that $R(\mathcal{N},Q_{n})\leq
n+\Theta\left(\frac{n}{\log n}\right)$. A key ingredient in our approach is
Theorem 9 where we showed a connection between the poset Ramsey number of
$R(P,Q_{n})$ for a poset $P$ and the extremal function $m_{P}(n)$ defined as

$m_{P}(n):=\min\\{N:~{}\text{there is no
}\text{P-free}~{}\text{$\mathcal{Y}$\\!-blocker in }\mathcal{Q}([N])\text{ for
some }\mathcal{Y}\subseteq[N],|\mathcal{Y}|=N-n\\}.$

A $\mathcal{Y}$-blocker can be seen as a transversal of a set of specific
Boolean lattices, and is related to other notions of transversals, e.g.
clique-transversals in graphs as introduced by Erdős, Gallai and Tuza [9].
Seen in this context, research on $m_{P}(n)$ or similar extremal functions on
$\mathcal{Y}$-blockers might be of independent interest.

In our proof of Theorem 4 we obtained a bound on $N=n+k$ by finding a large
antichain in our $\mathcal{N}$-free $\mathcal{Y}$-blocker $\mathcal{F}$ and
applying Sperner’s theorem, which says that an antichain in $\mathcal{Q}([N])$
has size at most $\binom{N}{\lceil N/2\rceil}$. Alternatively one can utilize
the extremal number of $\mathcal{N}$: Given a poset $P$ and an integer $N$,
the extremal number $\operatorname{La}^{*}(N,P)$ is the maximum number of
vertices in a $P$-free poset in $\mathcal{Q}([N])$. Methuku and Pálvölgyi [15]
showed that $\operatorname{La}^{*}(N,P)\leq c(P)\binom{N}{N/2}$ which has the
same order of magnitude as the value given by Sperner’s theorem used in our
proof. Instead of showing that $\mathcal{F}$ contains a large antichain, i.e.
many pairwise incomparable vertices, one can simply show that the number of
vertices in $\mathcal{F}$ is large. This argument can be applied for
determining $R(P,Q_{n})$ for any fixed poset $P$.

Data Availability: Data sharing not applicable to this article as no datasets
were generated or analysed during the current study.

Acknowledgments: None.

Funding Statement: The research of both authors was partially supported by
Deutsche Forschungsgemeinschaft, grant FKZ AX 93/2-1.

Conflict of Interest: None.

Author Contribution Statement : M.A. and C.W. wrote and reviewed the
manuscript.

## References

  * [1] M. Axenovich, and S. Walzer. Boolean lattices: Ramsey properties and embeddings. Order 34(2), 287–298 (2017).
  * [2] M. Axenovich, and C. Winter. Poset Ramsey numbers: large Boolean lattice versus a fixed poset. Submitted, preprint available at arXiv:2110.07648v1, 2021.
  * [3] T. Bohman and F. Peng. A Construction for Boolean Cube Ramsey Numbers. Order, 2022.
  * [4] 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.
  * [5] 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. Order 39, 453–463, 2022.
  * [6] 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.
  * [7] 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.
  * [8] C. Cox and D. Stolee. Ramsey Numbers for Partially-Ordered Sets. Order 35(3), 557–579, 2018.
  * [9] P. Erdős, T. Gallai, and Zs. Tuza. Covering the cliques of a graph with vertices. Discrete Mathematics 108, 279–289, 1992.
  * [10] D. Grósz, A. Methuku, and C. Tompkins. Ramsey numbers of Boolean lattices. Submitted, preprint available at arXiv:2104.02002v1, 2021.
  * [11] 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).
  * [12] L. Lu, and K. Milans. Set families with forbidden subposets. Journal of Combinatorial Theory, Series A, 136, 126–142, 2015.
  * [13] L. Lu and C. Thompson. Poset Ramsey Numbers for Boolean Lattices. Order 39, 171–185, 2022.
  * [14] A. Méroueh. A LYM inequality for induced posets. Journal of Combinatorial Theory, Series A, 155, 398–417, 2018.
  * [15] 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.
  * [16] A. Methuku and C. Tompkins. Exact Forbidden Subposet Results using Chain Decompositions of the Cycle. Electronic Journal of Combinatorics 22(4), 2015.
  * [17] E. Sperner. Ein Satz über Untermengen einer endlichen Menge, (in German). Mathematische Zeitschrift, 27(1), 544–548, 1928.
  * [18] I. Tomon. Forbidden induced subposets of given height. Journal of Combinatorial Theory, Series A, 161, 537–562, 2019.
  * [19] J. Valdes. Parsing flowcharts and series-parallel graphs. Technical report STAN-CS-78-682, Computer Science Department, Stanford University, Stanford (1978).
  * [20] S. Walzer. Ramsey Variant of the 2-Dimension of Posets. In: Master Thesis, Karlsruhe Institute of Technology (2015).
  * [21] C. Winter. Poset Ramsey number R(P,Qn). I. Complete multipartite posets. Submitted, preprint available at arXiv:2204.03010v1, 2022.
  * [22] C. Winter. Poset Ramsey Number R(P,Qn). II. Antichains. In preparation, preprint available at arXiv:2205.02275v1, 2022.