Poset Ramsey numbers: large Boolean lattice versus a fixed poset

DOI10.1017/S0963548323000032MaRDI QIDQ6085871zbMATH OpenOpenAlexFDO

Authors Maria Axenovich, Christian Winter

Publication date 8 November 2023

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2110.07648

zbMATH Keywords

Boolean lattice combinatorics of posets poset Ramsey number

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07)

Abstract: Given partially ordered sets (posets)

(P, l e q_{P})

and

(P^{'}, l e q_{P^{'}})

, we say that

P^{'}

contains a copy of

P

if for some injective function

f : P i g h t a r r o w P^{'}

and for any

X, Y i n P

,

X l e q_{P} Y

if and only of

f (X) l e q_{P^{'}} f (Y)

. For any posets

P

and

Q

, the poset Ramsey number

R (P, Q)

is the least positive integer

N

such that no matter how the elements of an

N

-dimensional Boolean lattice are colored in blue and red, there is either a copy of

P

with all blue elements or a copy of

Q

with all red elements. We focus on a poset Ramsey number

R (P, Q_{n})

for a fixed poset

P

and an

n

-dimensional Boolean lattice

Q_{n}

, as

n

grows large. We show a sharp jump in behaviour of this number as a function of

n

depending on whether or not

P

contains a copy of either a poset

V

, i.e. a poset on elements

A, B, C

such that

B > C

,

A > C

, and

A

and

B

incomparable, or a poset

L a m b d a

, its symmetric counterpart. Specifically, we prove that if

P

contains a copy of

V

or

L a m b d a

then

R (P, Q_{n}) g e q n + f r a c 115 f r a c n l o g n

. Otherwise

R (P, Q_{n}) l e q n + c (P)

for a constant

c (P)

. This gives the first non-marginal improvement of a lower bound on poset Ramsey numbers and as a consequence gives

R (Q_{2}, Q_{n}) = n + T h e t a (f r a c n l o g n)

.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Poset Ramsey numbers: large Boolean lattice versus a fixed poset

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6085871)