Poset Ramsey Numbers for Boolean Lattices

By Joshua Thompson

8 November 2019

A subposet Q' of a poset Q is a copy of a poset P if there is a bijection f between elements of P and Q' such that xy in P iff f(x) ≤ f(y) in Q'. For posets P, P', let the poset Ramsey number R(P,P') be the smallest N such that no matter how the elements of the Boolean lattice QN are colored red and blue, there is a copy of P with all red elements or a copy of P' with all blue elements. Axenovich and Walzer introduced this concept in Order (2017), where they proved R(Q2, Qn) ≤ 2n + 2 and R(Qn, Qm) ≤ mn + n + m, where Qn is the Boolean lattice of dimension n. They later proved 2nR(Qn, Qn) ≤ n2 + 2n. Walzer later proved R(Qn, Qn) ≤ n2 + 1. We provide some improved bounds for R(Qn, Qm) for various n,mN. In particular, we prove that R(Qn, Qn) ≤ n2 - n + 2, R(Q2, Qn) ≤ (5/3)n + 2, and R(Q3, Qn) ≤ (37/16)n + 39/16. We also prove that R(Q2,Q3) = 5, and R(Qm, Qn) ≤ (m - 2 + (9m - 9)((2m - 3)(m + 1)))n + m + 3 for all nm ≥ 4.