Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2403.13742 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910376118976512 |
|---|---|
| author | Aragão, Lucas Marciano, João Pedro Mendonça, Walner |
| author_facet | Aragão, Lucas Marciano, João Pedro Mendonça, Walner |
| contents | A classical result of Chvátal implies that if $n \geq (r-1)(t-1) +1$, then any colouring of the edges of $K_n$ in red and blue contains either a monochromatic red $K_r$ or a monochromatic blue $P_t$. We study a natural generalization of his result, determining the exact minimum degree condition for a graph $G$ on $n = (r - 1)(t - 1) + 1$ vertices which guarantees that the same Ramsey property holds in $G$. In particular, using a slight generalization of a result of Haxell, we show that $δ(G) \geq n - \lceil t/2 \rceil$ suffices, and that this bound is best possible. We also use a classical result of Bollobás, Erdős, and Straus to prove a tight minimum degree condition in the case $r = 3$ for all $n \geq 2t - 1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_13742 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Degree conditions for Ramsey goodness of paths Aragão, Lucas Marciano, João Pedro Mendonça, Walner Combinatorics A classical result of Chvátal implies that if $n \geq (r-1)(t-1) +1$, then any colouring of the edges of $K_n$ in red and blue contains either a monochromatic red $K_r$ or a monochromatic blue $P_t$. We study a natural generalization of his result, determining the exact minimum degree condition for a graph $G$ on $n = (r - 1)(t - 1) + 1$ vertices which guarantees that the same Ramsey property holds in $G$. In particular, using a slight generalization of a result of Haxell, we show that $δ(G) \geq n - \lceil t/2 \rceil$ suffices, and that this bound is best possible. We also use a classical result of Bollobás, Erdős, and Straus to prove a tight minimum degree condition in the case $r = 3$ for all $n \geq 2t - 1$. |
| title | Degree conditions for Ramsey goodness of paths |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2403.13742 |