Thresholds for constrained Ramsey and anti-Ramsey problems
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910893683507200 |
|---|---|
| author | Behague, Natalie Hancock, Robert Hyde, Joseph Letzter, Shoham Morrison, Natasha |
| author_facet | Behague, Natalie Hancock, Robert Hyde, Joseph Letzter, Shoham Morrison, Natasha |
| contents | Let $H_1$ and $H_2$ be graphs. A graph $G$ has the constrained Ramsey property for $(H_1,H_2)$ if every edge-colouring of $G$ contains either a monochromatic copy of $H_1$ or a rainbow copy of $H_2$. Our main result gives a 0-statement for the constrained Ramsey property in $G(n,p)$ whenever $H_1 = K_{1,k}$ for some $k \ge 3$ and $H_2$ is not a forest. Along with previous work of Kohayakawa, Konstadinidis and Mota, this resolves the constrained Ramsey property for all non-trivial cases with the exception of $H_1 = K_{1,2}$, which is equivalent to the anti-Ramsey property for $H_2$.
For a fixed graph $H$, we say that $G$ has the anti-Ramsey property for $H$ if any proper edge-colouring of $G$ contains a rainbow copy of $H$. We show that the 0-statement for the anti-Ramsey problem in $G(n,p)$ can be reduced to a (necessary) colouring statement, and use this to find the threshold for the anti-Ramsey property for some particular families of graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_06881 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Thresholds for constrained Ramsey and anti-Ramsey problems Behague, Natalie Hancock, Robert Hyde, Joseph Letzter, Shoham Morrison, Natasha Combinatorics 05D10, 05C80 Let $H_1$ and $H_2$ be graphs. A graph $G$ has the constrained Ramsey property for $(H_1,H_2)$ if every edge-colouring of $G$ contains either a monochromatic copy of $H_1$ or a rainbow copy of $H_2$. Our main result gives a 0-statement for the constrained Ramsey property in $G(n,p)$ whenever $H_1 = K_{1,k}$ for some $k \ge 3$ and $H_2$ is not a forest. Along with previous work of Kohayakawa, Konstadinidis and Mota, this resolves the constrained Ramsey property for all non-trivial cases with the exception of $H_1 = K_{1,2}$, which is equivalent to the anti-Ramsey property for $H_2$. For a fixed graph $H$, we say that $G$ has the anti-Ramsey property for $H$ if any proper edge-colouring of $G$ contains a rainbow copy of $H$. We show that the 0-statement for the anti-Ramsey problem in $G(n,p)$ can be reduced to a (necessary) colouring statement, and use this to find the threshold for the anti-Ramsey property for some particular families of graphs. |
| title | Thresholds for constrained Ramsey and anti-Ramsey problems |
| topic | Combinatorics 05D10, 05C80 |
| url | https://arxiv.org/abs/2401.06881 |