Poset Ramsey Numbers for Boolean Lattices

Publication date: 18 September 2019

Abstract: A subposet

Q^{'}

of a poset

Q

is a extit{copy of a poset}

P

if there is a bijection

f

between elements of

P

and

Q^{'}

such that

x l e y

in

P

iff

f (x) l e f (y)

in

Q^{'}

. For posets

P, P^{'}

, let the extit{poset Ramsey number}

R (P, P^{'})

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^{'}

with all blue elements. Axenovich and Walzer introduced this concept in extit{Order} (2017), where they proved

R (Q_{2}, Q_{n}) l e 2 n + 2

and

R (Q_{n}, Q_{m}) l e m n + n + m

, where

Q_{n}

is the Boolean lattice of dimension

n

. They later proved

2 n l e R (Q_{n}, Q_{n}) l e n^{2} + 2 n

. Walzer later proved

R (Q_{n}, Q_{n}) l e n^{2} + 1

. We provide some improved bounds for

R (Q_{n}, Q_{m})

for various

n, m i n m a t h b b N

. In particular, we prove that

R (Q_{n}, Q_{n}) l e n^{2} - n + 2

,

R (Q_{2}, Q_{n}) l e f r a c 53 n + 2

, and

R (Q_{3}, Q_{n}) l e f r a c 3716 n + f r a c 3916

. We also prove that

R (Q_{2}, Q_{3}) = 5

, and

R (Q_{m}, Q_{n}) l e (m - 2 + f r a c 9 m - 9 (2 m - 3) (m + 1)) n + m + 3

for all

n g e m g e 4

.

This page was built for publication: Poset Ramsey Numbers for Boolean Lattices