The size-Ramsey number of powers of paths |
| |
| Authors: | Dennis Clemens Matthew Jenssen Yoshiharu Kohayakawa Natasha Morrison Guilherme Oliveira Mota Damian Reding Barnaby Roberts |
| |
| Institution: | 1. Institut für Mathematik, Technische Universität Hamburg, Hamburg, Germany;2. Department of Mathematics, London School of Economics, London, UK;3. Instituto de Matemática e Estatística, Universidade de São Paulo, São Paulo, Brazil;4. Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Cambridge, UK;5. Centro de Matemática, Computação e Cognição, Universidade Federal do ABC, Santo André, Brazil |
| |
| Abstract: | Given graphs  and  and a positive integer  , say that  is  -Ramsey for  , denoted  , if every  -coloring of the edges of  contains a monochromatic copy of  . The size-Ramsey number  of a graph  is defined to be  . Answering a question of Conlon, we prove that, for every fixed  , we have  , where  is the  th power of the  -vertex path  (ie, the graph with vertex set  and all edges  such that the distance between  and  in  is at most  ). Our proof is probabilistic, but can also be made constructive. |
| |
| Keywords: | powers of paths Ramsey size-Ramsey |
|
|
