KIT | KIT-Bibliothek | Impressum | Datenschutz

Poset Ramsey number R(P,Qn). III. Chain compositions and antichains

Winter, Christian ORCID iD icon 1,2
1 Karlsruher Institut für Technologie (KIT)
2 Institut für Experimentelle Teilchenphysik (ETP), Karlsruher Institut für Technologie (KIT)

Abstract:

An induced subposet (P$_2$, ≤$_2$) of a poset (P$_1$, ≤$_1$) is a subset of P$_1$ such that for every two
X, Y ∈ P$_2$ , X ≤$_2$ Y if and only if X ≤$_1$ Y . The Boolean lattice Q$_n$ of dimension n is the poset consisting of all subsets of {1, . . . , 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 ≤ t ≤ log log n. Additionally, we briefly
survey proof techniques in the poset Ramsey setting P versus Q$_n$.


Verlagsausgabe §
DOI: 10.5445/IR/1000170424
Veröffentlicht am 10.05.2024
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Experimentelle Teilchenphysik (ETP)
KIT-Bibliothek (BIB)
Publikationstyp Zeitschriftenaufsatz
Publikationsmonat/-jahr 07.2024
Sprache Englisch
Identifikator ISSN: 0012-365X, 1872-681X
KITopen-ID: 1000170424
Erschienen in Discrete Mathematics
Verlag Elsevier
Band 347
Heft 7
Seiten Art.-Nr.: 114031
Vorab online veröffentlicht am 17.04.2024
Nachgewiesen in Dimensions
Web of Science
Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page