Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-16T19:56:38.506Z Has data issue: false hasContentIssue false

An Alternative Proof of the Linearity of the Size-Ramsey Number of Paths

Published online by Cambridge University Press:  02 October 2014

ANDRZEJ DUDEK
Affiliation:
Department of Mathematics, Western Michigan University, Kalamazoo, MI 49008-5248, USA (e-mail: andrzej.dudek@wmich.edu)
PAWEŁ PRAŁAT
Affiliation:
Department of Mathematics, Ryerson University, Toronto, ON, M5B 2K3, Canada (e-mail: pralat@ryerson.ca)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The size-Ramsey number $\^{r} $(F) of a graph F is the smallest integer m such that there exists a graph G on m edges with the property that every colouring of the edges of G with two colours yields a monochromatic copy of F. In 1983, Beck provided a beautiful argument that shows that $\^{r} $(Pn) is linear, solving a problem of Erdős. In this note, we provide another proof of this fact that actually gives a better bound, namely, $\^{r} $(Pn) < 137n for n sufficiently large.

Information

Type
Paper
Copyright
Copyright © Cambridge University Press 2014