Abstract | ||
---|---|---|
Let F → ( G ) r v [ F → ( G ) r e ] 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 A if for some constants c and C the probability that the binomial random graph K ( n , p ) has A tends to 0 when np d < c and tends to 1 while np d > C , p = p ( n ), n → ∞. Let | G | and e ( G ) stand for the number of the vertices and edges of a graph G , respectively. We prove that max H⊆G (e (H) |H| − 1) is crucial for K ( n , p ) → ( G ) r v , whereas 2 is crucial for K ( n , p ) → ( K 3 ) 2 e . The existence of sparse Ramsey graphs is also deduced. |
Year | DOI | Venue |
---|---|---|
1992 | 10.1016/0095-8956(92)90006-J | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
random graph,ramsey property | Ramsey theory,Random regular graph,Discrete mathematics,Graph,Combinatorics,Random graph,Vertex (geometry),Binomial,Cycle graph,Ramsey's theorem,Mathematics | Journal |
Volume | Issue | ISSN |
56 | 1 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
25 | 6.94 | 1 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tomasz Łuczak | 1 | 225 | 40.26 |
Andrzej Ruciński | 2 | 420 | 51.89 |