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 |
|
|