Poset Ramsey number $R(P,Q_n)$. I. Complete multipartite posets

Abstract

A poset $(P^{\prime },{\le }_{P^{\prime }})$ contains a copy of some other poset $(P,{\le }_P)$ if there is an injection $f:P^{\prime }\to P$ where for every $X,Y\in P$, $X{\le }_{P}Y$ if and only if $f(X){\le }_{P^{\prime }}f(Y)$. For any posets $P$ and $Q$, the poset Ramsey number $R(P,Q)$ is the smallest integer $N$ such that any blue/red coloring of a Boolean lattice of dimension $N$ contains either a copy of $P$ with all elements blue or a copy of $Q$ with all elements red. We denote by $K_{t_1,\dots ,t_{\ell }}$ a complete $\ell$-partite poset, i.e.\ a poset consisting of $\ell$ pairwise disjoint sets $A^i$ of size $t_i$, $1\le i\le \ell$, such that for any $i,j\in \{1,\dots ,\ell \}$ and any two $X\in A^i$ and $Y\in A^j$, $X<Y$ if and only if $i<j$. In this paper we show that $R(K_{t_1,\dots ,t_{\ell }},Q_n)\le n+\frac{(2+o_n(1))\ell n}{\log n}$.

8 pages, 3 figures