Poset Ramsey Numbers for Boolean Lattices

Abstract

A subposet $Q^{\prime }$ of a poset $Q$ is a \textit{copy of a poset} $P$ if there is a bijection $f$ between elements of $P$ and $Q^{\prime }$ such that $x\le y$ in $P$ iff $f(x)\le f(y)$ in $Q^{\prime }$. For posets $P,P^{\prime }$, let the \textit{poset Ramsey number} $R(P,P^{\prime })$ be the smallest $N$ such that no matter how the elements of the Boolean lattice $Q_N$ are colored red and blue, there is a copy of $P$ with all red elements or a copy of $P^{\prime }$ with all blue elements. Axenovich and Walzer introduced this concept in \textit{Order} (2017), where they proved $R(Q_2,Q_n)\le 2n+2$ and $R(Q_n,Q_m)\le mn+n+m$, where $Q_n$ is the Boolean lattice of dimension $n$. They later proved $2n\le R(Q_n,Q_n)\le n^2+2n$. Walzer later proved $R(Q_n,Q_n)\le n^2+1$. We provide some improved bounds for $R(Q_n,Q_m)$ for various $n,m\in \mathbb{N}$. In particular, we prove that $R(Q_n,Q_n)\le n^2-n+2$, $R(Q_2,Q_n)\le \frac{5}{3}n+2$, and $R(Q_3,Q_n)\le \frac{37}{16}n+\frac{39}{16}$. We also prove that $R(Q_2,Q_3)=5$, and $R(Q_m,Q_n)\le (m-2+\frac{9m-9}{(2m-3)(m+1)})n+m+3$ for all $n\ge m\ge 4$.

19 pages

Cited by in corpus (2)

• Rainbow Ramsey problems for the Boolean lattice
• Existence thresholds and Ramsey properties of random posets