Poset Ramsey number R(P,Q_n). III. Chain Compositions and Antichains

Abstract: An induced subposet

(P_{2}, l e_{2})

of a poset

(P_{1}, l e_{1})

is a subset of

P_{1}

such that for every two

X, Y i n P_{2}

,

X l e_{2} Y

if and only if

X l e_{1} Y

. The Boolean lattice

Q_{n}

of dimension

n

is the poset consisting of all subsets of

1, d o t s, n

ordered by inclusion. Given two posets

P_{1}

and

P_{2}

the poset Ramsey number

R (P_{1}, P_{2})

is the smallest integer

N

such that in any blue/red coloring of the elements of

Q_{N}

there is either a monochromatically blue induced subposet isomorphic to

P_{1}

or a monochromatically red induced subposet isomorphic to

P_{2}

. We provide upper bounds on

R (P, Q_{n})

for two classes of

P

: parallel compositions of chains, i.e. posets consisting of disjoint chains which are pairwise element-wise incomparable, as well as subdivided

Q_{2}

, which are posets obtained from two parallel chains by adding a common minimal and a common maximal element. This completes the determination of

R (P, Q_{n})

for posets

P

with at most

4

elements. If

P

is an antichain

A_{t}

on

t

elements, we show that

R (A_{t}, Q_{n}) = n + 3

for

3 l e t l e l o g l o g n

. Additionally, we briefly survey proof techniques in the poset Ramsey setting

P

versus

Q_{n}

.

This page was built for publication: Poset Ramsey number $R(P,Q_n)$. III. Chain Compositions and Antichains