An exponential upper bound for induced Ramsey numbers
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917077549318144 |
|---|---|
| author | Aragão, Lucas Campos, Marcelo Dahia, Gabriel Filipe, Rafael Marciano, João Pedro |
| author_facet | Aragão, Lucas Campos, Marcelo Dahia, Gabriel Filipe, Rafael Marciano, João Pedro |
| contents | The induced Ramsey number $R_{\mathrm{ind}}(H; r)$ of a graph $H$ is the minimum number $N$ such that there exists a graph with $N$ vertices for which all $r$-colourings of its edges contain a monochromatic induced copy of $H$. Our main result is the existence of a constant $C > 0$ such that, for every graph $H$ on $k$ vertices, these numbers satisfy \begin{equation*}
R_{\mathrm{ind}}(H; r) \le r^{C r k}. \end{equation*} When $r = 2$, this resolves a conjecture of Erdős from 1975. For $r > 2$, it answers a question of Conlon, Fox and Sudakov in a strong form. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_22629 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An exponential upper bound for induced Ramsey numbers Aragão, Lucas Campos, Marcelo Dahia, Gabriel Filipe, Rafael Marciano, João Pedro Combinatorics The induced Ramsey number $R_{\mathrm{ind}}(H; r)$ of a graph $H$ is the minimum number $N$ such that there exists a graph with $N$ vertices for which all $r$-colourings of its edges contain a monochromatic induced copy of $H$. Our main result is the existence of a constant $C > 0$ such that, for every graph $H$ on $k$ vertices, these numbers satisfy \begin{equation*} R_{\mathrm{ind}}(H; r) \le r^{C r k}. \end{equation*} When $r = 2$, this resolves a conjecture of Erdős from 1975. For $r > 2$, it answers a question of Conlon, Fox and Sudakov in a strong form. |
| title | An exponential upper bound for induced Ramsey numbers |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2509.22629 |