The multicolour size-Ramsey number of powers of paths
| Autor: | Han, Jie, Jenssen, Matthew, Kohayakawa, Yoshiharu, Mota, Guilherme Oliveira, Roberts, Barnaby |
|---|---|
| Rok vydání: | 2018 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Given a positive integer $s$, a graph $G$ is $s$-Ramsey for a graph $H$, denoted $G\rightarrow (H)_s$, if every $s$-colouring of the edges of $G$ contains a monochromatic copy of $H$. The $s$-colour size-Ramsey number ${\hat{r}}_s(H)$ of a graph $H$ is defined to be ${\hat{r}}_s(H)=\min\{|E(G)|\colon G\rightarrow (H)_s\}$. We prove that, for all positive integers $k$ and $s$, we have ${\hat{r}}_s(P_n^k)=O(n)$, where $P_n^k$ is the $k$th power of the $n$-vertex path $P_n$. Comment: 15 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|