A canonical Ramsey theorem for even cycles in random graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912130134966272 |
|---|---|
| author | Alvarado, José D. Kohayakawa, Y. Morris, Patrick Mota, Guilherme O. |
| author_facet | Alvarado, José D. Kohayakawa, Y. Morris, Patrick Mota, Guilherme O. |
| contents | The celebrated canonical Ramsey theorem of Erdős and Rado implies that for $2\leq k\in \mathbb{N}$, any colouring of the edges of $K_n$ with $n$ sufficiently large gives a copy of $C_{2k}$ which has one of three canonical colour patterns: monochromatic, rainbow or lexicographic. In this paper we show that if $p=ω(n^{-1+1/(2k-1)}\log n)$, then ${\mathbf{G}}(n,p)$ will asymptotically almost surely also have the property that any colouring of its edges induces canonical copies of $C_{2k}$. This determines the threshold for the canonical Ramsey property with respect to even cycles, up to a $\log$ factor. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_14566 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A canonical Ramsey theorem for even cycles in random graphs Alvarado, José D. Kohayakawa, Y. Morris, Patrick Mota, Guilherme O. Combinatorics The celebrated canonical Ramsey theorem of Erdős and Rado implies that for $2\leq k\in \mathbb{N}$, any colouring of the edges of $K_n$ with $n$ sufficiently large gives a copy of $C_{2k}$ which has one of three canonical colour patterns: monochromatic, rainbow or lexicographic. In this paper we show that if $p=ω(n^{-1+1/(2k-1)}\log n)$, then ${\mathbf{G}}(n,p)$ will asymptotically almost surely also have the property that any colouring of its edges induces canonical copies of $C_{2k}$. This determines the threshold for the canonical Ramsey property with respect to even cycles, up to a $\log$ factor. |
| title | A canonical Ramsey theorem for even cycles in random graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2411.14566 |