Ramsey properties of random graphs
type: Item
instance of: scholarly article
title: Ramsey properties of random graphs
zbMATH Open document ID: 0711.05041
DOI: 10.1016/0095-8956(92)90006-J
author: Tomasz Łuczak
author: Andrzej Ruciński
author: Bernd Voigt
published in: Journal of Combinatorial Theory. Series B
publication date: 1991-01-01T00:00:00Z
review text: Let \(F\to (G)^ v_ r[F\to (G)^ e_ r]\) mean that for every r- coloring of the vertices [edges] of graph F there is a monochromatic copy of G in F. A rational d is said to be crucial for property \({\mathcal A}\) if for some constants c and C the probability that the binomial random graph K(n,p) has \({\mathcal A}\) tends to 0 when \(np^ d<c\) and tends to 1 while \(np^ d>C\), \(p=p(n)\), \(n\to \infty\). Let \(| G|\) and e(G) stand for the number of the vertices and edges of a graph G, respectively. We prove that \(\max_{H\subseteq G}e(H)/| H| -1\) is crucial for \(K(n,p)\to (G)^ v_ r\), whereas 2 is crucial for \(K(n,p)\to (K_ 3)^ e_ 2\). The existence of sparse Ramsey graphs is also deduced.
reviewed by: Andrzej Ruciński
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C55
zbMATH DE Number: 4168722
zbMATH Keywords: binomial random graph
zbMATH Keywords: sparse Ramsey graphs
MaRDI profile type: Publication
Recommended article: Ramsey properties of random hypergraphs
Recommended article: Ramsey properties of random graphs and folkman numbers
Recommended article: Anti-Ramsey properties of random graphs
Recommended article: On an anti-Ramsey property of random graphs
Recommended article: Vertex Ramsey properties of randomly perturbed graphs
Recommended article: Ramseyan properties of graphs
Recommended article: Ramsey properties of random subgraphs of pseudo-random graphs
Recommended article: Properties of Ramsey graphs
description: scientific article; zbMATH DE number 4168722