Size-Ramsey numbers of graphs with maximum degree three
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912593131601920 |
|---|---|
| author | Draganić, Nemanja Petrova, Kalina |
| author_facet | Draganić, Nemanja Petrova, Kalina |
| contents | The size-Ramsey number $\hat{r}(H)$ of a graph $H$ is the smallest number of edges a (host) graph $G$ can have, such that for any red/blue colouring of $G$, there is a monochromatic copy of $H$ in $G$. Recently, Conlon, Nenadov and Trujić showed that if $H$ is a graph on $n$ vertices and maximum degree three, then $\hat{r}(H) = O(n^{8/5})$, improving upon the upper bound of $n^{5/3 + o(1)}$ by Kohayakawa, Rödl, Schacht and Szemerédi. In this paper we show that $\hat{r}(H)\leq n^{3/2+o(1)}$. While the previously used host graphs were vanilla binomial random graphs, we prove our result using a novel host graph construction. Our bound hits a natural barrier of the existing methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2207_05048 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Size-Ramsey numbers of graphs with maximum degree three Draganić, Nemanja Petrova, Kalina Combinatorics 05D10, 05D40, 05C80 The size-Ramsey number $\hat{r}(H)$ of a graph $H$ is the smallest number of edges a (host) graph $G$ can have, such that for any red/blue colouring of $G$, there is a monochromatic copy of $H$ in $G$. Recently, Conlon, Nenadov and Trujić showed that if $H$ is a graph on $n$ vertices and maximum degree three, then $\hat{r}(H) = O(n^{8/5})$, improving upon the upper bound of $n^{5/3 + o(1)}$ by Kohayakawa, Rödl, Schacht and Szemerédi. In this paper we show that $\hat{r}(H)\leq n^{3/2+o(1)}$. While the previously used host graphs were vanilla binomial random graphs, we prove our result using a novel host graph construction. Our bound hits a natural barrier of the existing methods. |
| title | Size-Ramsey numbers of graphs with maximum degree three |
| topic | Combinatorics 05D10, 05D40, 05C80 |
| url | https://arxiv.org/abs/2207.05048 |