Ramsey numbers of Boolean lattices

Dániel Grósz; Abhishek Methuku; Casey Tompkins

paper

Ramsey numbers of Boolean lattices

arXiv:2104.02002

Abstract

The poset Ramsey number $R (Q_{m}, Q_{n})$ is the smallest integer $N$ such that any blue-red coloring of the elements of the Boolean lattice $Q_{N}$ has a blue induced copy of $Q_{m}$ or a red induced copy of $Q_{n}$ . The weak poset Ramsey number $R_{w} (Q_{m}, Q_{n})$ is defined analogously, with weak copies instead of induced copies. It is easy to see that $R (Q_{m}, Q_{n}) \geq R_{w} (Q_{m}, Q_{n})$ . Axenovich and Walzer showed that $n + 2 \leq R (Q_{2}, Q_{n}) \leq 2 n + 2$ . Recently, Lu and Thompson improved the upper bound to $\frac{5}{3} n + 2$ . In this paper, we solve this problem asymptotically by showing that $R (Q_{2}, Q_{n}) = n + O (n / lo g n)$ . In the diagonal case, Cox and Stolee proved $R_{w} (Q_{n}, Q_{n}) \geq 2 n + 1$ using a probabilistic construction. In the induced case, Bohman and Peng showed $R (Q_{n}, Q_{n}) \geq 2 n + 1$ using an explicit construction. Improving these results, we show that $R_{w} (Q_{m}, Q_{n}) \geq n + m + 1$ for all $m \geq 2$ and large $n$ by giving an explicit construction; in particular, we prove that $R_{w} (Q_{2}, Q_{n}) = n + 3$ .