Erdős-Hajnal problems for posets
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910898528976896 |
|---|---|
| author | Winter, Christian |
| author_facet | Winter, Christian |
| contents | We say that a poset $(Q,\le_{Q})$ contains an induced copy of a poset $(P,\le_P)$ if there is an injective function $ϕ\colon P\to Q$ such that for every two $X,Y\in P$,\;\;$X\le_P Y$ if and only if $ϕ(X)\le_Q ϕ(Y)$. We denote the Boolean lattice $(2^{[n]},\subseteq)$ by $Q_n$. Given a fixed $2$-coloring $c$ of a poset $P$, the poset Erdős-Hajnal number of this colored poset is the smallest integer $N$ such that every $2$-coloring of the Boolean lattice $Q_N$ contains an induced copy of $P$ colored as in $c$, or a monochromatic induced copy of $Q_n$. We present bounds on the poset Erdős-Hajnal number of general colored posets, antichains, chains, and small Boolean lattices. Let the poset Ramsey number $R(Q_n,Q_n)$ be the least $N$ such that every $2$-coloring of $Q_N$ contains a monochromatic induced copy of $Q_n$. As a corollary, we show that $R(Q_n,Q_n)> 2.02n$, improving on the best known lower bound $2n+1$ by Cox and Stolee \cite{CS}. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_02621 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Erdős-Hajnal problems for posets Winter, Christian Combinatorics 06A07, 05D10 We say that a poset $(Q,\le_{Q})$ contains an induced copy of a poset $(P,\le_P)$ if there is an injective function $ϕ\colon P\to Q$ such that for every two $X,Y\in P$,\;\;$X\le_P Y$ if and only if $ϕ(X)\le_Q ϕ(Y)$. We denote the Boolean lattice $(2^{[n]},\subseteq)$ by $Q_n$. Given a fixed $2$-coloring $c$ of a poset $P$, the poset Erdős-Hajnal number of this colored poset is the smallest integer $N$ such that every $2$-coloring of the Boolean lattice $Q_N$ contains an induced copy of $P$ colored as in $c$, or a monochromatic induced copy of $Q_n$. We present bounds on the poset Erdős-Hajnal number of general colored posets, antichains, chains, and small Boolean lattices. Let the poset Ramsey number $R(Q_n,Q_n)$ be the least $N$ such that every $2$-coloring of $Q_N$ contains a monochromatic induced copy of $Q_n$. As a corollary, we show that $R(Q_n,Q_n)> 2.02n$, improving on the best known lower bound $2n+1$ by Cox and Stolee \cite{CS}. |
| title | Erdős-Hajnal problems for posets |
| topic | Combinatorics 06A07, 05D10 |
| url | https://arxiv.org/abs/2310.02621 |