Erdős-Hajnal problems for posets

Abstract

We say that a poset $(Q,{\le }_Q)$ contains an induced copy of a poset $(P,{\le }_P)$ if there is an injective function $\ddot{I}•:P\to Q$ such that for every two $X,Y\in P$,\;\;$X{\le }_{P}Y$ if and only if $\ddot{I}•(X){\le }_Q\ddot{I}•(Y)$. We denote the Boolean lattice $(2^{[n]},\subseteq )$ by $Q_n$. Given a fixed $2$-coloring $c$ of a poset $P$, the poset Erdős-Hajnal number of this colored poset is the smallest integer $N$ such that every $2$-coloring of the Boolean lattice $Q_N$ contains an induced copy of $P$ colored as in $c$, or a monochromatic induced copy of $Q_n$. We present bounds on the poset Erdős-Hajnal number of general colored posets, antichains, chains, and small Boolean lattices. Let the poset Ramsey number $R(Q_n,Q_n)$ be the least $N$ such that every $2$-coloring of $Q_N$ contains a monochromatic induced copy of $Q_n$. As a corollary, we show that $R(Q_n,Q_n)>2.02n$, improving on the best known lower bound $2n+1$ by Cox and Stolee \cite{CS}.

20 pages, 8 figures. Published in Order, 2025. Fixed a mistake in the previous version. As a result, the constant 2.24 was replaced by the weaker 2.02