Hostname: page-component-745bb68f8f-b6zl4 Total loading time: 0 Render date: 2025-02-07T00:20:46.990Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  02 October 2014

ANDRZEJ DUDEK  and
PAWEŁ PRAŁAT
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.

Keywords

Primary 05D10Secondary 05C55
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 24 , Issue 3 , May 2015 , pp. 551 - 555
Copyright
Copyright © Cambridge University Press 2014 

References

[1]Alon, N. and Chung, F. R. K. (1988) Explicit construction of linear sized tolerant networks. Discrete Math. 72 15–19.Google Scholar
[2]Beck, J. (1983) On size Ramsey number of paths, trees, and circuits~I. J. Graph Theory 7 115–129.Google Scholar
[3]Beck, J. (1990) On size Ramsey number of paths, trees and circuits~II. In Mathematics of Ramsey Theory (Nešetřil, J. and Rödl, V., eds), Vol. 5 of Algorithms and Combinatorics, Springer, pp. 34–45.Google Scholar
[4]Bollobás, B. (1986) Extremal Graph Theory with Emphasis on Probabilistic Methods, Vol. 62 of CBMS Regional Conference Series in Mathematics, AMS.CrossRefGoogle Scholar
[5]Bollobás, B. (2001) Random Graphs, Cambridge University Press.Google Scholar
[6]Erdős, P. (1981) On the combinatorial problems which I would most like to see solved. Combinatorica 1 25–42.CrossRefGoogle Scholar
[7]Erdős, P., Faudree, R., Rousseau, C. and Schelp, R. (1978) The size Ramsey number. Period. Math. Hungar. 9 145–161.CrossRefGoogle Scholar
[8]Gerencsér, L. and Gyárfás, A. (1967) On Ramsey-type problems. Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 10 167–170.Google Scholar
[9]Letzter, S. (2014) Path Ramsey number for random graphs. arXiv:1405.6670 [math.CO]Google Scholar
[10]Pokrovskiy, A. (2014) Partitioning edge-coloured complete graphs into monochromatic cycles and paths. J. Combin. Theory Ser. B 106 70–97.Google Scholar