Discrete Mathematics Seminar - The Ramsey number of Boolean lattices

Speaker: Casey Tompkins (Rényi Institute, Budapest)

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) >= R_w(Q_m,Q_n).

Axenovich and Walzer showed that n+2 <= R(Q₂,Q_n) <= 2n+2. Recently, Lu and Thompson improved the upper bound to 5/3 n + 2. In this talk, we solve this problem asymptotically by showing that R(Q₂,Q_n)=n+O(n / log n).

This is work with Daniel Grosz and Abhishek Methuku.