Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-07T10:28:11.012Z Has data issue: false hasContentIssue false
  • English
  • Français

Path Ramsey Number for Random Graphs

Part of: Graph theory Extremal combinatorics

Published online by Cambridge University Press:  07 December 2015

SHOHAM LETZTER
SHOHAM LETZTER*
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: s.letzter@dpmms.cam.ac.uk)
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.

Answering a question raised by Dudek and Prałat, we show that if pn → ∞, w.h.p., whenever G = G(n, p) is 2-edge-coloured there is a monochromatic path of length (2/3 + o(1))n. This result is optimal in the sense that 2/3 cannot be replaced by a larger constant.

As part of the proof we obtain the following result. Given a graph G on n vertices with at least $(1-\varepsilon)\binom{n}{2}$ edges, whenever G is 2-edge-coloured, there is a monochromatic path of length at least $(2/3 - 110\sqrt{\varepsilon})n$ . This is an extension of the classical result by Gerencsér and Gyárfás which says that whenever Kn is 2-coloured there is a monochromatic path of length at least 2n/3.

MSC classification

Primary: 05D10: Ramsey theory
Secondary: 05C80: Random graphs

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 25 , Issue 4 , July 2016 , pp. 612 - 622
Copyright
Copyright © Cambridge University Press 2015 

References

[1] Beck, J. (1983) On size Ramsey number of paths, trees, and circuits I. J. Graph Theory 7 115–129.Google Scholar
[2] Beck, J. (1990) On size Ramsey number of paths, trees, and circuits II. In Mathematics of Ramsey Theory, Vol. 5 of Algorithms and Combinatorics, Springer, pp. 34–45.Google Scholar
[3] Benevides, F., Łuczak, T., Skokan, J., Scott, A. and White, M. (2012) Monochromatic cycles in 2-coloured graphs. Combin. Probab. Comput. 21 57–87.Google Scholar
[4] Bollobás, B. (1986) Extremal Graph Theory with Emphasis on Probabilistic Methods, AMS, published for the CBMS Regional Conference Series in Mathematics.Google Scholar
[5] Bollobás, B. (2001) Random Graphs, Cambridge University Press.CrossRefGoogle Scholar
[6] Conlon, D. (2014) Combinatorial theorems relative to a random set. Proceedings of the International Congress of Mathematicians, 4 303–328.Google Scholar
[7] Dudek, A. and Prałat, A. (2015) An alternative proof of the linearity of the size-Ramsey number of paths. Combin. Probab. Comput. 24 551–555.Google Scholar
[8] Erdős, P. (1981) Problems and results in graph theory. In The Theory and Applications of Graphs: Kalamazoo, MI, 1980, Wiley, pp. 331–341.Google Scholar
[9] Gerencsér, L. and Gyárfás, A. (1967) On Ramsey-type problems. Ann. Univ. Eötvös Sect. Math. 10 167–170.Google Scholar
[10] Gyárfás, A. and Sárközy, G. (2012) Star versus two stripes Ramsey numbers and a conjecture of Schelp. Combin. Probab. Comput. 21 179–186.CrossRefGoogle Scholar
[11] Kohayakawa, Y. (1997) Szemerédi's Regularity Lemma for sparse graphs. In Foundations of Computational Mathematics: Rio de Janeiro, 1997, Springer, pp. 216–230.CrossRefGoogle Scholar
[12] Pokrovskiy, A. (2014) Partitioning edge-coloured complete graphs into monochromatic cycles and paths. J. Combin. Theory Ser. B 106 70–97.Google Scholar
[13] Szemerédi, E. (1978) Regular partitions of graphs. Problèmes Combinatoires et Théorie des Graphes: Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976, Vol. 260 of Colloq. Internat. CNRS, CNRS, Paris, pp. 399–401.Google Scholar