A New Lower Bound for the Diagonal Poset Ramsey Numbers
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915811816374272 |
|---|---|
| author | Ivan, Maria-Romina Wessels, Bernardus A. |
| author_facet | Ivan, Maria-Romina Wessels, Bernardus A. |
| contents | Given two finite posets $\mathcal P$ and $\mathcal Q$, their Ramsey number, denoted by $R(\mathcal P,\mathcal Q)$, is defined to be the smallest integer $N$ such that any blue/red colouring of the vertices of the hypercube $Q_N$ has either a blue induced copy of $\mathcal P$, or a red induced copy of $\mathcal Q$.
Axenovich and Walzer showed that, for fixed $\mathcal P$, $R(\mathcal P, Q_n)$ grows linearly with $n$. However, for the diagonal question, we do not even come close to knowing the order of growth of $R(Q_n,Q_n)$. The current upper bound is $R(Q_n,Q_n)\leq n^2-(1-o(1))n\log n$, due to Axenovich and Winter.
What about lower bounds? It is trivial to see that $2n\leq R(Q_n,Q_n)$, but surprisingly, even an incremental improvement required significant work. Recently, an elegant probabilistic argument of Winter gave that, for large enough $n$, $R(Q_n,Q_n)\geq 2.02n$.
In this paper we show that $R(Q_n,Q_n)\geq 2.7n+k$, where $k$ is a constant. Our current techniques might in principle show that in fact, for every $ε>0$, for large enough $n$, $R(Q_n,Q_n)\geq (3-ε)n$. Our methods exploit careful modifications of layered-colourings, for a large number of layers. These modifications are stronger than previous arguments as they are more constructive, rather than purely probabilistic. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_16556 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A New Lower Bound for the Diagonal Poset Ramsey Numbers Ivan, Maria-Romina Wessels, Bernardus A. Combinatorics 06A07, 05D10 Given two finite posets $\mathcal P$ and $\mathcal Q$, their Ramsey number, denoted by $R(\mathcal P,\mathcal Q)$, is defined to be the smallest integer $N$ such that any blue/red colouring of the vertices of the hypercube $Q_N$ has either a blue induced copy of $\mathcal P$, or a red induced copy of $\mathcal Q$. Axenovich and Walzer showed that, for fixed $\mathcal P$, $R(\mathcal P, Q_n)$ grows linearly with $n$. However, for the diagonal question, we do not even come close to knowing the order of growth of $R(Q_n,Q_n)$. The current upper bound is $R(Q_n,Q_n)\leq n^2-(1-o(1))n\log n$, due to Axenovich and Winter. What about lower bounds? It is trivial to see that $2n\leq R(Q_n,Q_n)$, but surprisingly, even an incremental improvement required significant work. Recently, an elegant probabilistic argument of Winter gave that, for large enough $n$, $R(Q_n,Q_n)\geq 2.02n$. In this paper we show that $R(Q_n,Q_n)\geq 2.7n+k$, where $k$ is a constant. Our current techniques might in principle show that in fact, for every $ε>0$, for large enough $n$, $R(Q_n,Q_n)\geq (3-ε)n$. Our methods exploit careful modifications of layered-colourings, for a large number of layers. These modifications are stronger than previous arguments as they are more constructive, rather than purely probabilistic. |
| title | A New Lower Bound for the Diagonal Poset Ramsey Numbers |
| topic | Combinatorics 06A07, 05D10 |
| url | https://arxiv.org/abs/2602.16556 |