Diagonal poset Ramsey numbers

Abstract

A poset $(Q,{\le }_Q)$ contains an induced copy of a poset $(P,{\le }_P)$ if there exists an injective mapping $\ddot{I}•:P\to Q$ such that for any two elements $X,Y\in P$, $X{\le }_{P}Y$ if and only if $\ddot{I}•(X){\le }_Q\ddot{I}•(Y)$. By $Q_n$ we denote the Boolean lattice $(2^{[n]},\subseteq )$. The poset Ramsey number $R(P,Q)$ for posets $P$ and $Q$ is the least integer $N$ for which any coloring of the elements of $Q_N$ in blue and red contains either a blue induced copy of $P$ or a red induced copy of $Q$. In this paper, we show that $R(Q_m,Q_n)\le nm-(1-o(1))n\log m$ where $n\ge m$ and $m$ is sufficiently large. This improves the best known upper bound on $R(Q_n,Q_n)$ from $n^2-n+2$ to $n^2-(1-o(1))n\log n$. Furthermore, we determine $R(P,P)$ where $P$ is an $n$-fork or $n$-diamond up to an additive constant of $2$. A poset $(Q,{\le }_Q)$ contains a weak copy of $(P,{\le }_P)$ if there is an injection $\ddot{I}ˆ:P\to Q$ such that $\ddot{I}ˆ(X){\le }_Q\ddot{I}ˆ(Y)$ for any $X,Y\in P$ with $X{\le }_{P}Y$. The weak poset Ramsey number $R^{\text{w}}(P,Q)$ is the smallest $N$ for which any blue/red-coloring of $Q_N$ contains a blue weak copy of $P$ or a red weak copy of $Q$. We show that $R^{\text{w}}(Q_n,Q_n)\le 0.96n^2$.

18 pages, 4 figures