Poset Ramsey numbers: large Boolean lattice versus a fixed poset

Abstract

Given partially ordered sets (posets) $(P,{\le }_P)$ and $(P^{\prime },{\le }_{P^{\prime }})$, we say that $P^{\prime }$ contains a copy of $P$ if for some injective function $f:P\to P^{\prime }$ and for any $X,Y\in P$, $X{\le }_{P}Y$ if and only of $f(X){\le }_{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 $\hat{I}›$, its symmetric counterpart. Specifically, we prove that if $P$ contains a copy of $V$ or $\hat{I}›$ then $R(P,Q_n)\ge n+\frac{1}{15}\frac{n}{\log n}$. Otherwise $R(P,Q_n)\le 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+\hat{I}˜(\frac{n}{\log n})$.

18 pages, 2 figures